We present three contributions to the understanding of QMAs with multiple provers :

• We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM 2009], yielding a soundness gap $\Omega(N^{-2})$. Our improvement is achieved without the use of an instance w ith a constant soundness gap (i.e., without using a ``PCP'').
• We give a tight soundness analysis of the protocol of [Chen and Drucker, ArXiV 2010], thereby improving their result from a ``monolithic'' protocol where $\Theta(\sqrt{N})$ provers are needed in order to have any soundness gap, to a protocol with a smooth trade-off between the number of provers $\kappa$ and a soundness gap $\Omega(\kappa^{2}N^{-1})$, as long as $\kappa \in \Omega(\log N)$. (And, when $\kappa \in \Omega(\log N)$, we recover the original parameters of Chen and Drucker.)
• We make progress towards an open question of [Aaronson et al., ToC 2009] about what kinds of NP-complete problems are amenable to ``sublinear'' multiple-prover QMA protocols, by observing that a large class of such examples can easily be derived from results already in the PCP literature --- namely, at least the languages recognized by a non-deterministic RAMs in quasilinear time.

A d-gem is a $\{+,-,\times\}$-circuit having very few $\times$-gates and computing from $\{x\}\cup Z$ a univariate polynomial of degree $d$ having $d$ distinct integer roots. We introduce $d$-gems because they offer the remote possibility of being helpful for factoring integers, and because their exiatence for infinitely many $d$ would disprove a form of the Blum-Cucker-Shub-Smale conjecture (strengthened to allow arbitrary constants). A natural step towards a better understanding of the BCSS conjecture thus would be to construct $d$-gems or to rule out their existence. Ruling out $d$-gems for large $d$ is currently totally out of reach. Here the best we can do towards that goal is to prove that skew $2^n$-gems if they exist require $n$ $\{+,-\}$-gates and that skew $2^n$-gems or any $n\geq5$ would provide new solutions to the Prouhet-Tarry-Escott problem in number theory (skew meaning the further restriction that each $\{+,-\}$-gate merely adds an integer to a polynomial). In the opposite direction, here we do manage to construct skew $d$-gems for several values of $d$ up to $55$.

We consider computations of a Turing machine under noise that causes violations of the transition function. Given an upper bound \( \beta \) on the size of bursts of faults, we construct a Turing machine \( M(\beta) \) subject to faults that can simulate any fault-free machine under the condition that the time between bursts is lowerbounded by \( O(\beta^2) \).

We describe a method to upper bound the quantum query complexity of Boolean formula evaluation problems, using fundamental theorems about the general adversary bound. This nonconstructive method can give an upper bound on query complexity without producing an algorithm. For example, we describe an oracle problem which we prove (non-constructively) can be solved in $O(1)$ queries, where the previous best quantum algorithm uses a polylogarithmic number of queries. We then give an explicit $O(1)$-query algorithm for this problem based on span programs.

Can complexity classes be characterized in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings? Although this might seem improbable, a series of papers has recently provided evidence that this may be the case. In particular, it is known that there is a class of problems $\cal C$ defined in terms of polynomial-time truth-table reducibility to $RK$ (the set of Kolmogorov-random strings) that lies between $BPP$ and $PSPACE$.

The results in this paper were obtained, as part of an investigation of whether this upper bound can be improved, to show $$ BPP \subseteq {\cal C} \subseteq PSPACE \cap Ppoly. \quad\quad\quad(*)$$ In fact, we conjecture that ${\cal C} = BPP = Polytime$, and we close this paper with a discussion of the possibility this might be an avenue for trying to prove the equality of $BPP$ and $Polytime$.

In this paper, we present a collection of true statements in the language of arithmetic, (each provable in ZF) and show that if these statements can be proved in certain extensions of Peano arithmetic ($PA$), then (*) holds. Although it was subsequently proved (by Allender, Buhrman, Friedman and Loff) that infinitely many of these statements are, in fact, independent of those extensions of $PA$, we present these results in the hope that related ideas may yet contribute to a proof of ${\cal C} = BPP$, and because this work did serve as a springboard for subsequent work in the area.

We prove tight bounds of $\Theta(k \log k)$ queries for non-adaptively testing whether a function $f: \{ 0,1 \}^n \to \{ 0,1 \}$ is a $k$-parity or far from any $k$-parity. The lower bound combines a recent method of Blais, Brody and Matulef to get lower bounds for testing from communication complexity with an $\Omega(k\log k)$ lower bound for the one-way communication complexity of $k$-disjointness.

This paper studies a generalization of multi-prover interactive proofs in which a verifier interacts with two competing teams of provers: one team attempts to convince the verifier to accept while the other attempts to convince the verifier to reject. Each team consists of two provers who jointly implement a no-signaling strategy. No-signaling strategies are a curious class of joint strategy that cannot in general be implemented without communication between the provers, yet cannot be used as a black box to establish communication between them. Attention is restricted in this paper to two-turn interactions in which the verifier asks questions of each of the four provers and decides whether to accept or reject based on their responses. We prove that the complexity class of decision problems that admit two-turn interactive proofs with competing teams of no-signaling provers is a subset of PSPACE. This upper bound matches existing PSPACE lower bounds on the following two disparate and weaker classes of interactive proof:

• Two-turn multi-prover interactive proofs with only one team of no-signaling provers.
• Two-turn competing-prover interactive proofs with only one prover per team.

The completely bounded trace and spectral norms, for finite-dimensional spaces, are known to be efficiently expressible by semidefinite programs (J. Watrous, Theory of Computing 5: 11, 2009). This paper presents two new, and arguably simpler, semidefinite programming formulations of these norms.

We prove that if A is a large random relational structure (with at least one relation of arity at least 2) then the homomorphism extension problem Ext(A) is almost surely NP-complete.

We consider the problems of determining the feasibility of a linear congruence, producing a solution to a linear congruence, and finding a spanning set for the nullspace of an integer matrix, where each problem is considered modulo an arbitrary constant $k \geqslant 2$. These problems are known to be complete for the logspace modular counting classes $\mathrm{Mod_k L = coMod_k L}$ in the special case when $k$ is prime (Buntrock et al 1992). By considering variants of standard logspace function classes -- related to $\mathrm{\#L}$ and functions computable by $\mathrm{UL}$ machines, but which only characterize the number of accepting paths modulo $k$ -- we show that these problems of linear algebra are also complete for $\mathrm{coMod_k L}$ for any constant $k \geqslant 2$.

Our results are obtained by defining a class of functions $\mathrm{FUL_k}$ which are low for $\mathrm{Mod_k L}$ and $\mathrm{coMod_k L}$ for $k \geqslant 2$, using ideas similar to those used in the case of k prime in (Buntrock et al 1992) to show closure of $\mathrm{Mod_k L}$ under $\mathrm{NC^1}$ reductions (including $\mathrm{Mod_k L}$ oracle reductions). In addition to the results above, we briefly consider the relationship of the class $\mathrm{FUL_k}$ for arbitrary moduli $k$ to the class $\mathrm{F \cdot coMod_k L}$ of functions whose output symbols are verifiable by $\mathrm{coMod_k L}$ algorithms; and consider what consequences such a comparison may have for oracle closure results of the form $\mathrm{Mod_k L^{Mod_k L} = Mod_k L}$ for composite $k$.

We show that any number of parties can coherently exchange any one pure quantum state for another, without communication, given prior shared entanglement. Two applications of this fact to the study of multi-prover quantum interactive proof systems are given. First, we prove that there exists a one-round two-prover quantum interactive proof system for which no finite amount of shared entanglement allows the provers to implement an optimal strategy. More specifically, for every fixed input string, there exists a sequence of strategies for the provers, with each strategy requiring more entanglement than the last, for which the probability for the provers to convince the verifier to accept approaches one. It is not possible, however, for the provers to convince the verifier to accept with certainty with a finite amount of shared entanglement. The second application is a simple proof that multi-prover quantum interactive proofs can be transformed to have near-perfect completeness by the addition of one round of communication.

Obtaining a non-trivial (super-linear) lower bound for computation of the Fourier transform in the linear circuit model has been a long standing open problem. All lower bounds so far have made strong restrictions on the computational model. One of the best known results, by Morgenstern from 1973, provides an $\Omega(n \log n)$ lower bound for the unnormalized FFT when the constants used in the computation are bounded. The proof uses a potential function related to a determinant. The determinant of the unnormalized Fourier transform is $n^{n/2}$, and thus by showing that it can grow by at most a constant factor after each step yields the result. This classic result, however, does not explain why the normalized Fourier transform, which has a unit determinant, should take $\Omega(n\log n)$ steps to compute. In this work we show that in a layered linear circuit model restricted to unitary $2\times 2$ gates, one obtains an $\Omega(n\log n)$ lower bound. The well known FFT works in this model. The main conclusion from this work is that a potential function that might eventually help proving the $\Omega(n\log n)$ conjectured lower bound for computation of Fourier transform is not related to matrix determinant, but rather to a notion of matrix entropy.

Consider the following problem. A seller has infinite copies of $n$ products represented by nodes in a graph. There are $m$ consumers, each has a budget and wants to buy two products. Consumers are represented by weighted edges. Given the prices of products, each consumer will buy both products she wants, at the given price, if she can afford to. Our objective is to help the seller price the products to maximize her profit.

This problem is called graph vertex pricing (GVP) problem and has resisted several recent attempts despite its current simple solution. This motivates the study of this problem on special classes of graphs. In this paper, we study this problem on a large class of graphs such as graphs with bounded treewidth, bounded genus and $k$-partite graphs.

We show that there exists an FPTAS for GVP on graphs with bounded treewidth. This result is also extended to an FPTAS for the more general single-minded pricing problem. On bounded genus graphs we present a PTAS and show that GVP is NP-hard even on planar graphs.

We study the Sherali-Adams hierarchy applied to a natural Integer Program formulation that $(1+\epsilon)$-approximates the optimal solution of GVP. Sherali-Adams hierarchy has gained much interest recently as a possible approach to develop new approximation algorithms. We show that, when the input graph has bounded treewidth or bounded genus, applying a constant number of rounds of Sherali-Adams hierarchy makes the integrality gap of this natural LP arbitrarily small, thus giving a $(1+\epsilon)$-approximate solution to the original GVP instance.

On $k$-partite graphs, we present a constant-factor approximation algorithm. We further improve the approximation factors for paths, cycles and graphs with degree at most three.

Let $f:\{-1,1\}^n \to$ R be a real function on the hypercube, given by its discrete Fourier expansion, or, equivalently, represented as a multilinear polynomial. We say that it is Boolean if its image is in $\{-1,1\}$.

We show that every function on the hypercube with a sparse Fourier expansion must either be Boolean or far from Boolean. In particular, we show that a multilinear polynomial with at most $k$ terms must either be Boolean, or output values different than $-1$ or $1$ for a fraction of at least $2/(k+2)^2$ of its domain.

It follows that given oracle access to $f$, together with the guarantee that its representation as a multilinear polynomial has at most $k$ terms, one can test Booleanity using $O(k^2)$ queries. We show an $\Omega(k)$ queries lower bound for this problem.

Our proof crucially uses Hirschman's entropic version of Heisenberg's uncertainty principle.