We show that Reed-Solomon codes of dimension k and block length n over any finite field F can be deterministically list decoded from agreement √(k−1)n in time poly(n, log|F|).

Online bipartite matching is a classical problem in online algorithms and we know that both the deterministic fractional and randomized integral online matchings achieve the same competitive ratio of 1-1/e. In this work, we study classes of graphs where the online degree is restricted to 2. As expected, one can achieve a competitive ratio of better than 1-1/e in both the deterministic fractional and randomized integral cases, but surprisingly, these ratios are not the same. It was already known that for fractional matching, a 0.75 competitive ratio algorithm is optimal. We show that the folklore Half-Half algorithm achieves a competitive ratio of η ≈ 0.717772… and more surprisingly, show that this is optimal by giving a matching lower-bound. This yields a separation between the two problems: deterministic fractional and randomized integral, showing that it is impossible to obtain a perfect rounding scheme.

Abstract. Agreement tests are a generalization of low degree tests that capture a local-to-global phenomenon, which forms the combinatorial backbone of most probabilistically checkable proof (PCP) constructions. In an agreement test, a function is given by an ensemble of local restrictions. The agreement test checks that the restrictions agree when they overlap, and the main question is whether average agreement of the local pieces implies that there exists a global function that agrees with most local restrictions. There are very few structures that support agreement tests, essentially either coming from algebraic low degree tests or from direct product tests (and recently also from high-dimensional expanders). In this work, we prove a new agreement theorem which extends direct product tests to higher dimensions, analogously to how low degree tests extend linearity testing. As a corollary of our main theorem, it follows that an ensemble of small graphs on overlapping sets of vertices can be glued together to one global graph assuming they agree with each other on average. We prove the agreement theorem by (re)proving the agreement theorem for dimension 1, and then generalizing it to higher dimensions (with the dimension 1 case being the direct product test and dimension 2 being the graph case). A key technical step in our proof is the reverse union bound, which allows us to treat dependent events as if they are disjoint, and may be of independent interest. An added benefit of the reverse union bound is that it can be used to show that the “majority decoded” function also serves as a global function that explains the local consistency of the agreement theorem, a fact that was not known even in the direct product setting (dimension 1) prior to our work. Beyond the motivation to understand fundamental local-to-global structures, our main theorem allows us to lift structure theorems from the standard uniform distribution [Formula: see text] to the [Formula: see text]-biased distribution [Formula: see text]. As a simple demonstration of this paradigm, we show how the low degree testing result of Alon et al. [ IEEE Trans. Inform. Theory, 51 (2005), pp. 4032–4039,] and Bhattacharyya et al. [ Proc. 51 st FOCS, IEEE, 2010, pp. 488–497], originally proved for [Formula: see text], can be extended to the [Formula: see text]-biased hypercube [Formula: see text], even for very small subconstant [Formula: see text].

A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement$\boldsymbol{x}$and the proof$\boldsymbol{\pi}$are vectors over a finite field$\mathbb{F}$, and the proof is verified by making a single dot-product query$\langle \boldsymbol{q}, (\boldsymbol{x}\Vert\boldsymbol{\pi})\rangle$jointly to$\boldsymbol{x}$and$\boldsymbol{\pi}$. A DPP can be viewed as a 1-query fully linear PCP. We study the feasibility and efficiency of D PPs, obtaining the following results: •Small-field DPP. For any finite field$\mathbb{F}$and Boolean circuit$C$of size$S$, there is a D PP for proving that there exists$\boldsymbol{w}$such that$C(\boldsymbol{x},\ \boldsymbol{w})=1$with a proof$\boldsymbol{\pi}$of length$S\cdot \text{poly}(\vert \mathbb{F}\vert)$and soundness error$\varepsilon=O(1/\sqrt{\vert \mathbb{F}\vert })$. We show this error to be asymptotically optimal. In particular, and in contrast to the best known PCPs, there exist strictly linear-length DPPs over constant-size fields. •Large-field DPP. If$\vert \mathbb{F}\vert\geq$poly$(S/\varepsilon)$, there is a similar DPP with soundness error$\varepsilon$and proof length$O(S)$(in field elements). The above results do not rely on the PCP theorem and their proofs are considerably simpler. We apply our DPP constructions toward two kinds of applications. •Hardness of approximation. We obtain a simple proof for the NP-hardness of approximating MAXLIN (with dense instances) over any finite field$\mathbb{F}$up to some constant factor$c > 1$, independent of F. Unlike previous PCP-based proofs, our proof yields exponential-time hardness under the exponential time hypothesis (ETH). •Succinct arguments. We improve the concrete efficiency of succinct interactive arguments in the generic group model using input-independent preprocessing. In particular, the communication is comparable to sending two group elements and the verifier's computation is dominated by a single group exponentiation. We also show how to use DPPs together with linear-only encryption to construct succinct commit-and-prove arguments.

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in$\tilde{O}(n)$time. Univariate multiplicity codes and FRS codes are natural variants of Reed-Solomon codes that were discovered and studied for their applications to list decoding. It is known that for every$\varepsilon > 0$, and rate$r\in(0,1)$, there exist explicit families of these codes that have rate$r$and can be list decoded from a$(1-r-\varepsilon)$fraction of errors with constant list size in polynomial time (Guruswami & Wang (IEEE Trans. Inform. Theory 2013) and Kopparty, Ron-Zewi, Saraf & Wootters (SIAM J. Comput. 2023)). In this work, we present randomized algorithms that perform the above list-decoding tasks in$\tilde{O}(n)$, where$n$is the block-length of the code. Our algorithms have two main components. The first component builds upon the lattice-based approach of Alekhnovich (IEEE Trans. Inf. Theory 2005), who designed a$\tilde{O}(n)$time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design$\tilde{O}(n)$time algorithms for two natural algebraic problems: given a$(m+2)$-variate polynomial$Q(x, y_{0}, \ldots, y_{m})=\tilde{Q}(x)+\sum\nolimits_{i=0}^{m} Q_{i}(x) \cdot y_{i}$the first algorithm solves order-m linear differential equations of the form$Q\left(x, f(x), \frac{d f}{d x}, \ldots, \frac{d^{m} f}{d x^{m}}\right) \equiv 0$while the second solves functional equations of the form$Q(x, f(x), f(\gamma x), \ldots, f(\gamma^{m}x))\equiv 0$, where$m$is an arbitrary constant and$\gamma$is a field element of sufficiently high order. These algorithms can be viewed as generalizations of classical$\tilde{O}(n)$time algorithms of Sieveking (Computing 1972) and Kung (Numer. Math. 1974) for computing the modular inverse of a power series, and might be of independent interest.

We prove that the most natural low-degree test for polynomials over finite fields is “robust” in the high-error regime for linear-sized fields. Specifically we consider the “local” agreement of a function$f:\mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$from the space of degree-d polynomials, i.e., the expected agreement of the function from univariate degree-d polynomials over a randomly chosen line in$\mathbb{F}_{q}^{m}$, and prove that if this local agreement is$\varepsilon\geq\Omega((d/q)^{\tau}))$for some fixed$\tau > 0$, then there is a global degree-d polynomial$Q:\mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$with agreement nearly$\varepsilon$with$f$. This settles a long-standing open question in the area of low-degree testing, yielding an$O(d)$-query robust test in the “high-error” regime (i.e., when$\varepsilon < 1/2)$. The previous results in this space either required$\varepsilon > 1/2$(Polishchuk & Spielman, STOC 1994), or$q=\Omega(d^{4})$(Arora & Sudan, Combinatorica 2003), orneeded to measure local distance on 2-dimensional “planes” rather than one-dimensional lines leading to$\Omega(d^{2})$-query complexity (Raz & Safra, STOC 1997). Our analysis follows the spirit of most previous analyses in first analyzing the low-variable case$(m=O(1))$and then “boot-strapping” to general multivariate settings. Our main technical novelty is a new analysis in the bivariate setting that exploits a previously known connection between multivariate factorization and finding (or testing) low-degree polynomials, in a non “black-box” manner. This connection was used roughly in a black-box manner in the work of Arora & Sudan — and we show that opening up this black box and making some delicate choices in the analysis leads to our essentially optimal analysis. A second contribution is a bootstrapping analysis which manages to lift analyses for$m=2$directly to analyses for general$m$, where previous works needed to work with$m=3$or$m=4$— arguably this bootstrapping is significantly simpler than those in prior works.

Abstract. We introduce a variant of Probabilistically Checkable Proofs (PCPs) that we refer to as rectangular PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned into two disjoint sets, one determining the row of each query and the other determining the column. We construct PCPs that are efficient, short, smooth, and (almost) rectangular. As a key application, we show that proofs for hard languages in NTIME[Formula: see text], when viewed as matrices, are rigid infinitely often. This strengthens and simplifies a recent result of Alman and Chen [ FOCS, 2019] constructing explicit rigid matrices in FNP. Namely, we prove the following theorem: There is a constant [Formula: see text] such that there is an FNP-machine that, for infinitely many [Formula: see text], on input [Formula: see text] outputs [Formula: see text] matrices with entries in [Formula: see text] that are [Formula: see text]-far (in Hamming distance) from matrices of rank at most [Formula: see text]. Our construction of rectangular PCPs starts with an analysis of how randomness yields queries in the Reed–Muller-based outer PCP of Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan [ SIAM J. Comput., 36 (2006), pp. 889–974; CCC, 2005]. We then show how to preserve rectangularity under PCP composition and a smoothness-inducing transformation. This warrants refined and stronger notions of rectangularity, which we prove for the outer PCP and its transforms.

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of zeroes of a multivariate polynomial on a product set. This lemma motivates the multiplicity codes of Kopparty, Saraf and Yekhanin [J. ACM, 2014], who showed how to use this lemma to construct high-rate locally-decodable codes. However, the algorithmic results about these codes crucially rely on the fact that the polynomials are evaluated on a vector space and not an arbitrary product set. In this work, we show how to decode multivariate multiplicity codes of large multiplicities in polynomial time over finite product sets (over fields of large characteristic and zero characteristic). Previously such decoding algorithms were not known even for a positive fraction of errors. In contrast, our work goes all the way to the distance of the code and in particular exceeds both the unique-decoding bound and the Johnson radius. For errors exceeding the Johnson radius, even combinatorial list-decodablity of these codes was not known. Our algorithm is an application of the classical polynomial method directly to the multivariate setting. In particular, we do not rely on a reduction from the multivariate to the univariate case as is typical of many of the existing results on decoding codes based on multivariate polynomials. However, a vanilla application of the polynomial method in the multivariate setting does not yield a polynomial upper bound on the list size. We obtain a polynomial bound on the list size by taking an alternative view of multivariate multiplicity codes. In this view, we glue all the partial derivatives of the same order together using a fresh set$\mathbf {z}$of variables. We then apply the polynomial method by viewing this as a problem over the field$\mathbb {F} (\mathbf {z})$of rational functions in$\mathbf {z}$.

In this work, we present an abstract framework for some algebraic error-correcting codes with the aim of capturing codes that are list-decodable to capacity, along with their decoding algorithms. In the polynomial ideal framework, a code is specified by some ideals in a polynomial ring, messages are polynomials and the encoding of a message polynomial is the collection of residues of that polynomial modulo the ideals. We present an alternate way of viewing this class of codes in terms of linear operators, and show that this alternate view makes their algorithmic list-decodability amenable to analysis. Our framework leads to a new class of codes that we call affine Folded Reed-Solomon codes (which are themselves a special case of the broader class we explore). These codes are common generalizations of the well-studied Folded Reed-Solomon codes and Univariate Multiplicity codes as well as the less-studied Additive Folded Reed-Solomon codes, and lead to a large family of codes that were not previously known/studied. More significantly our framework also captures the algorithmic list-decodability of the constituent codes. Specifically, we present a unified view of the decoding algorithm for ideal-theoretic codes and show that the decodability reduces to the analysis of the distance of some related codes. We show that a good bound on this distance leads to a capacity-achieving performance of the underlying code, providing a unifying explanation of known capacity-achieving results. In the specific case of affine Folded Reed-Solomon codes, our framework shows that they are efficiently list-decodable up to capacity (for appropriate setting of the parameters), thereby unifying the previous results for Folded Reed-Solomon, Multiplicity and Additive Folded Reed-Solomon codes.

Rossman [In $\textit{Proc. $34$th Comput. Complexity Conf.}$, 2019] introduced the notion of $\textit{criticality}$. The criticality of a Boolean function $f : \{0,1\}^n \to \{0,1\}$ is the minimum $λ\geq 1$ such that for all positive integers $t$, \[ \Pr_{ρ\sim \mathcal{R}_p}\left[\text{DT}_{\text{depth}}(f|_ρ) \geq t\right] \leq (pλ)^t. \] Hästad's celebrated switching lemma shows that the criticality of any $k$-DNF is at most $O(k)$. Subsequent improvements to correlation bounds of $\text{AC}^0$-circuits against parity showed that the criticality of any $\text{AC}^0$-$\textit{circuit}$ of size $S$ and depth $d+1$ is at most $O(\log S)^d$ and any $\textit{regular}$ $\text{AC}^0$-$\textit{formula}$ of size $S$ and depth $d+1$ is at most $O\left(\frac1d \cdot \log S\right)^d$. We strengthen these results by showing that the criticality of $\textit{any}$ $\text{AC}^0$-formula (not necessarily regular) of size $S$ and depth $d+1$ is at most $O\left(\frac1d\cdot {\log S}\right)^d$, resolving a conjecture due to Rossman. This result also implies Rossman's optimal lower bound on the size of any depth-$d$ $\text{AC}^0$-formula computing parity [$\textit{Comput. Complexity, 27(2):209--223, 2018.}$]. Our result implies tight correlation bounds against parity, tight Fourier concentration results and improved $\#$SAT algorithm for $\text{AC}^0$-formulae.

We design nearly-linear time numerical algorithms for the problem of multivariate multipoint evaluation over the fields of rational, real and complex numbers. We consider both exact and approximate versions of the algorithm. The input to the algorithms are (1) coefficients of an m-variate polynomial f with degree d in each variable, and (2) points $\mathbf{a}_{1}, \ldots, \mathbf{a}_{N}$ each of whose coordinate has absolute value bounded by one. Approximate version: Given additionally an accuracy parameter t, the algorithm computes rational numbers $\beta_{1}, \ldots, \beta_{N}$ such that $\left|f\left(\mathbf{a}_{i}\right)-\beta_{i}\right| \leq 1 / 2^{t}$ for all i, and has a running time of $\left(\left(N m+d^{m}\right) t\right)^{1+o(1)}$ for all m and all sufficiently large d. Exact version (when over rationals): Given additionally a bound s on the bit-complexity of all the rational numbers in the input and output, the algorithm computes the rational numbers $f\left(\mathbf{a}_{1}\right), \ldots, f\left(\mathbf{a}_{N}\right)$, in time $\left(\left(N m+d^{m}\right) s\right)^{1+o(1)}$ for all m and all sufficiently large d. Our results also naturally extend to the case when the input is over the field of real or complex numbers under an appropriate standard model of representation of field elements in such fields.Prior to this work, a nearly-linear time algorithm for multivariate multipoint evaluation (exact or approximate) over any infinite field appears to be known only for the case of univariate polynomials, and was discovered in a recent work of Moroz [Proc. 62nd FOCS, 2021]. In this work, we extend this result from the univariate to the multivariate setting. However, our algorithm is based on ideas that seem to be conceptually different from those of Moroz [Proc. 62nd FOCS, 2021] and crucially relies on a recent algorithm of Bhargava, Ghosh, Guo, Kumar & Umans [Proc. 63rd FOCS, 2022] for multivariate multipoint evaluation over finite fields, and known efficient algorithms for the problems of rational number reconstruction and fast Chinese remaindering in computational number theory.

A problem is \emph{downward self-reducible} if it can be solved efficiently given an oracle that returns solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is well studied and it is known that all downward self-reducible problems are in \textsc{PSPACE}. In this paper, we initiate the study of downward self-reducible search problems which are guaranteed to have a solution -- that is, the downward self-reducible problems in \textsc{TFNP}. We show that most natural $\PLS$-complete problems are downward self-reducible and any downward self-reducible problem in \textsc{TFNP} is contained in \textsc{PLS}. Furthermore, if the downward self-reducible problem is in \textsc{TFUP} (i.e. it has a unique solution), then it is actually contained in \textsc{UEOPL}, a subclass of \textsc{CLS}. This implies that if integer factoring is \emph{downward self-reducible} then it is in fact in \textsc{UEOPL}, suggesting that no efficient factoring algorithm exists using the factorization of smaller numbers.

The multiplicity Schwartz-Zippel lemma asserts that over a field, a low-degree polynomial cannot vanish with high multiplicity very often on a sufficiently large product set. Since its discovery in a work of Dvir, Kopparty, Saraf and Sudan [DKSS13], the lemma has found numerous applications in both math and computer science; in particular, in the definition and properties of multiplicity codes by Kopparty, Saraf and Yekhanin [KSY14]. In this work, we show how to algorithmize the multiplicity Schwartz-Zippel lemma for arbitrary product sets over any field. In other words, we give an efficient algorithm for unique decoding of multivariate multiplicity codes from half their minimum distance on arbitrary product sets over all fields. Previously, such an algorithm was known either when the underlying product set had a nice algebraic structure (for instance, was a subfield) [Kop15] or when the underlying field had large (or zero) characteristic, the multiplicity parameter was sufficiently large and the multiplicity code had distance bounded away from 1 [BHKS21b]. In particular, even unique decoding of bivariate multiplicity codes with multiplicity two from half their minimum distance was not known over arbitrary product sets over any field. Our algorithm builds upon a result of Kim & Kopparty [KK17] who gave an algorithmic version of the Schwartz-Zippel lemma (without multiplicities) or equivalently, an efficient algorithm for unique decoding of Reed-Muller codes over arbitrary product sets. We introduce a refined notion of distance based on the multiplicity Schwartz-Zippel lemma and design a unique decoding algorithm for this distance measure. On the way, we give an alternate analysis of Forney's classical generalized minimum distance decoder that might be of independent interest. * The full version of the paper which includes the missing proofs can be accessed at [BHKS21a]. Research of the first, second and fourth authors supported by the Department of Atomic Energy, Government of India, under project 12-R&D-TFR-5.01-0500. This work was done while the first author was at TIFR, where he was supported in part by the Google PhD Fellowship and at the Simons Institute for the Theory of Computing where he was supported by the Simons-Berkeley Postdoctoral Fellowship. Research of the second author supported in part by the Swarnajayanti Fellowship.

We study the following natural question on random sets of points in 𝔽₂^m: Given a random set of k points Z = {z₁, z₂, … , z_k} ⊆ 𝔽₂^m, what is the dimension of the space of degree at most r multilinear polynomials that vanish on all points in Z? We show that, for r ≤ γ m (where γ > 0 is a small, absolute constant) and k = (1-ε)⋅binom(m, ≤ r) for any constant ε > 0, the space of degree at most r multilinear polynomials vanishing on a random set Z = {z_1,…, z_k} has dimension exactly binom(m, ≤ r) - k with probability 1 - o(1). This bound shows that random sets have a much smaller space of degree at most r multilinear polynomials vanishing on them, compared to the worst-case bound (due to Wei (IEEE Trans. Inform. Theory, 1991)) of binom(m, ≤ r) - binom(log₂ k, ≤ r) ≫ binom(m, ≤ r) - k. Using this bound, we show that high-degree Reed-Muller codes (RM(m,d) with d > (1-γ) m) "achieve capacity" under the Binary Erasure Channel in the sense that, for any ε > 0, we can recover from (1-ε)⋅binom(m, ≤ m-d-1) random erasures with probability 1 - o(1). This also implies that RM(m,d) is also efficiently decodable from ≈ binom(m, ≤ m-(d/2)) random errors for the same range of parameters.

In this paper, we show the mixing of three-term progressions (x, xg, xg²) in every finite quasirandom group, fully answering a question of Gowers. More precisely, we show that for any D-quasirandom group G and any three sets A₁, A₂, A₃ ⊂ G, we have |Pr_{x,y∼ G}[x ∈ A₁, xy ∈ A₂, xy² ∈ A₃] - ∏_{i = 1}³ Pr_{x∼ G}[x ∈ A_i]| ≤ (2/(√{D)})^{1/4}. Prior to this, Tao answered this question when the underlying quasirandom group is SL_{d}(𝔽_q). Subsequently, Peluse extended the result to all non-abelian finite simple groups. In this work, we show that a slight modification of Peluse’s argument is sufficient to fully resolve Gowers' quasirandom conjecture for 3-term progressions. Surprisingly, unlike the proofs of Tao and Peluse, our proof is elementary and only uses basic facts from non-abelian Fourier analysis.

In this work, we present an abstract framework for some algebraic error-correcting codes with the aim of capturing codes that are list-decodable to capacity, along with their decoding algorithm. In the polynomial ideal framework, a code is specified by some ideals in a polynomial ring, messages are polynomials and their encoding is the residue modulo the ideals. We present an alternate way of viewing this class of codes in terms of linear operators, and show that this alternate view makes their algorithmic list-decodability amenable to analysis. Our framework leads to a new class of codes that we call affine Folded Reed-Solomon codes (which are themselves a special case of the broader class we explore). These codes are common generalizations of the well-studied Folded Reed-Solomon codes and Multiplicity codes, while also capturing the less-studied Additive Folded Reed-Solomon codes as well as a large family of codes that were not previously known/studied. More significantly our framework also captures the algorithmic list-decodability of the constituent codes. Specifically, we present a unified view of the decoding algorithm for ideal theoretic codes and show that the decodability reduces to the analysis of the distance of some related codes. We show that good bounds on this distance lead to capacity-achieving performance of the underlying code, providing a unifying explanation of known capacity-achieving results. In the specific case of affine Folded Reed-Solomon codes, our framework shows that they are list-decodable up to capacity (for appropriate setting of the parameters), thereby unifying the previous results for Folded Reed-Solomon, Multiplicity and Additive Folded Reed-Solomon codes.

We construct an explicit family of 3XOR instances which is hard for $O(\sqrt{\log n})$ levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems can be constructed explicitly in deterministic polynomial time. Our construction is based on the high-dimensional expanders devised by Lubotzky, Samuels and Vishne, known as LSV complexes or Ramanujan complexes, and our analysis is based on two notions of expansion for these complexes: cosystolic expansion, and a local isoperimetric inequality due to Gromov. Our construction offers an interesting contrast to the recent work of Alev, Jeronimo and the last author~(FOCS 2019). They showed that 3XOR instances in which the variables correspond to vertices in a high-dimensional expander are easy to solve. In contrast, in our instances the variables correspond to the edges of the complex.

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of zeroes of a multivariate polynomial on a product set. This lemma motivates the multiplicity codes of Kopparty, Saraf and Yekhanin [J. ACM, 2014], who showed how to use this lemma to construct high-rate locally-decodable codes. However, the algorithmic results about these codes crucially rely on the fact that the polynomials are evaluated on a vector space and not an arbitrary product set.

We strengthen the notion of double samplers, first introduced by Dinur and Kaufman [``High dimensional expanders imply agreement expanders,” in Proc. 58th IEEE Symp. on Foundations of Comp. Science, IEEE, 2017, pp. 974--985], which are samplers with additional combinatorial properties, and whose existence we prove using high-dimensional expanders. The ABNNR code construction [N. Alon et al., IEEE Trans. Inform. Theory, 38 (1992), pp. 509--516] achieves large distance by starting with a base code $C$ with moderate distance, and then amplifying the distance using a sampler. We show that if the sampler is part of a larger double sampler, then the construction has an efficient list-decoding algorithm. Our algorithm works even if the ABNNR construction is not applied to a base code $C$ but rather to any string. In this case the resulting code is approximate-list-decodable, i.e., the output list contains an approximation to the original input. Our list-decoding algorithm works as follows: It uses a local voting scheme from which it constructs a unique games constraint graph. The constraint graph is an expander, so we can solve unique games efficiently. These solutions are the output of the list-decoder. This is a novel use of a unique games algorithm as a subroutine in a decoding procedure, as opposed to the more common situation in which unique games are used for demonstrating hardness results. Double samplers and high-dimensional expanders are akin to pseudorandom objects in their utility, but they greatly exceed random objects in their combinatorial properties. We believe that these objects hold significant potential for coding theoretic constructions and view this work as demonstrating the power of double samplers in this context.

In this work, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over F₂. We show the following results for multilinear forms and tensors. Correlation bounds. We show that a random d-linear form has exponentially low correlation with low-degree polynomials. More precisely, for d = 2^{o(k)}, we show that a random d-linear form f(X₁,X₂, … , X_d) : (F₂^{k}) ^d → F₂ has correlation 2^{-k(1-o(1))} with any polynomial of degree at most d/2 with high probability. This result is proved by giving near-optimal bounds on the bias of a random d-linear form, which is in turn proved by giving near-optimal bounds on the probability that a sum of t random d-dimensional rank-1 tensors is identically zero. Tensor rank vs Bias. We show that if a 3-dimensional tensor has small rank then its bias, when viewed as a 3-linear form, is large. More precisely, given any 3-dimensional tensor T: [k]³ → F₂ of rank at most t, the bias of the 3-linear form f_T(X₁, X₂, X₃) : = ∑_{(i₁, i₂, i₃) ∈ [k]³} T(i₁, i₂, i₃)⋅ X_{1,i₁}⋅ X_{2,i₂}⋅ X_{3,i₃} is at least (3/4)^t. This bias vs tensor-rank connection suggests a natural approach to proving nontrivial tensor-rank lower bounds. In particular, we use this approach to give a new proof that the finite field multiplication tensor has tensor rank at least 3.52 k, which is the best known rank lower bound for any explicit tensor in three dimensions over F₂. Moreover, this relation between bias and tensor rank holds for d-dimensional tensors for any fixed d.

We introduce a variant of PCPs, that we refer to as rectangular PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned into two disjoint sets, one determining the row of each query and the other determining the column. We construct PCPs that are efficient, short, smooth and (almost-)rectangular. As a key application, we show that proofs for hard languages in NTIME(2n), when viewed as matrices, are rigid infinitely often. This strengthens and simplifies a recent result of Alman and Chen [FOCS, 2019] constructing explicit rigid matrices in FNP. Namely, we prove the following theorem: : There is a constant δ ∈ (0,1) such that there is an FNP-machine that, for infinitely many N, on input 1Noutputs N×N matrices with entries in F2that are δN2-far (in Hamming distance) from matrices of rank at most 2logN/Ω(loglogN). Our construction of rectangular PCPs starts with an analysis of how randomness yields queries in the Reed-Muller-based outer PCP of Ben-Sasson, Goldreich, Harsha, Sudan and Vadhan [SICOMP, 2006; CCC, 2005]. We then show how to preserve rectangularity under PCP composition and a smoothness-inducing transformation. This warrants refined and stronger notions of rectangularity, which we prove for the outer PCP and its transforms.

We prove that for every constant c and epsilon = (log n)^{-c}, there is no polynomial time algorithm that when given an instance of 3-LIN with n variables where an (1 - epsilon)-fraction of the clauses are satisfiable, finds an assignment that satisfies atleast (1/2 + epsilon)-fraction of clauses unless NP subseteq BPP. The previous best hardness using a polynomial time reduction achieves epsilon = (log log n)^{-c}, which is obtained by the Label Cover hardness of Moshkovitz and Raz [J. ACM, 57(5), 2010] followed by the reduction from Label Cover to 3-LIN of Håstad [J. ACM, 48(4):798 - 859, 2001]. Our main idea is to prove a hardness result for Label Cover similar to Moshkovitz and Raz where each projection has a linear structure. This linear structure of Label Cover allows us to use Hadamard codes instead of long codes, making the reduction more efficient. For the hardness of Linear Label Cover, we follow the work of Dinur and Harsha [SIAM J. Comput., 42(6):2452 - 2486, 2013] that simplified the construction of Moshkovitz and Raz, and observe that running their reduction from a hardness of the problem LIN (of unbounded arity) instead of the more standard problem of solving quadratic equations ensures the linearity of the resultant Label Cover.

A local tester for an error-correcting code is a probabilistic procedure that queries a small subset of coordinates, accepts codewords with probability one, and rejects non-codewords with probability proportional to their distance from the code. The local tester is robust if for non-codewords it satisfies the stronger property that the average distance of local views from accepting views is proportional to the distance from the code. Robust testing is an important component in constructions of locally testable codes and probabilistically checkable proofs as it allows for composition of local tests. In this work we show that for certain codes, any (natural) local tester can be converted to a roubst tester with roughly the same number of queries. Our result holds for the class of affine-invariant lifted codes which is a broad class of codes that includes Reed-Muller codes, as well as recent constructions of high-rate locally testable codes (Guo, Kopparty, and Sudan, ITCS 2013). Instantiating this with known local testing results for lifted codes gives a more direct proof that improves some of the parameters of the main result of Guo, Haramaty, and Sudan (FOCS 2015), showing robustness of lifted codes. To obtain the above transformation we relate the notions of local testing and robust testing to the notion of agreement testing that attempts to find out whether valid partial assignments can be stitched together to a global codeword. We first show that agreement testing implies robust testing, and then show that local testing implies agreement testing. Our proof is combinatorial, and is based on expansion / sampling properties of the collection of local views of local testers. Thus, it immediately applies to local testers of lifted codes that query random affine subspaces in F_q^m, and moreover seems amenable to extension to other families of locally testable codes with expanding families of local views.

We propose a new paradigm for studying the structure of Boolean functions on the biased Boolean hypercube, i.e. when the measure is µp and p is potentially very small, e.g. as small as O(1/n). Our paradigm is based on the following simple fact: the p-biased hypercube is expressible as a convex combination of many small-dimensional copies of the uniform hypercube. To uncover structure for µp, we invoke known structure theorems for µ1/2, obtaining a structured approximation for each copy separately. We then sew these approximations together using a novel “agreement theorem”. This strategy allows us to lift structure theorems from µ1/2 to µp. We provide two applications of this paradigm: Our main application is a structure theorem for functions that are nearly low degree in the Fourier sense. The structure we uncover in the biased hypercube is not at all the same as for the uniform hypercube, despite using the structure theorem for the uniform hypercube as a black box. Rather, new phenomena emerge: whereas nearly low degree functions on the uniform hypercube are close to juntas, when p becomes small, non-juntas arise as well. For example, the function max(y1, · · ·, yε/p) (where yi ∊ {0, 1}) is nearly degree 1 despite not being close to any junta. A second (technically simpler) application is a test for being low degree in the GF(2) sense, in the setting of the biased hypercube. In both cases, we use as a black box the corresponding result for p = 1/2. In the first case, it is the junta theorem of Kindler and Safra, and in the second case, the low degree testing theorem of Alon et al. [IEEE Trans. Inform. Theory, 2005] and Bhattacharyya et al. [Proc. 51st FOCS, 2010]. A key component of our proof is a new local-to-global agreement theorem for higher dimensions, which extends the work of Dinur and Steurer [Proc. 29th CCC, 2014]. Whereas their result sews together vectors, our agreement theorem sews together labeled graphs and hypergraphs. The proof of our agreement theorem uses a novel pruning lemma for hypergraphs, which may be of independent interest. The pruning lemma trims a given hypergraph so that the number of hyperedges in a random induced subhypergraph has roughly a Poisson distribution, while maintaining the expected number of hyperedges.

We develop the notion of double samplers, first introduced by Dinur and Kaufman [DK17], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders. We show how double samplers give a generic way of amplifying distance in a way that enables efficient list-decoding. There are many error correcting code constructions that achieve large distance by starting with a base code C with moderate distance, and then amplifying the distance using a sampler, e.g., the ABNNR code construction [ABN+ 92] is such. We show that if the sampler is part of a larger double sampler then the construction has an efficient list-decoding algorithm and the list decoding algorithm is oblivious to the base code C (i.e., it runs the unique decoder for C in a black box way). Our list-decoding algorithm works as follows: it uses a local voting scheme from which it constructs a unique games constraint graph. The constraint graph is an expander, so we can solve unique games efficiently. These solutions are the output of the list decoder. This is a novel use of a unique games algorithm as a subroutine in a decoding procedure, as opposed to the more common situation in which unique games are used for demonstrating hardness results. Double samplers and high dimensional expanders are akin to pseudorandom objects in their utility, but they greatly exceed random objects in their combinatorial properties. We believe that these objects hold significant potential for coding theoretic constructions and view this work as demonstrating the power of double samplers in this context.

We consider the following multiplication-based tests to check if a given function f : Fqn→ Fqis a codeword of the Reed-Muller code of dimension n and order d over the finite field Fqfor prime q (i.e., f is the evaluation of a degree-d polynomial over Fq for q prime). Teste,k: pick P1,..., Pkindependent random degree-e polynomials and accept if the function f P1· · · Pkis the evaluation of a degree-(d + ek) polynomial (i.e., is a codeword of the Reed-Muller code of dimension n and order (d + ek)). We prove the robust soundness of the abovementioned tests for large values of e, answering a question of Dinur and Guruswami. Previous soundness analyses of these tests were known only for the case when either e = 1 or k = 1. Even for the case k = 1 and e > 1, earlier soundness analyses were not robust. We also analyze a derandomized version of this test, where (for example) the polynomials P1, ..., Pkcan be the same random polynomial P. This generalizes a result of Guruswami et al. One of the key ingredients that go into the proof of this robust soundness is an extension of the standard Schwartz-Zippel lemma over general finite fields Fq, which may be of independent interest.

We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders. Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse model for the Boolean slice or hypercube, and quite possibly additional results from Boolean function analysis can be carried over to this sparse model. Therefore, this model can be viewed as a derandomization of the Boolean slice, containing |X(k)|=O(n) points in comparison to binom{n}{k+1} points in the (k+1)-slice (which consists of all n-bit strings with exactly k+1 ones).

We investigate the value of parallel repetition of one-round games with any number of players k>=2. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games. Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are *connected* in a certain sense. We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.

In this paper we investigate the uniform distribution properties of polynomials in many variables and bounded degree over a fixed finite field F of prime order. Our main result is that a polynomial P : F^n -> F is poorly-distributed only if P is determined by the values of a few polynomials of lower degree, in which case we say that P has small rank. We give several applications of this result, paying particular attention to consequences for the theory of the so-called Gowers norms. We establish an inverse result for the Gowers U^{d+1}-norm of functions of the form f(x)= e_F(P(x)), where P : F^n -> F is a polynomial of degree less than F, showing that this norm can only be large if f correlates with e_F(Q(x)) for some polynomial Q : F^n -> F of degree at most d. The requirement deg(P) < |F| cannot be dropped entirely. Indeed, we show the above claim fails in characteristic 2 when d = 3 and deg(P)=4, showing that the quartic symmetric polynomial S_4 in F_2^n has large Gowers U^4-norm but does not correlate strongly with any cubic polynomial. This shows that the theory of Gowers norms in low characteristic is not as simple as previously supposed. This counterexample has also been discovered independently by Lovett, Meshulam, and Samorodnitsky. We conclude with sundry other applications of our main result, including a recurrence result and a certain type of nullstellensatz.

We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka the “short code” of Barak et al. [SIAM J. Comput., 44 (2015), pp. 1287--1324]) and the techniques proposed by Dinur and Guruswami [Israel J. Math., 209 (2015), pp. 611--649] to incorporate this code for inapproximability results. In particular, we prove quasi NP-hardness of the following problems on $n$-vertex hypergraphs: coloring a 2-colorable 8-uniform hypergraph with $2^{2^{\Omega(\sqrt{\log \log n})}}$ colors; coloring a 4-colorable 4-uniform hypergraph with $2^{2^{\Omega(\sqrt{\log \log n})}}$ colors; and coloring a 3-colorable 3-uniform hypergraph with $(\log n)^{\Omega(1/\log\log\log n)}$ colors. For the first two cases, the hardness results obtained are superpolynomial in what was previously known, and in the last case it is an exponential improvement. In fact, prior to this result, $(\log n)^{O(1)}$ colors was the strongest quantitative bound on the number of colors ruled out by inapproximability results for $O(1)$-colorable hypergraphs, and $(\log\log n)^{O(1)}$ for $O(1)$-colorable, 3-uniform hypergraphs.

We make progress on some questions related to polynomial approximations of AC^0. It is known, from the works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. 6th CCC 1991), that any AC^0 circuit of size s and depth d has an epsilon-error probabilistic polynomial over the reals of degree (log (s/epsilon))^{O(d)}. We improve this upper bound to (log s)^{O(d)}* log(1/epsilon), which is much better for small values of epsilon. We give an application of this result by using it to resolve a question posed by Tal (ECCC 2014): we show that (log s)^{O(d)}* log(1/epsilon)-wise independence fools AC^0, improving on Tal's strengthening of Braverman's theorem (J. ACM 2010) that (log (s/epsilon))^{O(d)}-wise independence fools AC^0. Up to the constant implicit in the O(d), our result is tight. As far as we know, this is the first PRG construction for AC^0 that achieves optimal dependence on the error epsilon. We also prove lower bounds on the best polynomial approximations to AC^0. We show that any polynomial approximating the OR function on n bits to a small constant error must have degree at least ~Omega(sqrt{log n}). This result improves exponentially on a recent lower bound demonstrated by Meka, Nguyen, and Vu (arXiv 2015).

Goemans showed that any n points x_1,..., x_n in d-dimensions satisfying l_2^2 triangle inequalities can be embedded into l_{1}, with worst-case distortion at most sqrt{d}. We consider an extension of this theorem to the case when the points are approximately low-dimensional as opposed to exactly low-dimensional, and prove the following analogous theorem, albeit with average distortion guarantees: There exists an l_{2}^{2}-to-l_{1} embedding with average distortion at most the stable rank, sr(M), of the matrix M consisting of columns {x_i-x_j}_{i

We consider the following multiplication-based tests to check if a given function f: F^n_q -> F_q is the evaluation of a degree-d polynomial over F_q for q prime. Test_{e,k}: Pick P_1,...,P_k independent random degree-e polynomials and accept iff the function f P_1 ... P_k is the evaluation of a degree-(d + ek) polynomial. We prove the robust soundness of the above tests for large values of e, answering a question of Dinur and Guruswami (FOCS 2013). Previous soundness analyses of these tests were known only for the case when either e = 1 or k = 1. Even for the case k = 1 and e > 1, earlier soundness analyses were not robust. We also analyze a derandomized version of this test, where (for example) the polynomials P_1 ,... , P_k can be the same random polynomial P. This generalizes a result of Guruswami et al. (STOC 2014). One of the key ingredients that go into the proof of this robust soundness is an extension of the standard Schwartz-Zippel lemma over general finite fields F_q, which may be of independent interest.

Let f: {0,1}^n*{0,1}^n -> {0,1} be a 2-party function. For every product distribution mu on {0,1}^n*{0,1}^n, we show that CC^{mu}_{0.49}(f) = O(log(prt_{1/8}(f))*log(log(prt_{1/8}(f)))^2), where CC^{mu}_{epsilon}(f) is the distributional communication complexity of f with error at most epsilon under the distribution mu and prt_{1/8}(f) is the partition bound of f, as defined by Jain and Klauck [Proc. 25th CCC, 2010]. We also prove a similar bound in terms of IC_{1/8}(f), the information complexity of f, namely, CC^{mu}_{0.49}(f) = O((IC_{1/8}(f)*log(IC_{1/8}(f)))^2). The latter bound was recently and independently established by Kol [Proc. 48th STOC, 2016] using a different technique. We show a similar result for query complexity under product distributions. Let g: {0,1}^n -> {0,1} be a function. For every bit-wise product distribution mu on {0,1}^n, we show that QC^{mu}_{0.49}(g) = O((log(qprt_{1/8}(g))*log(log(qprt_{1/8}(g))))^2), where QC^{mu}_{epsilon}(g) is the distributional query complexity of f with error at most epsilon under the distribution mu and qprt_{1/8}(g) is the query partition bound of the function g. Partition bounds were introduced (in both communication complexity and query complexity models) to provide LP-based lower bounds for randomized communication complexity and randomized query complexity. Our results demonstrate that these lower bounds are polynomially tight for product distributions.

In this paper, we address the question of whether the recent derandomization results obtained by the use of the low-degree long code can be extended to other product settings. We consider two settings: (1) the graph product results of Alon, Dinur, Friedgut and Sudakov [GAFA, 2004] and (2) the "majority is stablest" type of result obtained by Dinur, Mossel and Regev [SICOMP, 2009] and Dinur and Shinkar [In Proc. APPROX, 2010] while studying the hardness of approximate graph coloring. In our first result, we show that there exists a considerably smaller subgraph of $K_3^{\otimes R}$ which exhibits the following property (shown for $K_3^{\otimes R}$ by Alon et al.): independent sets close in size to the maximum independent set are well approximated by dictators. The "majority is stablest" type of result of Dinur et al. and Dinur and Shinkar shows that if there exist two sets of vertices $A$ and $B$ in $K_3^{\otimes R}$ with very few edges with one endpoint in $A$ and another in $B$, then it must be the case that the two sets $A$ and $B$ share a single influential coordinate. In our second result, we show that a similar "majority is stablest" statement holds good for a considerably smaller subgraph of $K_3^{\otimes R}$. Furthermore using this result, we give a more efficient reduction from Unique Games to the graph coloring problem, leading to improved hardness of approximation results for coloring.

We show that every language in NP has a PCP verifier that tosses O(log n) random coins, has perfect completeness, and a soundness error of at most 1/poly(n), while making O(poly log log n) queries into a proof over an alphabet of size at most n1/poly log log n. Previous constructions that obtain 1/poly(n) soundness error used either poly log n queries or an exponential alphabet, i.e. of size 2nc for some c> 0. Our result is an exponential improvement in both parameters simultaneously. Our result can be phrased as polynomial-gap hardness for approximate CSPs with arity poly log log n and alphabet size n1/poly log n. The ultimate goal, in this direction, would be to prove polynomial hardness for CSPs with constant arity and polynomial alphabet size (aka the sliding scale conjecture for inverse polynomial soundness error).

We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the"short code" of Barak et. al. [FOCS 2012]) and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results.

The main result of this paper is an optimal strong direct product result for the two-party public-coin randomized communication complexity of the Tribes function. This is proved by providing an alternate proof of the optimal lower bound of \Omega(n) for the randomised communication complexity of the Tribes function using the so-called smooth-rectangle bound, introduced by Jain and Klauck [JK10]. The optimal \Omega(n) lower bound for Tribes was originally proved by Jayram, Kumar and Sivakumar [JKS03], using a more powerful lower bound technique, namely the information complexity bound. The information complexity bound is known to be at least as strong a lower bound method as the smooth-rectangle bound [KLL+12]. On the other hand, we are not aware of any function or relation for which the smooth-rectangle bound is (asymptotically) smaller than its public-coin randomized communication complexity. The optimal direct product for Tribes is obtained by combining our smooth-rectangle bound for tribes with the strong direct product result of Jain and Yao [JY12] in terms of smooth-rectangle bound.

The main result of this paper is a generic composition theorem for low-error two-query probabilistically checkable proofs (PCPs). Prior to this work, composition of PCPs was well understood only in the constant error regime. Existing composition methods in the low-error regime were nonmodular (i.e., very much tailored to the specific PCPs that were being composed), resulting in complicated constructions of PCPs. Furthermore, until recently, composition in the low-error regime suffered from incurring an extra “consistency” query, resulting in PCPs that are not “two-query” and hence, much less useful for hardness-of-approximation reductions. In a recent breakthrough, Moshkovitz and Raz (Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (FOCS), 2008) [J. ACM, 57 (2010)] constructed almost linear-sized low-error 2-query PCPs for every language in NP. Indeed, the main technical component of their construction is a novel composition of certain specific PCPs. We generalize and abstract their composition method, thereby giving a modular and simpler proof of their result. To facilitate the modular composition, we introduce a new variant of PCP, which we call a decodable PCP (dPCP). A dPCP is an encoding of an NP witness that is both locally checkable and locally decodable. The dPCP verifier, in addition to verifying the validity of the given proof like a standard PCP verifier, also locally decodes the original NP witness. Our composition is generic in the sense that it works regardless of the way the component PCPs are constructed.

Let X be randomly chosen from {-1,1} n , and let Y be randomly chosen from the standard spherical Gaussian on ℝ n . For any (possibly unbounded) polytope P formed by the intersection of k halfspaces, we prove that |Pr[ X ∈ P ] - Pr[ Y ∈ P ]| ≤ log 8/5 k ⋅ Δ, where Δ is a parameter that is small for polytopes formed by the intersection of “regular” halfspaces (i.e., halfspaces with low influence). The novelty of our invariance principle is the polylogarithmic dependence on k . Previously, only bounds that were at least linear in k were known. The proof of the invariance principle is based on a generalization of the Lindeberg method for proving central limit theorems and could be of use elsewhere. We give two important applications of our invariance principle, one from learning theory and the other from pseudorandomness. (1) A bound of log O (1) k ⋅ ϵ 1/6 on the Boolean noise sensitivity of intersections of k “regular” halfspaces (previous work gave bounds linear in k ). This gives a corresponding agnostic learning algorithm for intersections of regular halfspaces. (2) A pseudorandom generator (PRG) for estimating the Gaussian volume of polytopes with k faces within error δ and seed-length O (log n poly(log k ,1/δ)). We also obtain PRGs with similar parameters that fool polytopes formed by intersection of regular halfspaces over the hypercube. Using our PRG constructions, we obtain the first deterministic quasi-polynomial time algorithms for approximately counting the number of solutions to a broad class of integer programs, including dense covering problems and contingency tables.

In this paper, we study the complexity of computing the determinant of a matrix over a non-commutative algebra. In particular, we ask the question, "over which algebras, is the determinant easier to compute than the permanent?" Towards resolving this question, we show the following hardness and easiness of noncommutative determinant computation. * [Hardness] Computing the determinant of an n \times n matrix whose entries are themselves 2 \times 2 matrices over a field is as hard as computing the permanent over the field. This extends the recent result of Arvind and Srinivasan, who proved a similar result which however required the entries to be of linear dimension. * [Easiness] Determinant of an n \times n matrix whose entries are themselves d \times d upper triangular matrices can be computed in poly(n^d) time. Combining the above with the decomposition theorem of finite dimensional algebras (in particular exploiting the simple structure of 2 \times 2 matrix algebras), we can extend the above hardness and easiness statements to more general algebras as follows. Let A be a finite dimensional algebra over a finite field with radical R(A). * [Hardness] If the quotient A/R(A) is non-commutative, then computing the determinant over the algebra A is as hard as computing the permanent. * [Easiness] If the quotient A/R(A) is commutative and furthermore, R(A) has nilpotency index d (i.e., the smallest d such that R(A)d = 0), then there exists a poly(n^d)-time algorithm that computes determinants over the algebra A. In particular, for any constant dimensional algebra A over a finite field, since the nilpotency index of R(A) is at most a constant, we have the following dichotomy theorem: if A/R(A) is commutative, then efficient determinant computation is feasible and otherwise determinant is as hard as permanent.

We give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of degree-d polynomial threshold functions (PTFs). These bounds hold both for PTFs over the Boolean hypercube {-1,1}n and for PTFs over Rn under the standard n-dimensional Gaussian distribution N(0,In). Our bound on the Boolean average sensitivity of PTFs represents progress towards the resolution of a conjecture of Gotsman and Linial [17], which states that the symmetric function slicing the middle d layers of the Boolean hypercube has the highest average sensitivity of all degree-d PTFs. Via the L1 polynomial regression algorithm of Kalai et al. [22], our bounds on Gaussian and Boolean noise sensitivity yield polynomial-time agnostic learning algorithms for the broad class of constant-degree PTFs under these input distributions.

Let X be randomly chosen from {-1,1}n, and let Y be randomly chosen from the standard spherical Gaussian on Rn. For any (possibly unbounded) polytope P formed by the intersection of k halfspaces, we prove that |Pr[X ∈ P] - Pr[Y ∈ P]| ≤ log8/5k • Δ, where Δ is a parameter that is small for polytopes formed by the intersection of "regular" halfspaces (i.e., halfspaces with low influence). The novelty of our invariance principle is the polylogarithmic dependence on k. Previously, only bounds that were at least linear in k were known.

We present a simple proof of the bounded-depth Frege proof lower bounds of Pitassi et al. [1993] and Krajíček et al. [1995] for the pigeonhole principle. Our method uses the interpretation of proofs as two player games given by Pudlák and Buss. Our lower bound is conceptually simpler than previous ones, and relies on tools and intuition that are well known in the context of computational complexity. This makes the lower bound of Pitassi et al. [1993] and Krajíček et al. [1995] accessible to the general computational complexity audience. We hope this new view will open new directions for research in proof complexity.

The main result of this paper is a generic composition theorem for low error two-query probabilistically checkable proofs (PCPs). Prior to this work, composition of PCPs was well-understood only in the constant error regime. Existing composition methods in the low error regime were non-modular (i.e., very much tailored to the specific PCPs that were being composed), resulting in complicated constructions of PCPs. Furthermore, until recently, composition in the low error regime suffered from incurring an extra 'consistency' query, resulting in PCPs that are not 'two-query' and hence, much less useful for hardness-of-approximation reductions. In a recent breakthrough, Moshkovitz and Raz [In Proc. 49th IEEE Symp. on Foundations of Comp. Science (FOCS), 2008] constructed almost linear-sized low-error 2-query PCPs for every language in NP. Indeed, the main technical component of their construction is a novel composition of certain specific PCPs. We give a modular and simpler proof of their result by repeatedly applying the new composition theorem to known PCP components. To facilitate the new modular composition, we introduce a new variant of PCP, which we call a "decodable PCP (dPCP)". A dPCP is an encoding of an NP witness that is both locally checkable and locally decodable. The dPCP verifier in addition to verifying the validity of the given proof like a standard PCP verifier, also locally decodes the original NP witness. Our composition is generic in the sense that it works regardless of the way the component PCPs are constructed.

LetXandYbe finite nonempty sets and(X,Y) a pair of random variables taking values inX?Y. We consider communication protocols between two parties,AliceandBob, for generatingXandY.Aliceis provided anx?Xgenerated according to the distribution ofX, and is required to send a message toBobin order to enable him to generatey?Y, whose distribution is the same as that ofY|X=x. Both parties have access to a shared random string generated in advance. LetT[X:Y] be the minimum (over all protocols) of the expected number of bitsAliceneeds to transmit to achieve this. We show that I[X:Y] ? T[X:Y] ? I [X:Y] + 2 log2(I[X:Y]+ O(1). We also consider the worst case communication required for this problem, where we seek to minimize the average number of bitsAlicemust transmit for the worst casex?X. We show that the communication required in this case is related to the capacityC(E) of the channelE, derived from(X,Y) , that mapsx?Xto the distribution ofY|X=x. We also show that the required communicationT(E) satisfiesC(E) ?T(E) ?C(E) + 2 log2(C(E)+1) +O(1). Using the first result, we derive a direct-sum theorem in communication complexity that substantially improves the previous such result shown by Jain, Radhakrishnan, and Sen [In Proc. 30th International Colloquium of Automata, Languages and Programming (ICALP), ser. Lecture Notes in Computer Science, vol. 2719. 2003, pp. 300-315]. These results are obtained by employing a rejection sampling procedure that relates the relative entropy between two distributions to the communication complexity of generating one distribution from the other.

We continue the study of the trade‐off between the length of probabilistically checkable proofs (PCPs) and their query complexity, establishing the following main results (which refer to proofs of satisfiability of circuits of size n): 1. We present PCPs of length $\exp(o(\log\log n)^2)\cdot n$ that can be verified by making $o(\log\log n)$ Boolean queries. 2. For every \epsilon>0, we present PCPs of length $\exp(\log^\epsilon n)\cdot n$ that can be verified by making a constant number of Boolean queries. In both cases, false assertions are rejected with constant probability (which may be set to be arbitrarily close to 1). The multiplicative overhead on the length of the proof, introduced by transforming a proof into a probabilistically checkable one, is just quasi polylogarithmic in the first case (of query complexity $o(\log\log n)$), and is $2^{(\log n)^\epsilon}$, for any $\epsilon > 0$, in the second case (of constant query complexity). Our techniques include the introduction of a new variant of PCPs that we call “robust PCPs of proximity.” These new PCPs facilitate proof composition, which is a central ingredient in the construction of PCP systems. (A related notion and its composition properties were discovered independently by Dinur and Reingold.) Our main technical contribution is a construction of a “length‐efficient” robust PCP of proximity. While the new construction uses many of the standard techniques used in PCP constructions, it does differ from previous constructions in fundamental ways, and in particular does not use the “parallelization” step of Arora et al. [J. ACM, 45 (1998), pp. 501–555]. The alternative approach may be of independent interest. We also obtain analogous quantitative results for locally testable codes. In addition, we introduce a relaxed notion of locally decodable codes and present such codes mapping k information bits to codewords of length $k^{1+\epsilon}$ for any $\epsilon>0$.

We show that every language in NP has a probabilistically checkable proof of proximity (i.e., proofs asserting that an instance is "close" to a member of the language), where the verifier's running time is polylogarithmic in the input size and the length of the probabilistically checkable proof is only polylogarithmically larger that the length of the classical proof. (Such a verifier can only query polylogarithmically many bits of the input instance and the proof. Thus it needs oracle access to the input as well as the proof, and cannot guarantee that the input is in the language - only that it is close to some string in the language.) If the verifier is restricted further in its query complexity and only allowed q queries, then the proof size blows up by a factor of 2/sup (log n)c/q/ where the constant c depends only on the language (and is independent of q). Our results thus give efficient (in the sense of running time) versions of the shortest known PCPs, due to Ben-Sasson et al. (STOC '04) and Ben-Sasson and Sudan (STOC '05), respectively. The time complexity of the verifier and the size of the proof were the original emphases in the definition of holographic proofs, due to Babai et al. (STOC '91), and our work is the first to return to these emphases since their work. Of technical interest in our proof is a new complete problem for NEXP based on constraint satisfaction problems with very low complexity constraints, and techniques to arithmetize such constraints over fields of small characteristic.

For a Boolean formula $\phi$ on n variables, the associated property $P_\phi$ is the collection of n-bit strings that satisfy $\phi$. We study the query complexity of tests that distinguish (with high probability) between strings in $P_\phi$ and strings that are far from $P_\phi$ in Hamming distance. We prove that there are 3CNF formulae (with O(n) clauses) such that testing for the associated property requires $\Omega(n)$ queries, even with adaptive tests. This contrasts with 2CNF formulae, whose associated properties are always testable with $O(\sqrt{n})$ queries [E. Fischer et al., Monotonicity testing over general poset domains, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 474--483]. Notice that for every negative instance (i.e., an assignment that does not satisfy $\phi$) there are three bit queries that witness this fact. Nevertheless, finding such a short witness requires reading a constant fraction of the input, even when the input is very far from satisfying the formula that is associated with the property. A property is linear if its elements form a linear space. We provide sufficient conditions for linear properties to be hard to test, and in the course of the proof include the following observations which are of independent interest: In the context of testing for linear properties, adaptive two-sided error tests have no more power than nonadaptive one-sided error tests. Moreover, without loss of generality, any test for a linear property is a linear test. A linear test verifies that a portion of the input satisfies a set of linear constraints, which define the property, and rejects if and only if it finds a falsified constraint. A linear test is by definition nonadaptive and, when applied to linear properties, has a one-sided error.Random low density parity check codes (which are known to have linear distance and constant rate) are not locally testable. In fact, testing such a code of length n requires $\Omega(n)$ queries.

We continue the study of the trade-off between the length of PCP sand their query complexity, establishing the following main results(which refer to proofs of satisfiability of circuits of size n): 1 We present PCPs of length exp(Õ(log log n)2)•n that can be verified by making o(log logn) Boolean queries.For every ε>0, we present PCPs of length exp(logε n)• n that can be verified by making a constant number of Boolean queries. In both cases, false assertions are rejected withconstant probability (which may be set to be arbitrarily close to 1). The multiplicative overhead on the length of the proof, introduced by transforming a proof into a probabilistically checkable one, is just quasi-polylogarithmic in the first case (ofquery complexity o(log logn)), and 2(log n)ε, for any ε>0, in the second case (of constant query complexity). In contrast, previous results required at least 2 √logn overhead in the length, even to get query complexity 2 √log n. Our techniques include the introduction of a new variant of PCPs that we call "Robust PCPs". These new PCPs facilitate proof composition, which is a central ingredient in construction of PCP systems. (A related notion and its composition properties were discovered independently by Dinur and Reingold. ) Our main technical contribution is a construction of a "length-efficient" Robust PCP. While the new construction uses many of the standard techniques in PCPs, it does differ from previous constructions in fundamental ways, and in particular does not use the "parallelization" step of Arora et al. . The alternative approach may be of independent interest. We also obtain analogous quantitative results for locally testable codes. In addition, we introduce a relaxed notion of locally decodable codes,and present such codes mapping k information bits to code words of length κ1+ε, for any ε>0.

For a boolean formula φ on n variables, the associated property Pφ is the collection of n-bit strings that satisfy φ. We prove that there are 3CNF properties that require a linear number of queries, even for adaptive tests. This contrasts with 2CNF properties that are testable with O(√n) queries[7]. Notice that for every bad instance (i.e. an assignment that does not satisfy φ) there is a 3-bit query that witnesses this fact. Nevertheless, finding such a short witness requires a linear number of queries, even for assignments that are very far from satisfying.We provide sufficient conditions for linear properties to be hard to test, and in the course of the proof include a couple of observations which are of independent interest.