Interactive oracle proofs (IOPs) extend the classical notion of probabilistically-checkable proofs (PCPs) by allowing a verifier to interact with a prover over a small number of rounds, while querying the prover’s messages in only a few locations. A recent line of work gave highly-efficient IOPs outperforming state-of-the-art PCPs, for example, constant-round and constant-query (ZK-)IOPs with only a linear (and even approaching the witness length) amount of communication, as well as (ZK-)IOPs with linear-time prover complexity. These constructions were leveraged in turn to obtain highly-efficient succinct arguments and zero-knowledge proofs. The improved efficiency was obtained by replacing polynomial-based codes, commonly used in such proof systems, with more efficient (tensor-based) codes. In particular, these constructions bypassed a barrier imposed by the need to encode the computation using a multiplication code. In the talk I will survey these highly-efficient IOP constructions, and highlight some interesting open problems raised by these works.

We present efficient decoding algorithms from square-root errors for two known families of double-circulant codes: A construction based on Sidon sets (Bhargava, Taveres, and Shiva, \emph{IEEE IT 74}; Calderbank, \emph{IEEE IT 83}; Guruswami and Li, \emph{IEEE IT 2025}), and a construction based on cyclic codes (Chen, Peterson, and Weldon, \emph{Information and Control 1969}). We further observe that the work of Guruswami and Li implicitly gives a transformation from double-circulant codes of certain block lengths to Wozencraft codes which preserves that distance of the codes, and we show that this transformation also preserves efficiency of decoding. By instantiating this transformation with the first family of double-circulant codes based on Sidon sets, we obtain an explicit construction of a Wozencraft code that is efficiently decodable from square-root errors. We also discuss limitations on instantiating this transformation with the second family of double-circulant codes based on cyclic codes.

Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input x belongs to a language \(L \in \mathsf {NP}\) , with communication that is much shorter than the \(\mathsf {NP}\) witness. Such arguments, which grew out of the theory literature, are now drawing immense interest also in practice, where a key bottleneck that has arisen is the high computational cost of proving correctness. In this work, we address this problem by constructing succinct arguments for general computations, expressed as Boolean circuits (of bounded fan-in), with a strictly linear size prover. The soundness error of the protocol is an arbitrarily small constant. Prior to this work, succinct arguments were known with a quasi- linear size prover for general Boolean circuits or with linear-size only for arithmetic circuits, defined over large finite fields. In more detail, for every Boolean circuit \(C=C(x,w)\) , we construct an \(O(\log |C|)\) -round argument-system in which the prover can be implemented by a size \(O(|C|)\) Boolean circuit (given as input both the instance x and the witness w ), with arbitrarily small constant soundness error and using \(\mathrm{poly}(\lambda ,\log |C|)\) communication, where \(\lambda\) denotes the security parameter. The verifier can be implemented by a size \(O(|x|) + \mathrm{poly}(\lambda , \log |C|)\) circuit following a size \(O(|C|)\) private pre-processing step, or, alternatively, by using a purely public-coin protocol (with no pre-processing) with a size \(O(|C|)\) verifier. The protocol can be made zero-knowledge using standard techniques (and with similar parameters). The soundness of our protocol is computational and relies on the existence of collision resistant hash functions that can be computed by linear-size circuits, such as those proposed by Applebaum et al. (ITCS, 2017). At the heart of our construction is a new information-theoretic interactive oracle proof ( \(\mathsf {IOP}\) ), an interactive analog of a \(\mathsf {PCP}\) , for circuit satisfiability, with constant prover overhead. The improved efficiency of our \(\mathsf {IOP}\) is obtained by bypassing a barrier faced by prior \(\mathsf {IOP}\) constructions, which needed to (either explicitly or implicitly) encode the entire computation using a multiplication code.

We investigate the relation between $δ$ and $ε$ required for obtaining a $(1+δ)$-approximation in time $N^{2-ε}$ for closest pair problems under various distance metrics, and for other related problems in fine-grained complexity. Specifically, our main result shows that if it is impossible to (exactly) solve the (bichromatic) inner product (IP) problem for vectors of dimension $c \log N$ in time $N^{2-ε}$, then there is no $(1+δ)$-approximation algorithm for (bichromatic) Euclidean Closest Pair running in time $N^{2-2ε}$, where $δ\approx (ε/c)^2$ (where $\approx$ hides $\polylog$ factors). This improves on the prior result due to Chen and Williams (SODA 2019) which gave a smaller polynomial dependence of $δ$ on $ε$, on the order of $δ\approx (ε/c)^6$. Our result implies in turn that no $(1+δ)$-approximation algorithm exists for Euclidean closest pair for $δ\approx ε^4$, unless an algorithmic improvement for IP is obtained. This in turn is very close to the approximation guarantee of $δ\approx ε^3$ for Euclidean closest pair, given by the best known algorithm of Almam, Chan, and Williams (FOCS 2016). By known reductions, a similar result follows for a host of other related problems in fine-grained hardness of approximation. Our reduction combines the hardness of approximation framework of Chen and Williams, together with an MA communication protocol for IP over a small alphabet, that is inspired by the MA protocol of Chen (Theory of Computing, 2020).

Interactive oracle proofs (IOPs) are a hybrid between interactive proofs and PCPs. In an IOP, the prover is allowed to interact with a verifier (like in an interactive proof) by sending relatively long messages to the verifier, who in turn is only allowed to query a few of the bits that were sent (like in a PCP). Efficient IOPs are currently at the core of leading practical implementations of highly efficient proof-systems. In this work we construct, for a large class of NP relations, IOPs in which the communication complexity approaches the witness length. More precisely, for any NP relation for which membership can be decided in polynomial-time with bounded polynomial space (i.e., space n ξ for some sufficiently small constant ξ > 0; e.g., SAT, Hamiltonicity, Clique, Vertex-Cover) and for any constant γ > 0, we construct an IOP with communication complexity (1 + γ) ⋅ n , where n is the original witness length. The number of rounds, as well as the number of queries made by the IOP verifier, are constant. This result improves over prior works on short IOPs/PCPs in two ways. First, the communication complexity in these short IOPs is proportional to the complexity of verifying the NP witness, which can be polynomially larger than the witness size. Second, even ignoring the difference between witness length and non-deterministic verification time, prior works incur (at the very least) a large constant multiplicative overhead to the communication complexity. In particular, as a special case, we also obtain an IOP for CircuitSAT with communication complexity (1 + γ) ⋅ t , for circuits of size t and any constant γ > 0. This improves upon the prior state-of-the-art work of Ben Sasson et al. (ICALP, 2017) who construct an IOP for CircuitSAT with communication length c ⋅ t for a large (unspecified) constant c ≥ 1. Our proof leverages the local testability and (relaxed) local correctability of high-rate tensor codes, as well as their support of a sumcheck-like procedure. In particular, we bypass the barrier imposed by the low rate of multiplication codes (e.g., Reed–Solomon, Reed–Muller, or AG codes)—a key building block of all known short PCP/IOP constructions.

We show that Gallager's ensemble of low-density parity-check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have this property. This result opens up a potential avenue toward truly linear-time list-decodable codes that achieve list-decoding capacity. Our result on list-decoding follows from a much more general result: any local property satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager's distribution. Local properties are properties characterized by the exclusion of small sets of codewords and include list-decodability, list-recoverability, and average-radius list-decodability. In order to prove our results on LDPC codes, we establish sharp thresholds for when local properties are satisfied by a random linear code. More precisely, we show that for any local property $\mathcal{P}$, there is some $R^*$ so that random linear codes of rate slightly less than $R^*$ satisfy $\mathcal{P}$ with high probability, while random linear codes of rate slightly more than $R^*$, with high probability, do not. We also give a characterization of the threshold rate $R^*$.

Abstract. We show new and improved list decoding properties of folded Reed–Solomon (RS) codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the source of recent advances in coding theory: folded RS codes were the first known explicit construction of capacity-achieving list decodable codes [V. Guruswami and A. Rudra, IEEE Trans. Inform. Theory, 54 (2008), pp. 135–150], and multiplicity codes were the first construction of high-rate locally decodable codes [S. Kopparty, S. Saraf, and S. Yekhanin, J. ACM, 61 (2014), 28]. In this work, we show that folded RS codes and multiplicity codes are in fact better than previously known in the context of list decoding and local list decoding. Our first main result shows that folded RS codes achieve list decoding capacity with constant list sizes, independent of the block length. Prior work with constant list sizes first obtained list sizes that are polynomial in the block length and relied on pre-encoding with subspace evasive sets to reduce the list sizes to a constant [V. Guruswami and C. Wang, IEEE Trans. Inform. Theory, 59 (2013), pp. 3257–3268], [Z. Dvir and S. Lovett, Proc. 44 th STOC, ACM, 2012, 351–358]. The list size we obtain is [Formula: see text] where [Formula: see text] is the gap to capacity, which matches the list size obtained by pre-encoding with subspace evasive sets. For our second main result, we observe that univariate multiplicity codes exhibit similar behavior, and we use this, together with additional ideas, to show that multivariate multiplicity codes are locally list decodable up to their minimum distance. By known reductions, this gives, in turn, capacity-achieving locally list decodable codes with query complexity [Formula: see text]. This improves on the tensor-based construction of [B. Hemenway, N. Ron-Zewi, and M. Wootters, SIAM J. Comput., 49 (2019), pp. 157–195], which gave capacity-achieving locally list decodable codes of query complexity [Formula: see text], and is close to the best known query complexity of [Formula: see text] for high-rate locally (uniquely) decodable codes [S. Kopparty et al., J. ACM, 64 (2017), 11].

Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input x belongs to a language L ∈ NP, with communication that is much shorter than the NP witness. Such arguments, which grew out of the theory literature, are now drawing immense interest also in practice, where a key bottleneck that has arisen is the high computational cost of proving correctness.

This issue of SICOMP contains six specially selected papers from STOC 2020, the Fifty-second Annual ACM Symposium on the Theory of Computing, which was held June 22--26, 2020, initially planned at Chicago, Illinois, but due to COVID-19 was an online conference in the end. The papers here were chosen to represent the range and quality of the STOC program. These papers have been revised and extended by their authors and subjected to the standard thorough reviewing process of SICOMP. The program committee for STOC 2020 consisted of an executive committee made up of Nima Anari, Boaz Barak, Sébastien Bubeck, Mark Bun, Arkadev Chattopadhyay, Chandra Chekuri, Julia Chuzhoy, Marek Cygan, Ilias Diakonikolas, Yevgeniy Dodis, Sebastian Forster, Ankit Garg, Nika Haghtalab, Prahladh Harsha, Justin Holmgren, Piotr Indyk, Rahul Jain, Sanjeev Khanna, Dakshita Khurana, Pravesh Kothari, Robert Krauthgamer, Marvin Künnemann, Tengyu Ma, Rafael Oliveira, Merav Parter, Sofya Raskhodnikova, Robert Robere, Dana Ron, Noga Ron-Zewi, Thatchaphol Saranurak, Balasubramanian Sivan, Christian Sohler, Madhur Tulsiani, Omri Weinstein, Christian Wulff-Nilsen, and Henry Yuen. The program chair was Julia Chuzhoy. Included in this issue are the following papers: ``Explicit Near-Ramanujan Graphs of Every Degree" by Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes shows a deterministic poly$(n)$-time algorithm that outputs a $d$-regular graph on $\Theta(n)$ vertices that is $\epsilon$-near-Ramanujan. ``Reducing Path TSP to TSP" by Vera Traub, Jens Vygen, and Rico Zenklusen presents a black-box reduction from the path version of the traveling salesman problem (Path TSP) to the classical tour version (TSP). ``Nearly Optimal Static Las Vegas Succinct Dictionary" by Huacheng Yu obtains a randomized dictionary data structure using ${OPT}+{poly}\lg n+O(\lg^{(\ell)} U)$ bits of space with expected constant query time for the static dictionary problem. ``Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions" by Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh Raj Saxena, and S. Matthew Weinberg provides the first separation in the approximation guarantee achievable by truthful and nontruthful combinatorial auctions with polynomial communication. ``Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization" by Lijie Chen and Hanlin Ren establish a connection between nondeterministic algorithms estimating the acceptance probability of a given circuit and average-case lower bounds for nondeterministic time classes. ``Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs" by Siddharth Bhandari and Sayantan Chakraborty presents a randomized algorithm that takes as input an undirected $n$-vertex graph $G$ with maximum degree $\Delta$ and an integer $k>3\Delta$ and returns a random proper $k$-coloring of $G$. We thank the authors, the STOC 2020 program committee, the STOC 2020 external reviewers, and the SICOMP referees for all of their hard work. Arkadev Chattopadhyay, Marek Cygan, Noga Ron-Zewi, Christian Wulff-Nilsen - Guest editors

We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes withbothconstant alphabet and constant list sizes. More specifically, for any$R \in (0,1)$and$\epsilon >0$, we give an algebraic construction of an infinite family of error-correcting codes of rate$R$, over an alphabet of size$(1/\epsilon)^{O(1/\epsilon ^{2})}$, that can be list decoded from a$(1-R-\epsilon)$-fraction of errors with list size at most$\exp (\mathrm {poly}(1/ \epsilon))$. Moreover, the codes can be encoded in time$\mathrm {poly}(1/ \epsilon,n)$, the output list is contained in a linear subspace of dimension at most$\mathrm {poly}(1/ \epsilon)$, and a basis for this subspace can be found in time$\mathrm {poly}(1 /\epsilon, n)$. Thus, both encoding and list decoding can be performed infully polynomial-time$\mathrm {poly}(1/ \epsilon,n)$, except for pruning the subspace and outputting the final list which takes time$\exp (\mathrm {poly}(1/ \epsilon)) \cdot \mathrm {poly} (n)$. In contrast, prior explicit and efficient constructions of capacity-achieving list decodable codes either required a much higher complexity in terms of$1/ \epsilon $(and were additionally much less structured), or had super-constant alphabet or list sizes. Our codes are quite natural and structured. Specifically, we use algebraic-geometric (AG) codes with evaluation points restricted to a subfield, and with the message space restricted to a (carefully chosen) linear subspace. Our main observation is that the output list of AG codes with subfield evaluation points is contained in an affine shift of the image of ablock-triangular-Toeplitz(BTT)matrix, and that the list size can potentially be reduced to a constant by restricting the message space to a BTTevasive subspace, which is a large subspace that intersects the image of any BTT matrix in a constant number of points. We further show how to explicitly construct such BTT evasive subspaces, based on the explicit subspace designs of Guruswami and Kopparty (Combinatorica, 2016), and composition.

A binary code Enc:{0,1}^k → {0,1}ⁿ is (1/2-ε,L)-list decodable if for every w ∈ {0,1}ⁿ, there exists a set List(w) of size at most L, containing all messages m ∈ {0,1}^k such that the relative Hamming distance between Enc(m) and w is at most 1/2-ε. A q-query local list-decoder for Enc is a randomized procedure Dec that when given oracle access to a string w, makes at most q oracle calls, and for every message m ∈ List(w), with high probability, there exists j ∈ [L] such that for every i ∈ [k], with high probability, Dec^w(i,j) = m_i. We prove lower bounds on q, that apply even if L is huge (say L = 2^{k^{0.9}}) and the rate of Enc is small (meaning that n ≥ 2^{k}): - For ε = 1/k^{ν} for some constant 0 < ν < 1, we prove a lower bound of q = Ω(log(1/δ)/ε²), where δ is the error probability of the local list-decoder. This bound is tight as there is a matching upper bound by Goldreich and Levin (STOC 1989) of q = O(log(1/δ)/ε²) for the Hadamard code (which has n = 2^k). This bound extends an earlier work of Grinberg, Shaltiel and Viola (FOCS 2018) which only works if n ≤ 2^{k^ν} and the number of coins tossed by Dec is small (and therefore does not apply to the Hadamard code, or other codes with low rate). - For smaller ε, we prove a lower bound of roughly q = Ω(1/(√ε)). To the best of our knowledge, this is the first lower bound on the number of queries of local list-decoders that gives q ≥ k for small ε. Local list-decoders with small ε form the key component in the celebrated theorem of Goldreich and Levin that extracts a hard-core predicate from a one-way function. We show that black-box proofs cannot improve the Goldreich-Levin theorem and produce a hard-core predicate that is hard to predict with probability 1/2 + 1/𝓁^ω(1) when provided with a one-way function f:{0,1}^𝓁 → {0,1}^𝓁, where f is such that circuits of size poly(𝓁) cannot invert f with probability ρ = 1/2^√𝓁 (or even ρ = 1/2^Ω(𝓁)). This limitation applies to any proof by black-box reduction (even if the reduction is allowed to use nonuniformity and has oracle access to f).

We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is approximately locally list recoverable, as well as globally list recoverable in probabilistic near-linear time. This was used in turn to give the first capacity-achieving list decodable codes with (1) local list decoding algorithms, and with (2) probabilistic near-linear time global list decoding algorithms. This also yielded constant-rate codes approaching the Gilbert-Varshamov bound with probabilistic near-linear time global unique decoding algorithms. In the current work we obtain the following results: 1) The tensor product of an efficient (poly-time) high-rate globally list recoverable code is globally list recoverable in deterministic near-linear time. This yields in turn the first capacity-achieving list decodable codes with deterministic near-linear time global list decoding algorithms. It also gives constant-rate codes approaching the Gilbert-Varshamov bound with deterministic near-linear time global unique decoding algorithms. 2) If the base code is additionally locally correctable, then the tensor product is (genuinely) locally list recoverable. This yields in turn (non-explicit) constant-rate codes approaching the Gilbert-Varshamov bound that are locally correctable with query complexity and running time No(1). This improves over prior work by Gopi et. al. (SODA'17; IEEE Transactions on Information Theory'18) that only gave query complexity NE with rate that is exponentially small in 1/ε. 3) A nearly-tight combinatori allower bound on output list size for list recovering high-rate tensor codes. This bound implies in turn a nearly-tight lower bound of NΩ(1/loglogN)on the product of query complexity and output list size for locally list recovering high-rate tensor codes.

We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have this property. This result opens up a potential avenue towards truly linear-time list-decodable codes that achieve list-decoding capacity. Our result on list decoding follows from a much more general result: any local property satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager's distribution. Local properties are properties characterized by the exclusion of small sets of codewords, and include list-decoding, list-recovery and average-radius list-decoding. In order to prove our results on LDPC codes, we establish sharp thresholds for when local properties are satisfied by a random linear code. More precisely, we show that for any local property P, there is some R* so that random linear codes of rate slightly less than R* satisfy P with high probability, while random linear codes of rate slightly more than R* with high probability do not. We also give a characterization of the threshold rate R*. This is an extended abstract. The full version is available at https://arxiv.org/abs/1909.06430

Interactive oracle proofs (IOPs) are a hybrid between interactive proofs and PCPs. In an IOP the prover is allowed to interact with a verifier (like in an interactive proof) by sending relatively long messages to the verifier, who in turn is only allowed to query a few of the bits that were sent (like in a PCP). Efficient IOPs are at the core of leading practical implementations of highly efficient proof-systems. In this work we construct, for a large class of N P relations, IOPs in which the communication complexity approaches the witness length. More precisely, for any N P relation for which membership can be decided in polynomial-time and bounded polynomial space (e.g., SAT, Hamiltonicity, Clique, Vertex-Cover, etc.) and for any constant , we construct an IOP with communication complexity (1+γ)·n, where n is the original witness length. The number of rounds, as well as the number of queries made by the IOP verifier, are constant. This result improves over prior works on short IOPs/PCPs in two ways. First, the communication complexity in these short IOPs is proportional to the complexity of verifying the NP witness, which can be polynomially larger than the witness size. Second, even ignoring the difference between witness length and non-deterministic verification time, prior works incur (at the very least) a large constant multiplicative overhead to the communication complexity. In particular, as a special case, we also obtain an IOP for CircuitSAT with communication complexity (1+γ)·t, for circuits of size t and any constant . This improves upon the prior state-of-the-art work of Ben Sasson et al. (ICALP, 2017) who construct an IOP for CircuitSAT with communication length c·t for a large (unspecified) constant c ≥ 1. Our proof leverages the local testability and (relaxed) local correctability of high-rate tensor codes, as well as their support of a sumcheck-like procedure. In particular, we bypass the barrier imposed by the low rate of multiplication codes (e.g., Reed-Solomon, Reed-Muller or AG codes) - a key building block of all known short PCP/IOP constructions.

We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let r > 0 be any integer. Given an inner codeC0of length d, and a d-regular bipartite expander graph G with n vertices on each side, we give an algorithm to list-decode the codeC=C(G,C0) of length nd from approximately δδrnd erasures in time n·poly (d2r/δ), where δ and δrare the relative distance and the r'th generalized relative distance ofC0, respectively. To the best of our knowledge, this is the first linear-time algorithm that can list-decode expander codes from erasures beyond their (designed) distance of approximately δ2nd. To obtain our results, we show that an approach similar to that of (Hemenway and Wootters, Information and Computation, 2018) can be used to obtain such an erasure-list-decoding algorithm with an exponentially worse dependence of the running time on r and δ; then we show how to improve the dependence of the running time on these parameters.

We show that the tensor product of a high-rate globally list recoverable code is (approximately) locally list recoverable. List recovery has been a useful building block in the design of list decodable codes, and our motivation is to use the tensor construction as such a building block. In particular, instantiating this construction with known constructions of high-rate globally list recoverable codes, and using appropriate transformations, we obtain the first capacity-achieving locally list decodable codes (over a large constant size alphabet), and the first capacity-achieving globally list decodable codes with nearly linear time list decoding algorithms. Our techniques are inspired by an approach of Gopalan, Guruswami, and Raghavendra [ SIAM J. Comput., 40 (2011), pp. 1432--1462] for list decoding tensor codes.

We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is approximately locally list recoverable, as well as globally list recoverable in probabilistic near-linear time. This was used in turn to give the first capacity-achieving list decodable codes with (1) local list decoding algorithms, and with (2) probabilistic near-linear time global list decoding algorithms. This also yielded constant-rate codes approaching the Gilbert-Varshamov bound with probabilistic near-linear time global unique decoding algorithms. In the current work we obtain the following results: 1) The tensor product of an efficient (poly-time) high-rate globally list recoverable code is globally list recoverable in deterministic near-linear time. This yields in turn the first capacity-achieving list decodable codes with deterministic near-linear time global list decoding algorithms. It also gives constant-rate codes approaching the Gilbert-Varshamov bound with deterministic near-linear time global unique decoding algorithms. 2) If the base code is additionally locally correctable, then the tensor product is (genuinely) locally list recoverable. This yields in turn (non-explicit) constant-rate codes approaching the Gilbert-Varshamov bound that are locally correctable with query complexity and running time N^{o(1)}. This improves over prior work by Gopi et. al. (SODA'17; IEEE Transactions on Information Theory'18) that only gave query complexity N^{epsilon} with rate that is exponentially small in 1/epsilon. 3) A nearly-tight combinatorial lower bound on output list size for list recovering high-rate tensor codes. This bound implies in turn a nearly-tight lower bound of N^{Omega(1/log log N)} on the product of query complexity and output list size for locally list recovering high-rate tensor codes.

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.

In this work, we show new and improved error-correcting properties of folded Reed-Solomon codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the sources of recent advances in coding theory. Folded Reed-Solomon codes were the first explicit constructions of codes known to achieve list-decoding capacity; multivariate multiplicity codes were the first constructions of high-rate locally correctable codes; and univariate multiplicity codes are also known to achieve list-decoding capacity. However, previous analyses of the error-correction properties of these codes did not yield optimal results. In particular, in the list-decoding setting, the guarantees on the list-sizes were polynomial in the block length, rather than constant; and for multivariate multiplicity codes, local list-decoding algorithms could not go beyond the Johnson bound. In this paper, we show that Folded Reed-Solomon codes and multiplicity codes are in fact better than previously known in the context of list decoding and local list-decoding. More precisely, we first show that Folded RS codes achieve list-decoding capacity with constant list sizes, independent of the block length; and that high-rate univariate multiplicity codes can also be list-recovered with constant list sizes. Using our result on univariate multiplicity codes, we show that multivariate multiplicity codes are high-rate, locally list-recoverable codes. Finally, we show how to combine the above results with standard tools to obtain capacity achieving locally list decodable codes with query complexity significantly lower than was known before.

We show an explicit (that is, efficient and deterministic) capacity approaching interactive coding scheme that simulates any interactive protocol under random errors with nearly optimal communication rate. Specifically, over the binary symmetric channel with crossover probability ϵ, our coding scheme achieves a communication rate of 1- O(√/H(ϵ)), together with negligible exp(-Ω(ϵ4n/logn)) failure probability (over the randomness of the channel). A rate of 1 - Θ(√/H(ϵ)) is likely asymptotically optimal as a result of Kol and Raz (2013) suggests. Prior to this paper, such a communication rate was achievable only using randomized coding schemes [Kol and Raz (2013); Hauepler (2014)].

One of the most important open problems in the theory of error-correcting codes is to determine the tradeoff between the rate R and minimum distance δ of a binary code. The best known tradeoff is the Gilbert-Varshamov bound, and says that for every δ ∈ (0, 1/2), there are codes with minimum distance δ and rate R = RGV(δ) 0 (for a certain simple function RGV(·)). In this paper, we show that the Gilbert-Varshamov bound can be achieved by codes, which support local error-detection and error-correction algorithms. Specifically, we show the following results. 1) Local testing: for all δ ∈ (0, 1/2) and all RGV(δ), there exist codes with length n, rate R, and minimum distance δ that are locally testable with quasipoly log(n) query complexity. 2) Local correction: for all ϵ > 0, for all δGV(δ), there exist codes with length n, rate R, and minimum distance δ that are locally correctable from (δ/2)-o(1) fraction errors with O(nϵ) query complexity. Furthermore, these codes have an efficient randomized construction, and the local testing and local correction algorithms can be made to run in time polynomial in the query complexity. Our results on locally correctable codes also immediately give locally decodable codes with the same parameters. Our local testing result is obtained by combining Thommesen's random concatenation technique and the best known locally testable codes by Kopparty et al. Our local correction result, which is significantly more involved, also uses random concatenation, along with a number of further ideas: the Guruswami-Sudan-Indyk list decoding strategy for concatenated codes, Alon-Edmonds-Luby distance amplification, and the local list-decodability, local list-recoverability, and local testability of Reed-Muller codes. Curiously, our final local correction algorithms go via local list-decoding and local testing algorithms; this seems to be the first time local testability is used in the construction of a locally correctable code.

In this work, we give the first construction of high-rate locally list-recoverable codes. List-recovery has been an extremely useful building block in coding theory, and our motivation is to use these codes as such a building block. In particular, our construction gives the first capacity-achieving locally list-decodable codes (over constant-sized alphabet); the first capacity achieving globally list-decodable codes with nearly linear time list decoding algorithm (once more, over constant-sized alphabet); and a randomized construction of binary codes on the Gilbert-Varshamov bound that can be uniquely decoded in near-linear-time, with higher rate than was previously known. Our techniques are actually quite simple, and are inspired by an approach of Gopalan, Guruswami, and Raghavendra (Siam Journal on Computing, 2011) for list-decoding tensor codes. We show that tensor powers of (globally) list-recoverable codes are `approximately' locally list-recoverable, and that the `approximately' modifier may be removed by pre-encoding the message with a suitable locally decodable code. Instantiating this with known constructions of high-rate globally list-recoverable codes and high-rate locally decodable codes finishes the construction.

One of the most important open problems in the theory of error-correcting codes is to determine the tradeoff between the rate R and minimum distance δ of a binary code. The best known tradeoff is the Gilbert-Varshamov bound, and says that for every δ ∊ (0,1/2), there are codes with minimum distance δ and rate R = rGV (δ) > 0 (for a certain simple function rGV(·)). In this paper we show that the Gilbert-Varshamov bound can be achieved by codes which support local error-detection and error- correction algorithms. Specifically, we show the following results. 1. Local Testing: For all δ ∊ (0,1/2) and all R < rGV(δ), there exist codes with length n, rate R and minimum distance δ that are locally testable with quasipolylog(n) query complexity. 2. Local Correction: For all ∊ > 0, for all δ < 1/2 sufficiently large, and all R < (1 — ∊)RGV(δ), there exist codes with length n, rate R and minimum distance δ that are locally correctable from fraction errors with O(ne) query complexity. Furthermore, these codes have an efficient randomized construction, and the local testing and local correction algorithms can be made to run in time polynomial in the query complexity. Our results on locally correctable codes also immediately give locally decodable codes with the same parameters. Our local testing result is obtained by combining Thommesen's random concatenation technique and the best known locally testable codes from [KMRS16]. Our local correction result, which is significantly more involved, also uses random concatenation, along with a number of further ideas: the Guruswami-Sudan-Indyk list decoding strategy for concatenated codes, Alon- Edmonds-Luby distance amplification, and the local list-decodability, local list-recoverability and local testability of Reed-Muller codes. Curiously, our final local correction algorithms go via local list-decoding and local testing algorithms; this seems to be the first time local testability is used in the construction of a locally correctable code.

Locally correctable codes (LCCs) and locally testable codes (LTCs) are error-correcting codes that admit local algorithms for correction and detection of errors. Those algorithms are local in the sense that they only query a small number of entries of the corrupted codeword. The fundamental question about LCCs and LTCs is to determine the optimal tradeoff among their rate, distance, and query complexity. In this work, we construct the first LCCs and LTCs with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist LCCs and LTCs with block length n , constant rate (which can even be taken arbitrarily close to 1), and constant relative distance, whose query complexity is exp(Õ(√log n )) (for LCCs) and (log n ) O (log log n ) (for LTCs). In addition to having small query complexity, our codes also achieve better tradeoffs between the rate and the relative distance than were previously known to be achievable by LCCs or LTCs. Specifically, over large (but constant size) alphabet, our codes approach the Singleton bound, that is, they have almost the best-possible relationship between their rate and distance. Over the binary alphabet, our codes meet the Zyablov bound. Such tradeoffs between the rate and the relative distance were previously not known for any o ( n ) query complexity. Our results on LCCs also immediately give locally decodable codes with the same parameters.

We study efficient, deterministic interactive coding schemes that simulate any interactive protocol both under random and adversarial errors, and can achieve a constant communication rate independent of the protocol length. For channels that flip bits independently with probability ∊ < 1/2, our coding scheme achieves a communication rate of and a failure probability of exp(−n/log n) in length n protocols. Prior to our work, all nontrivial deterministic schemes (either efficient or not) had a rate bounded away from 1. Furthermore, the best failure probability achievable by an efficient deterministic coding scheme with constant rate was only quasi-polynomial, i.e., of the form exp(− logO(1) n) (Braverman, ITCS 2012). For channels in which an adversary controls the noise pattern our coding scheme can tolerate Ω(1/log n) fraction of errors with rate approaching 1. Once more, all previously known nontrivial deterministic schemes (either efficient or not) in the adversarial setting had a rate bounded away from 1, and no nontrivial efficient deterministic coding schemes were known with any constant rate. Essential to both results is an explicit, efficiently encodable and decodable systematic tree code of length n that has relative distance Ω(1/log n) and rate approaching 1, defined over an O(log n)-bit alphabet. No nontrivial tree code (either efficient or not) was known to approach rate 1, and no nontrivial distance bound was known for any efficient constant rate tree code. The fact that our tree code is systematic, turns out to play an important role in obtaining rate in the random error model, and approaching rate 1 in the adversarial error model.

In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist LCCs and LTCs with block length n, constant rate (which can even be taken arbitrarily close to 1) and constant relative distance, whose query complexity is exp(Õ(√logn)) (for LCCs) and (logn)O(loglogn) (for LTCs). Previously such codes were known to exist only with Ω(nβ) query complexity (for constant β>0).

We establish a new connection between affine and two-source extractors by presenting black-box constructions of two-source extractors for min-entropy rate below half from any affine extractor for min-entropy rate below half. Two such constructions are presented, and one of our constructions can reach arbitrarily small min-entropy rate assuming that the affine extractor has sufficiently good parameters. The first part of our analysis shows that our constructions are two-source dispersers which are weak (but nontrivial) kinds of two-source extractors, also known as “bipartite Ramsey graphs.” To strengthen this result and obtain two-source extractors we introduce the approximate duality conjecture (ADC) and initiate its study. The ADC leads to a rather general result that can be used to convert a natural class of two-source dispersers---``low-rank dispersers''---into two-source extractors. More specifically, we first prove a special case of ADC that implies that the constructions mentioned above are two-source extractors with large (but nontrivial) constant error. In an attempt to reduce the error in our constructions we show that the polynomial Freiman--Ruzsa conjecture (PFR) in additive combinatorics implies a stronger “approximate duality” statement (and that this stronger statement also implies a weak but as-of-yet-unknown version of PFR). This stronger statement implies in turn that our constructions are two-source extractors with exponentially small error.

During the last 10 to 15 years, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important concern in SAT solving, and so research has mostly focused on weak systems that are used by SAT solvers. There has been a relatively long sequence of papers on space in resolution, which is now reasonably well-understood from this point of view. For other proof systems of interest, however, such as polynomial calculus or cutting planes, progress has been more limited. Essentially nothing has been known about space complexity in cutting planes, and for polynomial calculus the only lower bound has been for conjunctive normal form (CNF) formulas of unbounded width in [Alekhnovich et al., SIAM J. Comput., 31 (2002), pp. 1184--1211], where the space lower bound is smaller than the initial width of the clauses in the formulas. Thus, in particular, it has been consistent with current knowledge that polynomial calculus could be able to refute any $k$-CNF formula in constant space. In this paper, we prove several new results on space in polynomial calculus (PC) and in the extended proof system polynomial calculus resolution (PCR) studied by Alekhnovich et al.: (1) We prove an $\omega(n)$ space lower bound in PC for the canonical 3-CNF version of the pigeonhole principle formulas $PHP_{m}^{n}$ with $m$ pigeons and $n$ holes, and show that this is tight. (2) For PCR, we prove an $\omega(n)$ space lower bound for a bitwise encoding of the functional pigeonhole principle. These formulas have width O(log n), and hence this is an exponential improvement over Alekhnovich et al. measured in the width of the formulas. (3) We then present another encoding of the pigeonhole principle that has constant width, and prove an $\omega(n)$ space lower bound in PCR for these formulas as well. (4) Finally, we prove that any $k$-CNF formula can be refuted in PC in simultaneous exponential size and linear space (which holds for resolution and thus for PCR, but was not obviously the case for PC). We also characterize a natural class of CNF formulas for which the space complexity in resolution and PCR does not change when the formula is transformed into 3-CNF in the canonical way, something that we believe can be useful when proving PCR space lower bounds for other well-studied formula families in proof complexity.

28 pages

Identifying complexity measures that bound the communication complexity of a {0,1}-valued matrix M is one the most fundamental problems in communication complexity. Mehlhorn and Schmidt [1982] were the first to suggest matrix-rank as one such measure. Among other things, they showed log rank F(M) CC(M) rankF2(M), where CC ( M ) denotes the (deterministic) communication complexity of the function associated with M , and the rank on the left-hand side is over any field F and on the right-hand side it is over the two-element field F 2. For certain matrices M , communication complexity equals the right-hand side, and this completely settles the question of “communication complexity vs. F 2-rank”. Here we reopen this question by pointing out that, when M has an additional natural combinatorial property---high discrepancy with respect to distributions which are uniform over submatrices---then communication complexity can be sublinear in F 2-rank. Assuming the Polynomial Freiman-Ruzsa (PFR) conjecture in additive combinatorics, we show that CC(M) O(rank F2(M)/log rank F2(M)) for any matrix M which satisfies this combinatorial property. We also observe that if M has low rank over the reals, then it has low rank over F 2 and it additionally satisfies this combinatorial property. As a corollary, our results also give the first (conditional) sublinear bound on communication complexity in terms of rank over the reals, a result improved later by Lovett [2014]. Our proof is based on the study of the “approximate duality conjecture” which was suggested by Ben-Sasson and Zewi [2011] and studied there in connection to the PFR conjecture. First, we improve the bounds on approximate duality assuming the PFR conjecture. Then, we use the approximate duality conjecture (with improved bounds) to get our upper bound on the communication complexity of low-rank matrices.

During the last decade, an active line of research in proof complexity has been to study space complexity and time space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving. For the polynomial calculus proof system, the only previously known space lower bound is for CNF formulas of unbounded width in [Alekhnovich et al. '02], where the lower bound is smaller than the initial width of the clauses in the formulas. Thus, in particular, it has been consistent with current knowledge that polynomial calculus could refute any k-CNF formula in constant space. We prove several new results on space in polynomial calculus (PC) and in the extended proof system polynomial calculus resolution (PCR) studied in [Alekhnovich et al. '02]. (1) For PCR, we prove an Ω(n) space lower bound for a bitwise encoding of the functional pigeonhole principle with m pigeons and n holes. These formulas have width O(log n), and hence this is an exponential improvement over [Alekhnovich et al. '02] measured in the width of the formulas. (2) We then present another encoding of the pigeonhole principle that has constant width, and prove an Ω(n) space lower bound in PCR for these formulas as well. (3) We prove an Ω(n) space lower bound in PC for the canonical 3-CNF version of the pigeonhole principle formulas PHPmnwith m pigeons and n holes, and show that this is tight. (4) We prove that any k-CNF formula can be refuted in PC in simultaneous exponential size and linear space (which holds for resolution and thus for PCR, but was not known to be the case for PC). We also characterize a natural class of CNF formulas for which the space complexity in resolution and PCR does not change when the formula is transformed into 3-CNF in the canonical way.

For a {0, 1}-valued matrix M let CC(M) denote the deterministic communication complexity of the boolean function associated with M. It is well-known since the work of Mehlhorn and Schmidt [STOC 1982] that CC(M) is bounded from above by rank(M) and from below by log rank(M) where rank(M) denotes the rank of M over the field of real numbers. Determining where in this range lies the true worst-case value of CC(M) is a fundamental open problem in communication complexity. The state of the art is log1.631rank(M) ≤ CC(M) ≤ 0.415 rank(M), the lower bound is by Kushilevitz [unpublished, 1995] and the upper bound is due to Kotlov [Journal of Graph Theory, 1996]. Lovasz and Saks [FOCS 1988] conjecture that CC(M) is closer to the lower bound, i.e., CC(M)≤ logcrank(M)) for some absolute constant c - this is the famous "log-rank conjecture'' - but so far there has been no evidence to support it, even giving a slightly non-trivial (o(rank(M))) upper bound on the communication complexity. Our main result is that, assuming the Polynomial Freiman-Ruzsa (PFR) conjecture in additive combinatorics, there exists a universal constant c such that CC(M) ≤ c ·rank(M)/log rank(M). Although our bound is stated using the rank of M over the reals, our proof goes by studying the problem over the finite field of size 2, and there we bring to bear a number of new tools from additive combinatorics which we hope will facilitate further progress on this perplexing question. In more detail, our proof is based on the study of the "approximate duality conjecture'' which was suggested by Ben-Sasson and Zewi [STOC 2011] and studied there in connection to the PFR conjecture. First we improve the bounds on approximate duality assuming the PFR conjecture. Then we use the approximate duality conjecture (with improved bounds) to get our upper bound on the communication complexity of low-rank martices.

We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field Fqand an extension field Fqn, a property is a set of functions mapping Fqnto Fq. The property is said to be affine-invariant if it is invariant under affine transformations of Fqn, and it is said to be sparse if its size is polynomial in the domain size. Our work completes a line of work initiated by Grigorescu et al. [RANDOM 2009] and followed by Kaufman and Lovett [FOCS 2011]. The latter showed such a result for the case when q was prime. Extending to non-prime cases turns out to be non-trivial and our proof involves some detours into additive combinatorics, as well as a new calculus for building property testers for affine-invariant linear properties.

Two-source and affine extractors and dispersers are fundamental objects studied in the context of derandomization. This paper shows how to construct two-source extractors and dispersers for arbitrarily small min-entropy rate in a black-box manner given affine extractors with sufficiently good parameters. Our analysis relies on the study of approximate duality, a concept related to the polynomial Freiman-Ruzsa conjecture (PFR) from additive combinatorics. Two black-box constructions of two-source extractors from affine ones are presented. Both constructions work for min-entropy rate ρ0. We show that assuming the PFR conjecture, the error of this two-source extractor is exponentially small.The extractor-to-disperser reduction arises from studying approximate duality, a notion related to additive combinatorics. The duality measure of two sets A,B ⊆ F_2n aims to quantify how close these sets are to being dual and is defined as [u(A,B)=|Ea ∈ A, b ∈ B[(-1)∑i=1n ai bi]|] Notice that u(A,B)=1 implies that A is contained in an affine shift of B⊥ --- the space dual to the F2span of B. We study what can be said of A,B when their duality measure is large but strictly smaller than 1 and show that A,B contain subsets A',B' of nontrivial size for which u(A',B')=1 and consequently A' is contained in an affine shift of (B')⊥. This implies that our constructions are two-source extractors with constant error. Surprisingly, the PFR implies that such A',B' exist exist when A,B are large, even if the duality measure is exponentially small in $n$, and this implication leads to two-source extractors with exponentially small error.