In this work we give the first proof that Trace Hermitian codes have vanishing bias. This brings to the front the question of understanding the distance of Trace AG codes, and the fascinating possibility that in some variation they might give asymptotically good codes.

In this paper we study a basic and natural question about Fourier analysis of Boolean functions, which has applications to the study of Matching Vector based Private Information Retrieval (PIR) schemes. For integers m,r, define a delta function on {0,1}^r ⊆ ℤ_m^r to be a function f: ℤ_m^r → C if f(0) = 1 and f(x) = 0 for all nonzero Boolean x. The basic question that we study is how small can the Fourier sparsity of a delta function be; namely, how sparse can such an f be in the Fourier basis? In addition to being intrinsically interesting and natural, such questions arise naturally while studying "S-decoding polynomials" for the known matching vector families. Finding S-decoding polynomials of reduced sparsity - which corresponds to finding delta functions with low Fourier sparsity - would improve the current best PIR schemes. We show nontrivial upper and lower bounds on the Fourier sparsity of delta functions. Our proofs are elementary and clean. These results imply limitations on improvements to the Matching Vector PIR schemes simply by finding better S-decoding polynomials. In particular, there are no S-decoding polynomials which can make Matching Vector PIRs based on the known matching vector families achieve polylogarithmic communication for constantly many servers. Many interesting questions remain open.

This paper is motivated by basic complexity and probability questions about permanents of random matrices over small finite fields, and in particular, about properties separating the permanent and the determinant. Let q be a fixed odd prime, and let k ≤ n both be growing. For a uniformly random n × k matrix A over 𝔽_q, we study the probability that all k × k submatrices of A have zero permanent; namely that A does not have full permanental rank. When k = n, this is simply the probability that a random square matrix over 𝔽_q has zero permanent, which we do not understand. We believe that the probability in this case is 1/q + o(1), which would be in contrast to the case of the determinant, where the answer is 1/q + Ω_q(1). Our main result is that when k is O(√n), the probability that a random n × k matrix does not have full permanental rank is essentially the same as the probability that the matrix has a 0 column, namely (1 +o(1)) k/qⁿ. In contrast, for determinantal (standard) rank the analogous probability is Θ(q^k/q^n). At the core of our result are some basic linear algebraic properties of the permanent that distinguish it from the determinant.

In this paper, we construct Error-Correcting Graph Codes. An error-correcting graph code of distance δ is a family C of graphs, on a common vertex set of size n, such that if we start with any graph in C, we would have to modify the neighborhoods of at least δ n vertices in order to obtain some other graph in C. This is a natural graph generalization of the standard Hamming distance error-correcting codes for binary strings. Yohananov and Yaakobi were the first to construct codes in this metric. We extend their work by showing 1) Combinatorial results determining the optimal rate vs distance trade-off nonconstructively. 2) Graph code analogues of Reed-Solomon codes and code concatenation, leading to positive distance codes for all rates and positive rate codes for all distances. 3) Graph code analogues of dual-BCH codes, yielding large codes with distance δ = 1-o(1). This gives an explicit "graph code of Ramsey graphs". Several recent works, starting with the paper of Alon, Gujgiczer, Körner, Milojević, and Simonyi, have studied more general graph codes; where the symmetric difference between any two graphs in the code is required to have some desired property. Error-correcting graph codes are a particularly interesting instantiation of this concept.

A method of constructing specific polynomial representations $f(x)$ over the finite field $\mathbb{F}_p$ of the square roots function modulo a prime $p = 2^kn + 1$, $n$ odd, is presented. The formulas for the cases $k = 2$, $3$ and $4$ are given.

We study the problem of extracting randomness from somewhere-random sources, and related combinatorial phenomena: partition analogues of Shearer’s lemma on projections. A somewhere-random source is a tuple (X_1, …, X_t) of (possibly correlated) {0,1}ⁿ-valued random variables X_i where for some unknown i ∈ [t], X_i is guaranteed to be uniformly distributed. An extracting merger is a seeded device that takes a somewhere-random source as input and outputs nearly uniform random bits. We study the seed-length needed for extracting mergers with constant t and constant error. Since a somewhere-random source has min-entropy at least n, a standard extractor can also serve as an extracting merger. Our goal is to understand whether the further structure of being somewhere-random rather than just having high entropy enables smaller seed-length, and towards this we show: - Just like in the case of standard extractors, seedless extracting mergers with even just one output bit do not exist. - Unlike the case of standard extractors, it is possible to have extracting mergers that output a constant number of bits using only constant seed. Furthermore, a random choice of merger does not work for this purpose! - Nevertheless, just like in the case of standard extractors, an extracting merger which gets most of the entropy out (namely, having Ω(n) output bits) must have Ω(log n) seed. This is the main technical result of our work, and is proved by a second-moment strengthening of the graph-theoretic approach of Radhakrishnan and Ta-Shma to extractors. All this is in contrast to the status for condensing mergers (where the output is only required to have high min-entropy), whose seed-length/output-length tradeoffs can all be fully explained by using standard condensers. Inspired by such considerations, we also formulate a new and basic class of problems in combinatorics: partition analogues of Shearer’s lemma. We show basic results in this direction; in particular, we prove that in any partition of the 3-dimensional cube [0,1]³ into two parts, one of the parts has an axis parallel 2-dimensional projection of area at least 3/4.

Given disjoint sets S , S' ⊆ 𝔽 q of size n and a function f : S → 𝔽 q , where 𝔽 q is a finite field, the low-degree extension (LDE) of f to S' is the function f ' : S ' → 𝔽 q obtained by restricting the interpolating polynomial of f to S' . LDE computation is a fundamental primitive of modern algebraic coding theory and cryptography. The best asymptotic running time for LDE with parameter n is O(n log n ) arithmetic operations over 𝔽 q - when q and the sets S, S' are special. This running time is achieved via the Fast Fourier Transform (FFT), and requires 𝔽 q to contain a multiplicative subgroup of smooth order ≥ n (smoothness means being the product of small primes). Another variant uses an additive subgroup of smooth order ≥ n . Most finite fields do not contain such a subgroup, which raises the question of computing the LDE in time O(n · log n ) over general finite fields, for some disjoint pair of sets S , S ' of size n . The main result of this paper is a positive answer to this question, presenting O(n log n )-time LDE for special S , S ' shown to exist over all fields, as long as q = Ω( n 2 ). This result is achieved by introducing a new FFT-like transform, the Elliptic Curve Fast Fourier Transform (ECFFT), which gives an approach to fast algorithms (using preprocessing) for polynomial operations over all large finite fields. The key idea is to replace the group of roots of unity with a set of points L ⊂ 𝔽 q suitably related to a well-chosen elliptic curve group over 𝔽 q (the set L itself is not a group). The key advantage of this approach is that elliptic curve groups can be of any size in the Hasse-Weil interval and thus can have subgroups of large, smooth order, which an FFT-like divide and conquer algorithm can exploit. Compare this with multiplicative subgroups over 𝔽 q whose order must divide q − 1. By analogy, our method extends the standard, multiplicative FFT in a similar way to how Lenstra's elliptic curve method [Len87] extended Pollard's p − 1 algorithm [Pol74] for factoring integers. Representing polynomials by their evaluation over (well-chosen) subsets of L , we use the ECFFT to compute the LDE in time O(n log n ). We also give small arithmetic circuits for polynomial multiplication, division, degree-computation, interpolation, evaluation and Reed-Solomon encoding (also known as low-degree extension) with fixed evaluation points , matching the circuit size of classical FFT-based algorithms when the field size q is special. For the classical problems (in the standard representation) of low degree extension with chosen evaluation points, and evaluating elementary symmetric polynomials, this yields the asymptotically smallest known arithmetic circuits. The efficiency of the classical FFT follows from using the 2-to-1 squaring map to reduce the evaluation set of roots of unity of order 2 k to similar groups of size 2 k-i , i > 0. Our algorithms operate similarly, using isogenies of elliptic curves with kernel size 2 as 2-to-1 maps to reduce L of size 2 k to sets of size 2 k-i that are, like L , suitably related to elliptic curves, albeit different ones.

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].

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.

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.

Motivated by problems in algebraic complexity theory (e.g., matrix multiplication) and extremal combinatorics (e.g., the cap set problem and the sunflower problem), we introduce the geometric rank as a new tool in the study of tensors and hypergraphs. We prove that the geometric rank is an upper bound on the subrank of tensors and the independence number of hypergraphs. We prove that the geometric rank is smaller than the slice rank of Tao, and relate geometric rank to the analytic rank of Gowers and Wolf in an asymptotic fashion. As a first application, we use geometric rank to prove a tight upper bound on the (border) subrank of the matrix multiplication tensors, matching Strassen's well-known lower bound from 1987.

A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are δ-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are δ-close to the property. In particular, no set in the collection has roughly half of its members δ-close to the property and the others δ-far from it. We show that the collection of affine spaces displays a proximity gap with respect to Reed-Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any δ smaller than the Johnson/Guruswami-Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least) linear size in the RS code dimension, for δ smaller than the unique decoding radius. Concretely, if δ is smaller than half the minimal distance of an RS code V ⊂ Fqn, every affine space is either entirely δ-close to the code, or alternatively at most an ( n/q)-fraction of it is δ-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems. We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed-Solomon codes (due to Berlekamp-Welch and Guruswami-Sudan) on a formal element of an affine space. This involves working with Reed-Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests.

Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. The previous state of the art by [Ben-Sasson, Kopparty, Saraf, CCC 2018] showed that if some member of an affine space U is δ-far in relative Hamming distance from a linear code V - this is the worst-case assumption - then most elements of U are almost-δ-far from V - this is the average case. However, this result was known to hold only below the "double Johnson" function of the relative distance δ_V of the code V, i.e., only when δ < 1-(1-δ_V)^(1/4). First, we increase the soundness-bound to the "one-and-a-half Johnson" function of δ_V and show that the average distance of U from V is nearly δ for any worst-case distance δ smaller than 1-(1-δ_V)^(1/3). This bound is tight, which is somewhat surprising because the one-and-a-half Johnson function is unfamiliar in the literature on error correcting codes. To improve soundness further for Reed Solomon codes we sample outside the box. We suggest a new protocol in which the verifier samples a single point z outside the box D on which codewords are evaluated, and asks the prover for the value at z of the interpolating polynomial of a random element of U. Intuitively, the answer provided by the prover "forces" it to choose one codeword from a list of "pretenders" that are close to U. We call this technique Domain Extending for Eliminating Pretenders (DEEP). The DEEP method improves the soundness of the worst-case-to-average-case reduction for RS codes up their list decoding radius. This radius is bounded from below by the Johnson bound, implying average distance is approximately δ for all δ < 1-(1-δ_V)^(1/2). Under a plausible conjecture about the list decoding radius of Reed-Solomon codes, average distance from V is approximately δ for all δ. The DEEP technique can be generalized to all linear codes, giving improved reductions for capacity-achieving list-decodable codes. Finally, we use the DEEP technique to devise two new protocols: - An Interactive Oracle Proof of Proximity (IOPP) for RS codes, called DEEP-FRI. The soundness of the protocol improves upon that of the FRI protocol of [Ben-Sasson et al., ICALP 2018] while retaining linear arithmetic proving complexity and logarithmic verifier arithmetic complexity. - An Interactive Oracle Proof (IOP) for the Algebraic Linking IOP (ALI) protocol used to construct zero knowledge scalable transparent arguments of knowledge (ZK-STARKs) in [Ben-Sasson et al., eprint 2018]. The new protocol, called DEEP-ALI, improves soundness of this crucial step from a small constant < 1/8 to a constant arbitrarily close to 1.

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.

We consider codes for space bounded channels. This is a model for communication under noise that was studied by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in one pass, and modifies at most a p fraction of the bits of the codeword. Guruswami and Smith, and later work by Shaltiel and Silbak (RANDOM 2016), gave constructions of listdecodable codes with rate approaching 1 - H(p) against channels with space s = clog n, with encoding/decoding time poly(2s) = poly(nc). In this paper we show that for every constant 00, there are codes with rate R ≥ 1 - H(p) - ε, list size poly(1/ε), and furthermore: . Our codes can handle channels with space s = nΩ(1), which is much larger than O(log n) achieved by previous work. . We give encoding and decoding algorithms that run in time n · polylog(n). Previous work achieved large and unspecified poly(n) time (even for space s = 1 · log n channels). . We can handle space bounded channels that read the codeword in any order, whereas previous work considered channels that read the codeword in the standard order. Our construction builds on the machinery of Guruswami and Smith (with some key modifications) replacing some nonconstructive codes and pseudorandom objects (that are found in exponential time by brute force) with efficient explicit constructions. For this purpose we exploit recent results of Haramaty, Lee and Viola (SICOMP 2018) on pseudorandom properties of “t-wise independence + low weight noise” which we quantitatively improve using techniques by Forbes and Kelly (FOCS 2018). To make use of such distributions, we give new explicit constructions of binary linear codes that have dual distance of nΩ(1), and are also polynomial time list-decodable from relative distance á1/2-ε, with list size poly(1/ε). To the best of our knowledge, no such construction was previously known. Somewhat surprisingly, we show that Reed-Solomon codes with dimension k <; √n, have this property if interpreted as binary codes (in some specific interpretation)which we term: “Raw Reed-Solomon Codes”. A key idea is viewing Reed-Solomon codes as “bundles” of certain dualBCH codewords.

This special section comprises eleven fully refereed papers whose extended abstracts were presented at the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016) in New Brunswick, New Jersey, October 9--11, 2016. The unrefereed conference versions of these papers were published by IEEE in the FOCS 2016 proceedings. The regular conference program consisted of 85 papers chosen from among 307 submissions. These were selected by a program committee consisting of Eric Blais, Mark Braverman, Siu On Chan, Moses Charikar, Marek Cygan, Irit Dinur (chair), Andrew Drucker, Faith Ellen, Sariel Har-Peled, Prahladh Harsha, Alexandra Kolla, Swastik Kopparty, Robert Krauthgamer, Brendan Lucier, Or Meir, Raghu Meka, Daniele Micciancio, Moni Naor, Joe Neeman, Rasmus Pagh, Rocco Servedio, Yaoyun Shi, Ola Svensson, Thomas Vidick, and Daniel Wichs. The papers invited to this special section were also selected with the input of the program committee. The eleven papers in this section include a broad range of topics, including algorithms, combinatorics, circuit complexity, data structures, learning theory, parameterized complexity, and probability. We thank the authors and the anonymous referees for their efforts. In addition, we would like to thank SICOMP Editor-in-Chief Leonard Schulman and SIAM Senior Publications Coordinator Heather Blythe for their help in preparing this special section.

Algebraic proof systems reduce computational problems to problems about estimating the distance of a sequence of functions vec{u}=(u_1,..., u_k), given as oracles, from a linear error correcting code V. The soundness of such systems relies on methods that act "locally" on vec{u} and map it to a single function u^* that is, roughly, as far from V as are u_1,..., u_k. Motivated by these applications to efficient proof systems, we study a natural worst-case to average-case reduction of distance for linear spaces, and show several general cases in which the following statement holds: If some member of a linear space U=span(u_1,...,u_k) is delta-far from (all elements) of V in relative Hamming distance, then nearly all elements of U are (1-epsilon)delta-far from V; the value of epsilon depends only on the distance of the code V and approaches 0 as that distance approaches 1. Our results improve on the previous state-of-the-art which showed that nearly all elements of U are 1/2delta-far from V [Rothblum, Vadhan and Wigderson, STOC 2013]. When V is a Reed-Solomon (RS) code, as is often the case for algebraic proof systems, we show how to boost distance via a new "local" transformation that may be useful elsewhere. Relying on the affine-invariance of V, we map a vector u to a random linear combination of affine transformations of u, and show this process amplifies distance from V. Assuming V is an RS code with sufficiently large distance, this amplification process converts a function u that is somewhat far from V to one that is (1-epsilon)-far from V; as above, epsilon depends only on the distance of V and approaches 0 as the distance of V approaches 1. We give two concrete application of these techniques. First, we revisit the axis-parallel low-degree test for bivariate polynomials of [Polischuk-Spielman, STOC 1994] and prove a "list-decoding" type result for it, when the degree of one axis is extremely small. This result is similar to the recent list-decoding-regime result of [Chiesa, Manohar and Shinkar, RANDOM 2017] but is proved using different techniques, and allows the degree in one axis to be arbitrarily large. Second, we improve the soundness analysis of the recent RS proximity testing protocol of [Ben-Sasson et al., ICALP 2018] and extend it to the "list-decoding" regime, bringing it closer to the Johnson bound.

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.

In the simultaneous Max-Cut problem, we are given k weighted graphs on the same set of n vertices, and the goal is to find a cut of the vertex set so that the minimum, over the k graphs, of the cut value is as large as possible. Previous work [BKS15] gave a polynomial time algorithm which achieved an approximation factor of 1/2 – o(1) for this problem (and an approximation factor of 1/2 + εk in the unweighted case, where εk → 0 as k → ∞). In this work, we give a polynomial time approximation algorithm for simultaneous Max-Cut with an approximation factor of 0.8780 (for all constant k). The natural SDP formulation for simultaneous Max-Cut was shown to have an integrality gap of 1/2 + εk in [BKS15]. In achieving the better approximation guarantee, we use a stronger Sum-of-Squares hierarchy SDP relaxation and a rounding algorithm based on Raghavendra-Tan [RT12], in addition to techniques from [BKS15].

Reed-Muller codes are some of the oldest and most widely studied error-correcting codes, of interest for both their algebraic structure as well as their many algorithmic properties. A recent beautiful result of Saptharishi, Shpilka and Volk [SSV17] showed that for binary Reed-Muller codes of length n and distance d = O(1), one can correct polylog(n) random errors in poly(n) time (which is well beyond the worst-case error tolerance of O(1)). In this paper, we consider the problem of syndrome decoding Reed-Muller codes from random errors. More specifically, given the polylog(n)-bit long syndrome vector of a codeword corrupted in polylog(n) random coordinates, we would like to compute the locations of the codeword corruptions. This problem turns out to be equivalent to a basic question about computing tensor decomposition of random low-rank tensors over finite fields. Our main result is that syndrome decoding of Reed-Muller codes (and the equivalent tensor decomposition problem) can be solved efficiently, i.e., in polylog(n) time. We give two algorithms for this problem: 1. The first algorithm is a finite field variant of a classical algorithm for tensor decomposition over real numbers due to Jennrich. This also gives an alternate proof for the main result of [SSV17]. 2. The second algorithm is obtained by implementing the steps of [SSV17]'s Berlekamp-Welch-style decoding algorithm in sublinear-time. The main new ingredient is an algorithm for solving certain kinds of systems of polynomial equations.

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.

The explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Yet, the codes being deployed in practice are fairly short. In this work, we address what we view as the main coding theoretic barrier to deploying longer codes in storage: at large lengths, failures are not independent and correlated failures are inevitable. This motivates designing codes that allow quick data recovery even after large correlated failures, and which have efficient encoding and decoding. We propose that code design for distributed storage be viewed as a two step process. The first step is choose a topology of the code, which incorporates knowledge about the correlate d failures that need to be handled, and ensures local recovery from such failures. In the second step one specifies a code with the chosen topology by choosing coefficients from a finite field Fq. In this step, one tries to balance reliability (which is better over larger fields) with encoding and decoding efficiency (which is better over smaller fields). This work initiates an in-depth study of this reliability/efficiency tradeoff. We consider the field-size needed for achieving maximal recover ability: the strongest reliability possible with a given topology. We propose a family of topologies called grid-like topologies which unify a number of topologies considered both in theory and practice, and prove the following results about codes for such topologies: The first super-polynomial lower bound on the field size needed for achieving maximal recoverability in a simple grid-like topology. To our knowledge, there was no super-linear lower bound known before, for any topology. A combinatorial characterization of erasure patterns correctable by Maximally Recoverable codes for a topology which corresponds to tensoring MDS codes with a parity check code. This topology is used in practice (for instance see [MLR+14]). We conjecture a similar characterization for Maximally Recoverable codes instantiating arbitrary tensor product topologies.

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 give a polynomial time algorithm to decode multivariate polynomial codes of degree d up to half their minimum distance, when the evaluation points are an arbitrary product set S^m, for every d < |S|. Previously known algorithms could achieve this only if the set S has some very special algebraic structure, or if the degree d is significantly smaller than |S|. We also give a near-linear time algorithm, which is based on tools from list-decoding, to decode these codes from nearly half their minimum distance, provided d < (1-epsilon)|S| for constant epsilon > 0. Our result gives an m-dimensional generalization of the well known decoding algorithms for Reed-Solomon codes, and can be viewed as giving an algorithmic version of the Schwartz-Zippel lemma.

In this paper, we construct large sequences and matrices with the property that the contents of any small window determine the location of the window, robustly. Such objects have found many applications in practical settings, from positioning of wireless devices to smart pens, and have recently gained some theoretical interest. In this context, we give the first explicit constructions of sequences and matrices with high rate and constant relative distance. Accompanying these efficient constructions, we also give efficient decoding algorithms, which can determine the position of the window given its contents, even if a constant fraction of the contents have been corrupted.

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).

The PCP theorem [Arora et al. 1998; Arora and Safra 1998] says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up incurred by this encoding, that is, how long is the PCP compared to the original NP-proof? The state-of-the-art work of Ben-Sasson and Sudan [2008] and Dinur [2007] shows that one can encode proofs of length n by PCPs of length n · poly log n that can be verified using a constant number of queries. In this work, we show that if the query complexity is relaxed to n ε , then one can construct PCPs of length O ( n ) for circuit-SAT, and PCPs of length O ( t log t ) for any language in NTIME( t ). More specifically, for any ε > 0, we present (nonuniform) probabilistically checkable proofs (PCPs) of length 2 O (1/ε) · n that can be checked using n ε queries for circuit-SAT instances of size n . Our PCPs have perfect completeness and constant soundness. This is the first constant-rate PCP construction that achieves constant soundness with nontrivial query complexity ( o ( n )). Our proof replaces the low-degree polynomials in algebraic PCP constructions with tensors of transitive algebraic geometry (AG) codes. We show that the automorphisms of an AG code can be used to simulate the role of affine transformations that are crucial in earlier high-rate algebraic PCP constructions. Using this observation, we conclude that any asymptotically good family of transitive AG codes over a constant-sized alphabet leads to a family of constant-rate PCPs with polynomially small query complexity. Such codes are constructed in the appendix to this article for the first time for every message length, building on an earlier construction for infinitely many message lengths by Stichtenoth [2006].

Lifted Reed-Solomon codes are a natural affine-invariant family of error-correcting codes, which generalize Reed-Muller codes. They were known to have efficient local-testing and local-decoding algorithms (comparable with the known algorithms for Reed-Muller codes), but with significantly better rate. We give efficient algorithms for list decoding and local list decoding of lifted codes. Our algorithms are based on a new technical lemma, which says that the codewords of lifted codes are low degree polynomials when viewed as univariate polynomials over a big field (even though they may be very high degree when viewed as multivariate polynomials over a small field).

In this paper we show that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. Specifically, we show that given an arithmetic circuit (either explicitly or via black-box access) that computes a multivariate polynomial f, the task of computing arithmetic circuits for the factors of f can be solved deterministically, given a deterministic algorithm for the polynomial identity testing problem (we require either a white-box or a black-box algorithm, depending on the representation of f). Together with the easy observation that deterministic factoring implies a deterministic algorithm for polynomial identity testing, this establishes an equivalence between these two central derandomization problems of arithmetic complexity. Previously, such an equivalence was known only for multilinear circuits [SV10].

The PCP theorem (Arora et. al., J. ACM 45(1, 3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up incurred by this encoding, i.e., how long is the PCP compared to the original NP-proof. The state-of-the-art work of Ben-Sasson and Sudan (SICOMP 38(2)) and Dinur (J. ACM 54(3)) shows that one can encode proofs of length n by PCPs of quasi-linear length that can be verified using a constant number of queries. In this work, we show that if the query complexity is relaxed to polynomial, then one can construct PCPs of linear length for circuit-SAT, and PCPs of length O(tlog t) for any language in NTIME(t). Our PCPs have perfect completeness and constant soundness. This is the first constant-rate PCP construction that achieves constant soundness with nontrivial query complexity. Our proof replaces the low-degree polynomials in algebraic PCP constructions with tensors of transitive algebraic geometry (AG) codes. We show that the automorphisms of an AG code can be used to simulate the role of affine transformations which are crucial in earlier high-rate algebraic PCP constructions. Using this observation we conclude that any asymptotically good family of transitive AG codes over a constant-sized alphabet leads to a family of constant-rate PCPs with polynomially small query complexity. Such codes are constructed for the first time for every message length.

A subspace design is a collection {H1, H2, . . . , HM} of subspaces of Fmqwith the property that no low-dimensional subspace W of Fqmintersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal rate list-decodable codes over constant-sized large alphabets and sub-logarithmic (and even smaller) list size. Subspace designs are the only non-explicit part of their construction. In this paper, we give explicit constructions of subspace designs with parameters close to the probabilistic construction, and this implies the first deterministic polynomial time construction of list-decodable codes achieving the above parameters. Our constructions of subspace designs are natural and easily described, and are based on univariate polynomials over finite fields. Curiously, the constructions are very closely related to certain good list-decodable codes (folded RS codes and univariate multiplicity codes). The proof of the subspace design property uses the polynomial method (with multiplicities): Given a target low-dimensional subspace W, we construct a nonzero low-degree polynomial PWthat has several roots for each H that non-trivially intersects W. The construction of PWis based on the classical Wronskian determinant and the folded Wronskian determinant, the latter being a recently studied notion that we make explicit in this paper. Our analysis reveals some new phenomena about the zeroes of univariate polynomials, namely that polynomials with many structured roots or many high multiplicity roots tend to be linearly independent.

In this work we explore error-correcting codes derived from the "lifting" of "affine-invariant" codes. Affine-invariant codes are simply linear codes whose coordinates are a vector space over a field and which are invariant under affine-transformations of the coordinate space. Lifting takes codes defined over a vector space of small dimension and lifts them to higher dimensions by requiring their restriction to every subspace of the original dimension to be a codeword of the code being lifted. While the operation is of interest on its own, this work focusses on new ranges of parameters that can be obtained by such codes, in the context of local correction and testing. In particular we present four interesting ranges of parameters that can be achieved by such lifts, all of which are new in the context of affine-invariance and some may be new even in general. The main highlight is a construction of high-rate codes with sublinear time decoding. The only prior construction of such codes is due to Kopparty, Saraf and Yekhanin [33]. All our codes are extremely simple, being just lifts of various parity check codes (codes with one symbol of redundancy), and in the final case, the lift of a Reed-Solomon code.

We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry base-code of block-length q to a lifted-code of block-length qm, for arbitrary integer m. The construction generalizes the way degree-d, univariate polynomials evaluated over the q-element field (also known as Reed-Solomon codes) are "lifted" to degree-d, m-variate polynomials (Reed-Muller codes). A number of properties are established: The rate of the degree-lifted code is approximately a 1/m!-fraction of the rate of the base-code. The relative distance of the degree-lifted code is at least as large as that of the base-code. This is proved using a generalization of the Schwartz-Zippel Lemma to degree-lifted Algebraic-Geometry codes. [Local correction] If the base code is invariant under a group that is "close" to being doubly-transitive (in a precise manner defined later then the degree-lifted code is locally correctable with query complexity at most q2. The automorphisms of the base-code are crucially used to generate query-sets, abstracting the use of affine-lines in the local correction procedure of Reed-Muller codes. Taking a concrete illustrating example, we show that degree-lifted Hermitian codes form a family of locally correctable codes over an alphabet that is significantly smaller than that obtained by Reed-Muller codes of similar constant rate, message length, and distance.

The classical zero-one law for first-order logic on random graphs says that for every first-order property φ in the theory of graphs and every p ∈ (0,1), the probability that the random graph G ( n , p ) satisfies φ approaches either 0 or 1 as n approaches infinity. It is well known that this law fails to hold for any formalism that can express the parity quantifier: for certain properties, the probability that G ( n , p ) satisfies the property need not converge, and for others the limit may be strictly between 0 and 1. In this work, we capture the limiting behavior of properties definable in first order logic augmented with the parity quantifier, FO[⌖], over G ( n , p ), thus eluding the above hurdles. Specifically, we establish the following “modular convergence law”. For every FO[⌖] sentence φ, there are two explicitly computable rational numbers a 0 , a 1 , such that for i ∈ {0,1}, as n approaches infinity, the probability that the random graph G (2 n + i , p ) satisfies φ approaches a i . Our results also extend appropriately to FO equipped with Mod q quantifiers for prime q . In the process of deriving this theorem, we explore a new question that may be of interest in its own right. Specifically, we study the joint distribution of the subgraph statistics modulo 2 of G ( n , p ): namely, the number of copies, mod 2, of a fixed number of graphs F 1 , …, F ℓ of bounded size in G ( n , p ). We first show that every FO[⌖] property φ is almost surely determined by subgraph statistics modulo 2 of the above type. Next, we show that the limiting joint distribution of the subgraph statistics modulo 2 depends only on n mod 2, and we determine this limiting distribution completely. Interestingly, both these steps are based on a common technique using multivariate polynomials over finite fields and, in particular, on a new generalization of the Gowers norm. The first step is analogous to the Razborov-Smolensky method for lower bounds for AC 0 with parity gates, yet stronger in certain ways. For instance, it allows us to obtain examples of simple graph properties that are exponentially uncorrelated with every FO[⌖] sentence, which is something that is not known for AC 0 [⌖].

We extend the “method of multiplicities” to get the following results, of interest in combinatorics and randomness extraction. (i) We show that every Kakeya set in $\mathbb{F}_q^n$, the $n$-dimensional vector space over the finite field on $q$ elements, must be of size at least $q^n/2^n$. This bound is tight to within a $2+o(1)$ factor for every $n$ as $q\to\infty$. (ii) We give improved “randomness mergers”: Mergers are seeded functions that take as input $\ell$ (possibly correlated) random variables in $\{0,1\}^N$ and a short random seed and output a single random variable in $\{0,1\}^N$ that is statistically close to having entropy $(1-\delta)\cdot N$ when one of the $\ell$ input variables is distributed uniformly. The seed we require is only $(1/\delta)\cdot\log\ell$-bits long, which significantly improves upon previous construction of mergers. (iii) We give improved randomness extractors, based on our improved mergers. Specifically, we show how to construct randomness extractors that use logarithmic length seeds while extracting $1-o(1)$ fraction of the min-entropy of the source. Previous results could extract only a constant fraction of the entropy while maintaining logarithmic seed length. The “method of multiplicitie” was used in prior work to analyze combinatorial parameters of “algebraically nice” subsets of vector spaces over finite fields. The method works by constructing somewhat low-degree interpolating polynomials that vanish on every point in the subset with high multiplicity. The typical use of this method involves using the “algebraic niceness” to show that the interpolating polynomial also vanishes on some points outside the subset. It then uses simple bounds on the number of zeroes of low-degree polynomials to bound the combinatorial parameter of interest. Our augmentation to this technique is that we prove, under appropriate conditions, that the interpolating polynomial vanishes with high multiplicity outside the set. This novelty leads to significantly tighter analyses. To develop the extended method of multiplicities, we provide a number of basic technical results about multiplicity of zeroes of polynomials that may be of general use. For instance, we strengthen the Schwartz--Zippel lemma to show that the expected multiplicity of zeroes of a nonzero degree $d$ polynomial at a random point in $S^n$, for any finite subset $S$ of the underlying field, is at most $d/|S|$ (a fact that does not seem to have been noticed in the CS literature before).

In this paper, we give surprisingly efficient algorithms for list-decoding and testing random linear codes. Our main result is that random sparse linear codes are locally list-decodable and locally testable in the high-error regime with only a constant number of queries. More precisely, we show that for all constants c> 0 and γ > 0, and for every linear code C ⊆ 0,1N which is: sparse: |C| ≤ Nc, and unbiased: each nonzero codeword in C has weight in (1/2 - N-γ, 1/2 + N-γ), C is locally testable and locally list-decodable from (1/2 - ε)-fraction worst-case errors using only poly(1/ε) queries to a received word. We also give subexponential time algorithms for list-decoding arbitrary unbiased (but not necessarily sparse) linear codes in the high-error regime. In particular, this yields the first subexponential time algorithm even for the problem of (unique) decoding random linear codes of inverse-polynomial rate from a fixed positive fraction of errors. Earlier, Kaufman and Sudan had shown that sparse, unbiased codes can be locally (unique) decoded and locally tested from a constant fraction of errors, where this constant fraction tends to 0 as the number of codewords grows. Our results significantly strengthen their results, while also having significantly simpler proofs. At the heart of our algorithms is a natural "self-correcting" operation defined on codes and received words. This self-correcting operation transforms a code C with a received word w into a simpler code C' and a related received word w', such that w is close to C if and only if w' is close to C'. Starting with a sparse, unbiased code C and an arbitrary received word w, a constant number of applications of the self-correcting operation reduces us to the case of local list-decoding and testing for the Hadamard code, for which the well known algorithms of Goldreich-Levin and Blum-Luby-Rubinfeld are available. This yields the constant-query local algorithms for the original code C. Our algorithm for decoding unbiased linear codes in subexponential time proceeds similarly. Applying the self-correcting operation to an unbiased code C and an arbitrary received word a super-constant number of times, we get reduced to the problem of learning noisy parities, for which non-trivial subexponential time algorithms were recently given by Blum-Kalai-Wasserman and Feldman-Gopalan-Khot-Ponnuswami. Our result generalizes a result of Lyubashevsky, which gave a subexponential time algorithm for decoding random linear codes of inverse-polynomial rate from random errors.

In this paper, we introduce and develop the method of certifying polynomials for proving AC^0 circuit lower bounds. We use this method to show that Approximate Majority cannot be computed by AC^0(parity) circuits of size n^{1 + o(1)}. This implies a separation between the power of AC^0(parity) circuits of near-linear size and uniform AC^0(parity) (and even AC^0) circuits of polynomial size. This also implies a separation between randomized AC^0(parity) circuits of linear size and deterministic AC^0(parity) circuits of near-linear size. Our proof using certifying polynomials extends the deterministic restrictions technique of Chaudhuri and Radhakrishnan, who showed that Approximate Majority cannot be computed by AC^0 circuits of size n^{1+o(1)}. At the technical level, we show that for every ACP circuit C of near-linear size, there is a low degree variety V over F_2 such that the restriction of C to V is constant. We also prove other results exploring various aspects of the power of certifying polynomials. In the process, we show an essentially optimal lower bound of Omega\left(\log^{\Theta(d)} s \cdot \log \frac{1}{\epsilon} \right) on the degree of \epsilon-approximating polynomials for AC^0(parity) circuits of size s.

An affine disperser over F2n for sources of dimension d is a function f: F2n → F2 such that for any affine space S ⊆ F2n of dimension at least d, we have {f(s) : s in S} = F2. Affine dispersers have been considered in the context of deterministic extraction of randomness from structured sources of imperfect randomness. Previously, explicit constructions of affine dispersers were known for every d = Ω(n), due to Barak et. al.[2] and Bourgain[10] (the latter in fact gives stronger objects called affine extractors). In this work we give the first explicit affine dispersers for sublinear dimension. Specifically, our dispersers work even when d = Ω(n4/5). The main novelty in our construction lies in the method of proof, which relies on elementary properties of subspace polynomials. In contrast, the previous works mentioned above relied on sum-product theorems for finite fields.

We study the complexity of computing the k th-power of an element of F2n by constant depth arithmetic circuits over F2 (also known as AC 0 (⊕)). Our study encompasses the complexity of basic arithmetic operations such as computing cube-root and computing cubic-residuosity of elements of F2n. Our main result is that these problems require exponential size circuits. We also derive strong average-case versions of these results. For example, we show that no subexponential-size, constant-depth, arithmetic circuit over F2 can correctly compute the cubic residue symbol for more than 1/3 + o(1) fraction of the elements of F2n. As a corollary, we deduce a character sum bound showing that the cubic residue character over F2n is uncorrelated with all degree-d n-variate F2 polynomials (viewed as functions over F2n in a natural way), provided d ≪ n ɛ for some universal ɛ> 0. Classical methods (based on van der Corput differencing and the Weil bounds) show this only for d ≪ log(n). Our proof revisits the classical Razborov-Smolensky method for circuit lower bounds, and executes an analogue of it in the land of univariate polynomials over F2n. The tools we use come from both F2n and Fn2. In recent years, this interplay between F2n and Fn2 has played an important role in many results in pseudorandomness, property testing and coding theory.

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of its decoding algorithms has been well studied, and it has widely been suspected that nontrivial locality must come at the price of low rate. A particular setting of potential interest in practice is codes of constant rate. For such codes, decoding algorithms with locality O ( k∈ ) were known only for codes of rate ∈ Ω(1/ ∈ ), where k is the length of the message. Furthermore, for codes of rate > 1/2, no nontrivial locality had been achieved. In this article, we construct a new family of locally decodable codes that have very efficient local decoding algorithms, and at the same time have rate approaching 1. We show that for every ∈ > 0 and α > 0, for infinitely many k , there exists a code C which encodes messages of length k with rate 1 − α , and is locally decodable from a constant fraction of errors using O ( k∈ ) queries and time. These codes, which we call multiplicity codes, are based on evaluating multivariate polynomials and their derivatives. Multiplicity codes extend traditional multivariate polynomial codes; they inherit the local-decodability of these codes, and at the same time achieve better tradeoffs and flexibility in the rate and minimum distance.

The list-decodability of random linear codes is shown to be as good as that of general random codes. Specifically, for every fixed finite field Fq,p∈ (0,1 - 1/q) and ε >; 0, it is proved that with high probability a random linear codeCin Fqnof rate (1-Hq(p)-ε) can be list decoded from a fractionpof errors with lists of size at mostO(1/ε). This also answers a basic open question concerning the existence of highly list-decodable linear codes, showing that a list-size of O(1/ε) suffices to have rate within ε of the information-theoretically optimal rate of 1 - Hq(p). The best previously known list-size bound was qO(1/ε)(except in the q = 2 case where a list-size bound of O(1/ε) was known). The main technical ingredient in the proof is a strong upper bound on the probability that I random vectors chosen from a Hamming ball centered at the origin have too many (more than Ω(ℓ)) vectors from their linear span also belong to the ball.

We consider the problem of testing if a given function f:F2n→ F2is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. Alon et al. [1] proposed and analyzed a natural 2d+1-query test for this problem. This test turned out to be intimately related to the Gowers norm. Alon et. al. showed that this test accepts every degree d polynomial with probability 1, while it rejects functions that are Ω(1)-far with probability Ω(1/(d2d)). We give an asymptotically optimal analysis of this test, and show that it rejects functions that are (even only) Ω(2-d)-far with Ω(1)probability (so the rejection probability is a universal constant independent of d and n). This implies a tight relationship between the (d + 1)st-Gowers norm of a function and its maximal correlation with degree d polynomials, when the correlation is close to 1. Our proof works by induction on n and yields a new analysis of even the classical Blum-Luby-Rubinfeld [2] linearity test, for the setting of functions mapping F2nto F2. The optimality follows from a tighter analysis of counterexamples to the "inverse conjecture for the Gowers norm" constructed by [3], [4]. Our result has several implications. First, it shows that the Gowers norm test is tolerant, in that it also accepts close codewords. Second, it improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson [5]. Third, it implies a "query hierarchy" result for property testing of affine-invariant properties. That is, for every function q(n), it gives an affine-invariant property that is testable with O(q(n))-queries, but not with o(q(n))-queries, complementing an analogous result of [6] for graph properties.

We show that the list-decodability of random linear codes is as good as that of general random codes. Specifically, for every fixed finite field Fq, p ∈ (0,1-1/q) and ε > 0, we prove that with high probability a random linear code C in Fqn of rate (1-H_q(p)-ε) can be list decoded from a fraction p of errors with lists of size at most O(1/ε). This also answers a basic open question concerning the existence of highly list-decodable linear codes, showing that a list-size of O(1/ε) suffices to have rate within ε of the "list decoding capacity" 1-Hq(p). The best previously known list-size bound was qO(1/ε) (except in the q=2 case where a list-size bound of O(1/ε) was known).

We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson-Guraswami-Sudan bounds. In particular, we show that for arbitrarily large fields FN, |FN| = N, for any ¿ ¿ (0,1), and K = N¿: (1) Existence: there exists a received word wN: FN¿ FNthat agrees with a super-polynomial number of distinct degree K polynomials on ¿ N¿¿points each; (2) Explicit: there exists a polynomial time constructible received word w'N: FN¿ FNthat agrees with a superpolynomial number of distinct degree K polynomials, on ¿2¿(log N)K points each. In both cases, our results improve upon the previous state of the art, which was ¿ N¿/¿ points of agreement for the existence case (proved by Justesen and Hoholdt), and ¿ 2N¿points of agreement for the explicit case (proved by Guruswami and Rudra). Furthermore, for ¿ close to 1 our bound approaches the Guruswami-Sudan bound (which is ¿(N K)) and implies limitations on extending their efficient Reed-Solomon list decoding algorithm to larger decoding radius. Our proof is based on some remarkable properties of sub-space polynomials. Using similar ideas, we then present a family of low rate codes that are efficiently list-decodable beyond the Johnson bound. This leads to an optimal list-decoding algorithm for the family of matrix-codes.

We study the 2-party randomized communication complexity of read-once AC0formulae. For balanced AND-OR trees T with n inputs and depth d, we show that the communication complexity of the function fT(x, y) = T(x omicron y) is Omega(n/4d) where (x omicron y)iis defined so that the resulting tree also has alternating levels of AND and OR gates. For each bit of x, y, the operation omicron is either AND or OR depending on the gate in T to which it is an input. Using this, we show that for general AND-OR trees T with n inputs and depth d, the communication complexity of fT(x, y) is n/2Omega(dlogd). These results generalize classical results on the communication complexity of set-disjointness (where T is an OR -gate) and recent results on the communication complexity of the TRIBES functions (where T is a depth-2 read-once formula). Our techniques build on and extend the information complexity methodology for proving lower bounds on randomized communication complexity. Our analysis for trees of depth d proceeds in two steps: (1) reduction to measuring the information complexity of binary depth-d trees, and (2) proving lower bounds on the information complexity of binary trees. In order to execute this program, we carefully construct input distributions under which both these steps can be carried out simultaneously. We believe the tools we develop will prove useful in further studies of information complexity in particular, and communication complexity in general.

We extend the "method of multiplicities" to get the following results, of interest in combinatorics and randomness extraction. 1) We show that every Kakeya set (a set of points that contains a line in every direction) in Fqnmust be of size at least qn/2n. This bound is tight to within a 2 + o(1) factor for every n as q ? ?, compared to previous bounds that were off by exponential factors in n. 2) We give an improved construction of "randomness mergers". Mergers are seeded functions that take as input ? (possibly correlated) random variables in {0,1}Nand a short random seed, and output a single random variable in {0,1}Nthat is statistically close to having entropy (1 - ?) ? N when one of the ? input variables is distributed uniformly. The seed we require is only (1/?) ? log ?-bits long, which significantly improves upon previous construction of mergers. 3) We show how to construct randomness extractors that use logarithmic length seeds while extracting 1 - o(1) fraction of the min-entropy of the source. Previous results could extract only a constant fraction of the entropy while maintaining logarithmic seed length. The "method of multiplicities", as used in prior work, analyzed subsets of vector spaces over finite fields by constructing somewhat low degree interpolating polynomials that vanish on every point in the subset with high multiplicity. The typical use of this method involved showing that the interpolating polynomial also vanished on some points outside the subset, and then used simple bounds on the number of zeroes to complete the analysis. Our augmentation to this technique is that we prove, under appropriate conditions, that the interpolating polynomial vanishes with high multiplicity outside the set. This novelty leads to significantly tighter analyses. To develop the extended method of multiplicities we provide a number of basic technical results about multiplicity of zeroes of polynomials that may be of general use. For instance, we strengthen the Schwartz-Zippel lemma to show that the expected multiplicity of zeroes of a non-zero degree d polynomial at a random point in Sn, for any finite subset S of the underlying field, is at most d/|S|.

The classical zero-one law for first-order logic on random graphs says that for every first-order property φ in the theory of graphs and every p ∈ (0,1), the probability that the random graph G(n, p) satisfies φ approaches either 0 or 1 as n approaches infinity. It is well known that this law fails to hold for any formalism that can express the parity quantifier: for certain properties, the probability that G(n,p) satisfies the property need not converge, and for others the limit may be strictly between 0 and 1. In this work, we capture the limiting behavior of properties definable in first order logic augmented with the parity quantifier, FOP, over G(n,p), thus eluding the above hurdles. Specifically, we establish the following "modular convergence law": For every FOP sentence φ, there are two explicitly computable rational numbers a0, a1, such that for i ∈ {0,1}, as n approaches infinity, the probability that the random graph G(2n+i, p) satisfies φ approaches ai. Our results also extend appropriately to FO equipped with Modq quantifiers for prime q. In the process of deriving the above theorem, we explore a new question that may be of interest in its own right. Specifically, we study the joint distribution of the subgraph statistics modulo 2 of G(n,p): namely, the number of copies, mod 2, of a fixed number of graphs F1, ..., Fl of bounded size in G(n,p). We first show that every FOP property φ is almost surely determined by subgraph statistics modulo 2 of the above type. Next, we show that the limiting joint distribution of the subgraph statistics modulo 2 depends only on n Mod 2, and we determine this limiting distribution completely. Interestingly, both these steps are based on a common technique using multivariate polynomials over finite fields and, in particular, on a new generalization of the Gowers norm that we introduce. The first step above is analogous to the Razborov-Smolensky method for lower bounds for AC0 with parity gates, yet stronger in certain ways. For instance, it allows us to obtain examples of simple graph properties that are exponentially uncorrelated with every FOP sentence, which is something that is not known for AC.

We study the complexity of deciding whether a given homogeneous multivariate polynomial has a non- trivial root over a finite field. Given a homogeneous algebraic circuit C that computes an n- variate polynomial p(x) of degree d over a finite field Fq, we wish to determine if there exists a nonzero xisinFqnwith C(x)=0. For constant n there are known algorithms for doing this efficiently. However for linear n, the problem becomes NP hard. In this paper, using interesting algebraic techniques, we show that if d is prime and n>d/2, the problem can be solved over sufficiently large finite fields in randomized polynomial time. We complement this result by showing that relaxing any of these constraints makes the problem intractable again.

Given a pair of finite groups G and H, the set of homomorphisms from G to H form an error-correcting code where codewords differ in at least 1/2 the coordinates. We show that for every pair of abelian groups G and H, the resulting code is (locally) list-decodable from a fraction of errors arbitrarily close to its distance. At the heart of this result is the following combinatorial result: There is a fixed polynomial p(•) such that for every pair of abelian groups G and H, if the maximum fraction of agreement between two distinct homomorphisms from G to H is Λ, then for every ε> 0 and every function f:G -> H, the number of homomorphisms that have agreement Λ + ε with f is at most p(1/ε). We thus give a broad class of codes whose list-decoding radius exceeds the "Johnson bound". Examples of such codes are rare in the literature, and for the ones that do exist, "combinatorial" techniques to analyze their list-decodability are limited. Our work is an attempt to add to the body of such techniques. We use the fact that abelian groups decompose into simpler ones and thus codes derived from homomorphisms over abelian groups may be viewed as certain "compositions" of simpler codes. We give techniques to lift list-decoding bounds for the component codes to bounds for the composed code. We believe these techniques may be of general interest.

We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson and Guruswami-Sudan bounds in the works of S.M. Johnson (1962, 1963) and V. Guruswami and M. Sudan (1999). In particular, we show that for arbitrarily large fields FN, |FN| - N, for any delta isin (0,1), and K = Ndelta;: middot Existence: there exists a received word wN: FNrarr FNthat agrees with a super-polynomial number of distinct degree K polynomials on ap Nradicdeltapoints each; middot Explicit: there exists a polynomial time constructible received word w'N: FNrarr FNthat agrees with a super-polynomial number of distinct degree K polynomials, on ap 2radic(log N)K points each. In both cases, our results improve upon the previous state of the art, which was ap Ndelta/delta for the existence case in the work J. Justesen and T. Hoboldt (2001), and ap 2Ndeltafor the explicit one in the work of V. Guruswami and M. Sudan (2005). Furthermore, for delta close to 1 our bound approaches the Guruswami-Sudan bound (which is radicNK) and implies limitations on extending their efficient RS list decoding algorithm to larger decoding radius. Our proof method is surprisingly simple. We work with polynomials that vanish on subspaces of an extension field viewed as a vector space over the base field. These sub-space polynomials are a subclass of linearized polynomials that were first studied by O. Ore (1933, 1934) in the 1930s, and later by coding theorists. For us their main attraction is their sparsity and abundance of roots, virtues that recently won them pivotal roles in probabilistically checkable proofs of proximity in the works of E. Ben-Sasson et al. (2004) and E. Ben-Sasson and M. Sudan (2005) and sub-linear proof verification in the work of E. Ben-Sasson et al. (2005)

The Border Gateway Protocol (BGP), the current inter domain routing protocol in the Internet, has two modes of operation: eBGP (External BGP), used to exchange routing information between autonomous systems, and iBGP (Internal BGP), used to propagate that information within an autonomous system (AS). This paper focuses on the construction of an iBGP session configuration that guarantees two correctness properties - loop-free forwarding paths and complete visibility to all eBGP-learned best routes - while attempting to minimize the number of iBGP sessions (for scalability) and ensuring that the constructed configuration guarantees the two correctness properties even in the face of link failures and IGPpath changes. Our algorithm constructs an iBGP configuration based on route reflectors, a commonly used way to control the number of iBGP sessions. The algorithm, BGPSep, uses the notion of a graph separator, a (small) set of nodes that partition a graph into connected components of roughly equal sizes, recursively applies this idea to the connected components, and produces a route reflector hierarchy and the associated iBGP sessions. We prove thatBGPSep guarantees the desired correctness properties, andevaluate an implementation of the BGPSep algorithm on several real-world and simulated network topologies. Across these topologies, we find that the number of iBGP sessions with is afactor of 2.5 to 5 times smaller than with a \"full mesh\" iBGP, while guaranteeing the desired correctness properties.

We present a novel coding-based technique for answering spatial and spatiotemporal queries on objects moving along a system of curves on the plane such as many road networks. We handle join, range, intercept, and other spatial and spatiotemporal queries under these assumptions, with distances being measured along the trajectories. Most work to date has studied the significantly simpler case of objects moving in straight lines on the plane. Our work is an advance toward solving the problem in its more general form.Central to our approach is an efficient coding technique, based on hypercube embedding, for assigning labels to nodes in the network. The Hamming distance between codes corresponds to the physical distance between nodes, so that we can determine shortest distances in the network extremely quickly. The coding method also efficiently captures many properties of the network relevant to spatial and spatiotemporal queries. Our approach also yields a very effective spatial hashing method for this domain. Our analytical results demonstrate that our methods are space- and time-efficient.We have studied the performance of our method for large planar graphs designed to represent road networks. Experiments show that our methods are efficient and practical.

The fairness and throughput of TCP suffer when it is used in mobile ad hoc networks. This is because TCP wrongly attributes packet losses due to link failures (a consequence of mobility) to congestion. The resulting overall degradation of throughput especially affects connections with a large number of hops, where link failures are more likely; thus, short connections enjoy an unfair advantage. Furthermore, if the IEEE 802.11 MAC protocol is used, the problems are exacerbated due to the protocol-induced capture effect, leading to greater unfairness and a further throughput degradation. We develop a scheme, called split TCP, which separates the TCP functions of congestion control and reliable packet delivery. For any TCP connection, certain nodes along the route take up the role of being proxies for that connection. The proxies buffer packets upon receipt and administer rate control. The buffering enables dropped packets to be recovered from the most recent proxy. The rate control helps in controlling congestion on inter-proxy segments. Thus, we emulate shorter TCP connections and can thereby achieve better parallelism in the network. Simulations show that the use of proxies improves the total throughput by as much as 30% in typical scenarios and reduces unfairness significantly. In terms of an unfairness metric that we introduce, the unfairness decreases from 0.8 to 0.2 (1.0 being the maximum unfairness). We conclude that incorporating TCP proxies is beneficial in terms of improving TCP performance in ad hoc networks.