Swastik Kopparty

STOC Conference 2025 Conference Paper

High Rate Multivariate Polynomial Evaluation Codes

• Swastik Kopparty
• Mrinal Kumar 0001
• Harry Sha

The classical Reed-Muller codes over a finite field F q are based on evaluations of m -variate polynomials of degree at most d over a product set U m , for some d 0. In fact, we give two quite different constructions, and for both we develop efficient decoding algorithms for these codes that can decode from half the minimum distance. The first of these codes is based on evaluating multivariate polynomials on simplex-like sets. The distance of this code is proved via a generalized Schwartz-Zippel lemma on the probability of non-zeroness when evaluating polynomials on sparser subsets of U m – the final bound only depends on the “shape” of the set, and recovers the Schwartz-Zippel bound for the case of the full U m , while still being Ω(1) for much sparser simplex-like subsets of U m . The second of these codes is more algebraic and, surprisingly (to us), has some strong locality properties. It is based on evaluating multivariate polynomials at the intersection points of hyperplanes in general position. It turns out that these evaluation points have many large subsets of collinear points. These subsets form the basis of a simple local characterization, and using some deeper algebraic tools generalizing ideas from Polischuk-Spielman, Raz-Safra, and Ben-Sasson-Sudan, we show that this gives a local test for these codes. Interestingly, the set of evaluation points for these locally testable multivariate polynomial evaluation codes can be as small as O ( d m ), and need not occupy a constant or even noticeable fraction of the full space F q m .

STOC Conference 2025 Conference Paper

Improved PIR Schemes using Matching Vectors and Derivatives

• Fatemeh Ghasemi
• Swastik Kopparty
• Madhu Sudan 0001

In this paper, we construct new t -server Private Information Retrieval (PIR) schemes with communication complexity subpolynomial in the previously best known, for all but finitely many t . Our results are based on combining derivatives (in the spirit of Woodruff-Yekhanin) with the Matching Vector based PIRs of Yekhanin and Efremenko. Previously such a combination was achieved in an ingenious way by Dvir and Gopi, using polynomials and derivatives over certain exotic rings, en route to their fundamental result giving the first 2-server PIR with subpolynomial communication. Our improved PIRs are based on two ingredients: We develop a new and direct approach to combine derivatives with Matching Vector based PIRs. This approach is much simpler than that of Dvir-Gopi: it works over the same field as the original PIRs, and only uses elementary properties of polynomials and derivatives. A key subproblem that arises in the above approach is a higher-order polynomial interpolation problem. We show how “sparse S -decoding polynomials”, a powerful tool from the original constructions of Matching Vector PIRs, can be used to solve this higher-order polynomial interpolation problem using surprisingly few higer-order evaluations. Using the known sparse S -decoding polynomials in combination with our ideas leads to our improved PIRs. Notably, we get a 3-server PIR scheme with communication 2 ( (log n ) 1/3 ) , improving upon the previously best known communication of 2 ( √log n ) due to Efremenko.

SODA Conference 2023 Conference Paper

Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Low-degree Extension in Time O(n log n ) over all Finite Fields

• Eli Ben-Sasson
• Dan Carmon
• Swastik Kopparty
• David Levit

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.

FOCS Conference 2020 Conference Paper

Proximity Gaps for Reed-Solomon Codes

• Eli Ben-Sasson
• Dan Carmon
• Yuval Ishai
• Swastik Kopparty
• Shubhangi Saraf

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 $\delta$ -close to the property in relative Hamming distance or (ii) only a tiny fraction of members are $\delta$ -close to the property. In particular, no set in the collection has roughly half of its members $\delta$ -close to the property and the others $\delta$ -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 $\delta$ 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 $\delta$ smaller than the unique decoding radius. Concretely, if $\delta$ is smaller than half the minimal distance of an RS code $v\subset \mathbb{F}_{q}^{n}$, every affine space is either entirely $\delta$ -close to the code, or alternatively at most an ( $n/q$ )-fraction of it is $\delta$ -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.

FOCS Conference 2019 Conference Paper

Quasilinear Time List-Decodable Codes for Space Bounded Channels

• Jad Silbak
• Swastik Kopparty
• Ronen Shaltiel

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(2 s ) = poly(n c ). In this paper we show that for every constant 0 0, 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.

FOCS Conference 2018 Conference Paper

Improved Decoding of Folded Reed-Solomon and Multiplicity Codes

• Swastik Kopparty
• Noga Ron-Zewi
• Shubhangi Saraf
• Mary Wootters

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.

SODA Conference 2018 Conference Paper

Near-optimal approximation algorithm for simultaneous Max-Cut

• Amey Bhangale
• Subhash Khot
• Swastik Kopparty
• Sushant Sachdeva
• Devanathan Thiruvenkatachari

SODA Conference 2018 Conference Paper

Syndrome decoding of Reed-Muller codes and tensor decomposition over finite fields

• Swastik Kopparty
• Aditya Potukuchi

SODA Conference 2017 Conference Paper

Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound

• Sivakanth Gopi
• Swastik Kopparty
• Rafael Oliveira 0002
• Noga Ron-Zewi
• Shubhangi Saraf

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 = r GV (δ) > 0 (for a certain simple function r GV (·)). 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 < r GV (δ), 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 — ∊)R GV (δ), there exist codes with length n, rate R and minimum distance δ that are locally correctable from fraction errors with O ( n e ) 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.

SODA Conference 2017 Conference Paper

Maximally Recoverable Codes for Grid-like Topologies

• Parikshit Gopalan
• Guangda Hu
• Swastik Kopparty
• Shubhangi Saraf
• Carol Wang
• Sergey Yekhanin

STOC Conference 2016 Conference Paper

High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity

• Swastik Kopparty
• Or Meir
• Noga Ron-Zewi
• Shubhangi Saraf

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(Õ(√log n )) (for LCCs) and (log n ) O (loglog n ) (for LTCs). Previously such codes were known to exist only with Ω( n β ) query complexity (for constant β>0). In addition to having small query complexity, our codes also achieve better trade-offs 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. This has the surprising consequence that asking for a large-alphabet error-correcting code to further be an LCC or LTC with sub-polynomial query complexity does not require any sacrifice in terms of rate and distance! Over the binary alphabet, our codes meet the Zyablov bound. Such trade-offs 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 (LDCs) with the same parameters. Our codes are based on a technique of Alon, Edmonds and Luby. We observe that this technique can be used as a general distance-amplification method, and show that it interacts well with local correctors and testers. We obtain our main results by applying this method to suitably constructed LCCs and LTCs in the non-standard regime of sub-constant relative distance .

SODA Conference 2016 Conference Paper

Robust positioning patterns

• Ross Berkowitz
• Swastik Kopparty

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.

STOC Conference 2013 Conference Paper

A new family of locally correctable codes based on degree-lifted algebraic geometry codes

• Eli Ben-Sasson
• Ariel Gabizon
• Yohay Kaplan
• Swastik Kopparty
• Shubhangi Saraf

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 q m , 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 q 2 . 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.

FOCS Conference 2013 Conference Paper

Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity

• Eli Ben-Sasson
• Yohay Kaplan
• Swastik Kopparty
• Or Meir
• Henning Stichtenoth

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.

FOCS Conference 2013 Conference Paper

Explicit Subspace Designs

• Venkatesan Guruswami
• Swastik Kopparty

A subspace design is a collection {H 1, H 2, .. ., H M } of subspaces of F m q with the property that no low-dimensional subspace W of F q m intersects 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 P W that has several roots for each H that non-trivially intersects W. The construction of P W is 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.

STOC Conference 2011 Conference Paper

High-rate codes with sublinear-time decoding

• Swastik Kopparty
• Shubhangi Saraf
• Sergey Yekhanin

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 exp(1/ε), where k is the length of the message. Furthermore, for codes of rate > 1/2, no nontrivial locality has been achieved.

STOC Conference 2011 Conference Paper

On the complexity of powering in finite fields

• Swastik Kopparty

We study the complexity of computing the k th -power of an element of F 2 n by constant depth arithmetic circuits over F 2 (also known as ACP). Our study encompasses the complexity of basic arithmetic operations such as computing cube-root and computing cubic-residuosity of elements of F 2 n . Our main result is that these problems require exponential size circuits.

STOC Conference 2010 Conference Paper

Local list-decoding and testing of random linear codes from high error

• Swastik Kopparty
• Shubhangi Saraf

STOC Conference 2010 Conference Paper

On the list-decodability of random linear codes

• Venkatesan Guruswami
• Johan Håstad
• Swastik Kopparty

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 F q , p ∈ (0,1-1/q) and ε > 0, we prove that with high probability a random linear code C in F q n 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-H q (p). The best previously known list-size bound was q O(1/ε) (except in the q=2 case where a list-size bound of O(1/ε) was known).

FOCS Conference 2010 Conference Paper

Optimal Testing of Reed-Muller Codes

• Arnab Bhattacharyya 0001
• Swastik Kopparty
• Grant Schoenebeck
• Madhu Sudan 0001
• David Zuckerman

We consider the problem of testing if a given function f: F 2 n → F 2 is 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 2 d+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/(d2 d )). 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 F 2 n to F 2. 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.

STOC Conference 2009 Conference Paper

Affine dispersers from subspace polynomials

• Eli Ben-Sasson
• Swastik Kopparty

An affine disperser over F 2 n for sources of dimension d is a function f: F 2 n → F 2 such that for any affine space S ⊆ F 2 n of dimension at least d, we have {f(s) : s in S} = F 2 . 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 = Ω(n 4/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.

FOCS Conference 2009 Conference Paper

Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers

• Zeev Dvir
• Swastik Kopparty
• Shubhangi Saraf
• Madhu Sudan 0001

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 F q n 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? ?, 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} N and a short random seed, and output a single random variable in {0, 1} N that 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 S n, for any finite subset S of the underlying field, is at most d/|S|.

STOC Conference 2009 Conference Paper

Random graphs and the parity quantifier

• Phokion G. Kolaitis
• Swastik Kopparty

STOC Conference 2008 Conference Paper

Decodability of group homomorphisms beyond the johnson bound

• Irit Dinur
• Elena Grigorescu
• Swastik Kopparty
• Madhu Sudan 0001

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.

FOCS Conference 2006 Conference Paper

Subspace Polynomials and List Decoding of Reed-Solomon Codes

• Eli Ben-Sasson
• Swastik Kopparty
• Jaikumar Radhakrishnan

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 F N, |F N | - N, for any delta isin (0, 1), and K = N delta; : middot Existence: there exists a received word w N: F N rarr F N that agrees with a super-polynomial number of distinct degree K polynomials on ap N radicdelta points each; middot Explicit: there exists a polynomial time constructible received word w' N: F N rarr F N that agrees with a super-polynomial number of distinct degree K polynomials, on ap 2 radic(log N) K points each. In both cases, our results improve upon the previous state of the art, which was ap N delta /delta for the existence case in the work J. Justesen and T. Hoboldt (2001), and ap 2N delta for 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)