Results for query **kopparty**:

__
TR20-083
| 30th May 2020
__

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf#### Proximity Gaps for Reed-Solomon Codes

__
TR20-083
| 30th May 2020
__

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf#### Proximity Gaps for Reed-Solomon Codes

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

__
TR20-083
| 30th May 2020
__

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf#### Proximity Gaps for Reed-Solomon Codes

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

__
TR20-083
| 30th May 2020
__

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf#### Proximity Gaps for Reed-Solomon Codes

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

__
TR20-029
| 6th March 2020
__

Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam#### Geometric Rank of Tensors and Subrank of Matrix Multiplication

__
TR20-029
| 6th March 2020
__

Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam#### Geometric Rank of Tensors and Subrank of Matrix Multiplication

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

__
TR20-029
| 6th March 2020
__

Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam#### Geometric Rank of Tensors and Subrank of Matrix Multiplication

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

__
TR19-090
| 27th June 2019
__

Ronen Shaltiel, Swastik Kopparty, Jad Silbak#### Quasilinear time list-decodable codes for space bounded channels

Revisions: 2

__
TR19-090
| 27th June 2019
__

Ronen Shaltiel, Swastik Kopparty, Jad Silbak#### Quasilinear time list-decodable codes for space bounded channels

Revisions: 2
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 ... more >>>

__
TR19-090
| 27th June 2019
__

Ronen Shaltiel, Swastik Kopparty, Jad Silbak#### Quasilinear time list-decodable codes for space bounded channels

Revisions: 2
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 ... more >>>

__
TR19-090
| 27th June 2019
__

Ronen Shaltiel, Swastik Kopparty, Jad Silbak#### Quasilinear time list-decodable codes for space bounded channels

Revisions: 2
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 ... more >>>

__
TR19-080
| 1st June 2019
__

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas#### On List Recovery of High-Rate Tensor Codes

__
TR19-080
| 1st June 2019
__

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas#### On List Recovery of High-Rate Tensor Codes

We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is {\em approximately} locally list recoverable, as well as globally list recoverable ... more >>>

__
TR19-080
| 1st June 2019
__

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas#### On List Recovery of High-Rate Tensor Codes

We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is {\em approximately} locally list recoverable, as well as globally list recoverable ... more >>>

__
TR19-080
| 1st June 2019
__

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas#### On List Recovery of High-Rate Tensor Codes

We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is {\em approximately} locally list recoverable, as well as globally list recoverable ... more >>>

__
TR19-080
| 1st June 2019
__

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas#### On List Recovery of High-Rate Tensor Codes

We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is {\em approximately} locally list recoverable, as well as globally list recoverable ... more >>>

__
TR19-044
| 28th March 2019
__

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf#### DEEP-FRI: Sampling Outside the Box Improves Soundness

Revisions: 2

__
TR19-044
| 28th March 2019
__

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf#### DEEP-FRI: Sampling Outside the Box Improves Soundness

Revisions: 2
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 $\delta$-far in ... more >>>

__
TR19-044
| 28th March 2019
__

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf#### DEEP-FRI: Sampling Outside the Box Improves Soundness

Revisions: 2
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 $\delta$-far in ... more >>>

__
TR19-044
| 28th March 2019
__

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf#### DEEP-FRI: Sampling Outside the Box Improves Soundness

Revisions: 2
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 $\delta$-far in ... more >>>

__
TR19-044
| 28th March 2019
__

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf#### DEEP-FRI: Sampling Outside the Box Improves Soundness

Revisions: 2
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 $\delta$-far in ... more >>>

__
TR19-044
| 28th March 2019
__

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf#### DEEP-FRI: Sampling Outside the Box Improves Soundness

Revisions: 2
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 $\delta$-far in ... more >>>

__
TR18-091
| 4th May 2018
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters#### Improved decoding of Folded Reed-Solomon and Multiplicity Codes

__
TR18-091
| 4th May 2018
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters#### Improved decoding of Folded Reed-Solomon and Multiplicity Codes

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

__
TR18-091
| 4th May 2018
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters#### Improved decoding of Folded Reed-Solomon and Multiplicity Codes

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

__
TR18-091
| 4th May 2018
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters#### Improved decoding of Folded Reed-Solomon and Multiplicity Codes

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

__
TR18-090
| 4th May 2018
__

Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf#### Worst-case to average case reductions for the distance to a code

Revisions: 1

__
TR18-090
| 4th May 2018
__

Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf#### Worst-case to average case reductions for the distance to a code

Revisions: 1
Algebraic proof systems reduce computational problems to problems about estimating the distance of a sequence of functions $u=(u_1,\ldots, u_k)$, given as oracles, from a linear error correcting code $V$. The soundness of such systems relies on methods that act ``locally'' on $u$ and map it to a single function $u^*$ ... more >>>

__
TR18-090
| 4th May 2018
__

Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf#### Worst-case to average case reductions for the distance to a code

Revisions: 1
Algebraic proof systems reduce computational problems to problems about estimating the distance of a sequence of functions $u=(u_1,\ldots, u_k)$, given as oracles, from a linear error correcting code $V$. The soundness of such systems relies on methods that act ``locally'' on $u$ and map it to a single function $u^*$ ... more >>>

__
TR18-081
| 20th April 2018
__

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar#### On Multilinear Forms: Bias, Correlation, and Tensor Rank

Revisions: 1

__
TR18-081
| 20th April 2018
__

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar#### On Multilinear Forms: Bias, Correlation, and Tensor Rank

Revisions: 1

__
TR18-081
| 20th April 2018
__

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar#### On Multilinear Forms: Bias, Correlation, and Tensor Rank

Revisions: 1

__
TR18-081
| 20th April 2018
__

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar#### On Multilinear Forms: Bias, Correlation, and Tensor Rank

Revisions: 1
In this paper, 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 $GF(2)= \{0,1\}$. We show the following results for multilinear forms and tensors.

__
TR17-126
| 7th August 2017
__

Swastik Kopparty, Shubhangi Saraf#### Local Testing and Decoding of High-Rate Error-Correcting Codes

__
TR17-126
| 7th August 2017
__

Swastik Kopparty, Shubhangi Saraf#### Local Testing and Decoding of High-Rate Error-Correcting Codes

__
TR17-126
| 7th August 2017
__

Swastik Kopparty, Shubhangi Saraf#### Local Testing and Decoding of High-Rate Error-Correcting Codes

__
TR16-122
| 11th August 2016
__

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf#### Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound

__
TR15-110
| 8th July 2015
__

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf#### High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity

Revisions: 1

__
TR15-110
| 8th July 2015
__

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf#### High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity

Revisions: 1

__
TR15-110
| 8th July 2015
__

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf#### High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity

Revisions: 1

__
TR15-110
| 8th July 2015
__

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf#### High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity

Revisions: 1

__
TR15-110
| 8th July 2015
__

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf#### High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity

Revisions: 1

__
TR15-110
| 8th July 2015
__

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf#### High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity

Revisions: 1

__
TR15-068
| 21st April 2015
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf#### High rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Revisions: 2

__
TR15-068
| 21st April 2015
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf#### High rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Revisions: 2
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 binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant ... more >>>

__
TR15-068
| 21st April 2015
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf#### High rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Revisions: 2
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 binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant ... more >>>

__
TR15-068
| 21st April 2015
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf#### High rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Revisions: 2
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 binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant ... more >>>

__
TR15-068
| 21st April 2015
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf#### High rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Revisions: 2
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 binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant ... more >>>

__
TR15-047
| 2nd April 2015
__

Swastik Kopparty, Mrinal Kumar, Michael Saks#### Efficient indexing of necklaces and irreducible polynomials over finite fields

__
TR15-047
| 2nd April 2015
__

Swastik Kopparty, Mrinal Kumar, Michael Saks#### Efficient indexing of necklaces and irreducible polynomials over finite fields

We study the problem of indexing irreducible polynomials over finite fields, and give the first efficient algorithm for this problem. Specifically, we show the existence of poly(n, log q)-size circuits that compute a bijection between {1, ... , |S|} and the set S of all irreducible, monic, univariate polynomials of ... more >>>

__
TR14-098
| 30th July 2014
__

Amey Bhangale, Swastik Kopparty, Sushant Sachdeva#### Simultaneous Approximation of Constraint Satisfaction Problems

__
TR14-098
| 30th July 2014
__

Amey Bhangale, Swastik Kopparty, Sushant Sachdeva#### Simultaneous Approximation of Constraint Satisfaction Problems

__
TR14-001
| 4th January 2014
__

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka#### Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization

__
TR14-001
| 4th January 2014
__

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka#### Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization

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 polynomial $f(X_1,\ldots,X_n)$, the task of computing arithmetic circuits for the factors ... more >>>

__
TR14-001
| 4th January 2014
__

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka#### Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization

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 polynomial $f(X_1,\ldots,X_n)$, the task of computing arithmetic circuits for the factors ... more >>>

__
TR13-085
| 13th June 2013
__

Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth#### Constant rate PCPs for circuit-SAT with sublinear query complexity

__
TR13-085
| 13th June 2013
__

Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth#### Constant rate PCPs for circuit-SAT with sublinear query complexity

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

__
TR13-085
| 13th June 2013
__

Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth#### Constant rate PCPs for circuit-SAT with sublinear query complexity

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

__
TR13-085
| 13th June 2013
__

Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth#### Constant rate PCPs for circuit-SAT with sublinear query complexity

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

__
TR13-060
| 10th April 2013
__

Venkatesan Guruswami, Swastik Kopparty#### Explicit Subspace Designs

__
TR13-060
| 10th April 2013
__

Venkatesan Guruswami, Swastik Kopparty#### Explicit Subspace Designs

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf 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 ... more >>>

__
TR13-060
| 10th April 2013
__

Venkatesan Guruswami, Swastik Kopparty#### Explicit Subspace Designs

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf 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 ... more >>>

__
TR13-060
| 10th April 2013
__

Venkatesan Guruswami, Swastik Kopparty#### Explicit Subspace Designs

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf 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 ... more >>>

__
TR13-060
| 10th April 2013
__

Venkatesan Guruswami, Swastik Kopparty#### Explicit Subspace Designs

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf 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 ... more >>>

__
TR13-060
| 10th April 2013
__

Venkatesan Guruswami, Swastik Kopparty#### Explicit Subspace Designs

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf 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 ... more >>>

__
TR12-149
| 8th November 2012
__

Alan Guo, Swastik Kopparty, Madhu Sudan#### New affine-invariant codes from lifting

Comments: 1

__
TR12-149
| 8th November 2012
__

Alan Guo, Swastik Kopparty, Madhu Sudan#### New affine-invariant codes from lifting

Comments: 1

__
TR12-149
| 8th November 2012
__

Alan Guo, Swastik Kopparty, Madhu Sudan#### New affine-invariant codes from lifting

Comments: 1

__
TR12-149
| 8th November 2012
__

Alan Guo, Swastik Kopparty, Madhu Sudan#### New affine-invariant codes from lifting

Comments: 1

__
TR12-149
| 8th November 2012
__

Alan Guo, Swastik Kopparty, Madhu Sudan#### New affine-invariant codes from lifting

Comments: 1

__
TR12-148
| 7th November 2012
__

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf#### A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Revisions: 1

__
TR12-148
| 7th November 2012
__

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf#### A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Revisions: 1
We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry (AG) 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" ... more >>>

__
TR12-148
| 7th November 2012
__

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf#### A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Revisions: 1
We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry (AG) 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" ... more >>>

__
TR12-148
| 7th November 2012
__

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf#### A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Revisions: 1
We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry (AG) 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" ... more >>>

__
TR12-102
| 16th August 2012
__

Swastik Kopparty, Srikanth Srinivasan#### Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ circuits, with applications

__
TR12-102
| 16th August 2012
__

Swastik Kopparty, Srikanth Srinivasan#### Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ circuits, with applications

__
TR12-102
| 16th August 2012
__

Swastik Kopparty, Srikanth Srinivasan#### Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ circuits, with applications

__
TR12-044
| 22nd April 2012
__

Swastik Kopparty#### List-Decoding Multiplicity Codes

__
TR12-044
| 22nd April 2012
__

Swastik Kopparty#### List-Decoding Multiplicity Codes

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

__
TR12-044
| 22nd April 2012
__

Swastik Kopparty#### List-Decoding Multiplicity Codes

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

__
TR12-044
| 22nd April 2012
__

Swastik Kopparty#### List-Decoding Multiplicity Codes

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

__
TR12-044
| 22nd April 2012
__

Swastik Kopparty#### List-Decoding Multiplicity Codes

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

__
TR12-044
| 22nd April 2012
__

Swastik Kopparty#### List-Decoding Multiplicity Codes

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

__
TR12-044
| 22nd April 2012
__

Swastik Kopparty#### List-Decoding Multiplicity Codes

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

__
TR12-044
| 22nd April 2012
__

Swastik Kopparty#### List-Decoding Multiplicity Codes

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

__
TR10-148
| 23rd September 2010
__

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin#### High-rate codes with sublinear-time decoding

__
TR10-148
| 23rd September 2010
__

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin#### High-rate codes with sublinear-time decoding

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

__
TR10-148
| 23rd September 2010
__

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin#### High-rate codes with sublinear-time decoding

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

__
TR10-148
| 23rd September 2010
__

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin#### High-rate codes with sublinear-time decoding

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

__
TR10-148
| 23rd September 2010
__

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin#### High-rate codes with sublinear-time decoding

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

__
TR10-148
| 23rd September 2010
__

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin#### High-rate codes with sublinear-time decoding

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

__
TR10-044
| 12th March 2010
__

Eli Ben-Sasson, Swastik Kopparty#### Affine Dispersers from Subspace Polynomials

__
TR10-044
| 12th March 2010
__

Eli Ben-Sasson, Swastik Kopparty#### Affine Dispersers from Subspace Polynomials

{\em Dispersers} and {\em extractors} for affine sources of dimension $d$ in $\mathbb F_p^n$ --- where $\mathbb F_p$ denotes the finite field of prime size $p$ --- are functions $f: \mathbb F_p^n \rightarrow \mathbb F_p$ that behave pseudorandomly when their domain is restricted to any particular affine space $S \subseteq ... more >>>

__
TR10-044
| 12th March 2010
__

Eli Ben-Sasson, Swastik Kopparty#### Affine Dispersers from Subspace Polynomials

{\em Dispersers} and {\em extractors} for affine sources of dimension $d$ in $\mathbb F_p^n$ --- where $\mathbb F_p$ denotes the finite field of prime size $p$ --- are functions $f: \mathbb F_p^n \rightarrow \mathbb F_p$ that behave pseudorandomly when their domain is restricted to any particular affine space $S \subseteq ... more >>>

__
TR10-003
| 6th January 2010
__

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty#### On the List-Decodability of Random Linear Codes

__
TR10-003
| 6th January 2010
__

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty#### On the List-Decodability of Random Linear Codes

__
TR10-003
| 6th January 2010
__

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty#### On the List-Decodability of Random Linear Codes

__
TR09-115
| 13th November 2009
__

Swastik Kopparty, Shubhangi Saraf#### Local list-decoding and testing of random linear codes from high-error

__
TR09-115
| 13th November 2009
__

Swastik Kopparty, Shubhangi Saraf#### Local list-decoding and testing of random linear codes from high-error

__
TR09-115
| 13th November 2009
__

Swastik Kopparty, Shubhangi Saraf#### Local list-decoding and testing of random linear codes from high-error

__
TR09-086
| 2nd October 2009
__

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman#### Optimal testing of Reed-Muller codes

Revisions: 1

__
TR09-086
| 2nd October 2009
__

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman#### Optimal testing of Reed-Muller codes

Revisions: 1

__
TR09-086
| 2nd October 2009
__

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman#### Optimal testing of Reed-Muller codes

Revisions: 1

__
TR09-086
| 2nd October 2009
__

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman#### Optimal testing of Reed-Muller codes

Revisions: 1

__
TR09-033
| 16th April 2009
__

Phokion G. Kolaitis, Swastik Kopparty#### Random Graphs and the Parity Quantifier

__
TR09-033
| 16th April 2009
__

Phokion G. Kolaitis, Swastik Kopparty#### Random Graphs and the Parity Quantifier

The classical zero-one law for first-order logic on random graphs says that for every first-order property $\varphi$ in the theory of graphs and every $p \in (0,1)$, the probability that the random graph $G(n, p)$ satisfies $\varphi$ approaches either $0$ or $1$ as $n$ approaches infinity. It is well known ... more >>>

__
TR09-033
| 16th April 2009
__

Phokion G. Kolaitis, Swastik Kopparty#### Random Graphs and the Parity Quantifier

The classical zero-one law for first-order logic on random graphs says that for every first-order property $\varphi$ in the theory of graphs and every $p \in (0,1)$, the probability that the random graph $G(n, p)$ satisfies $\varphi$ approaches either $0$ or $1$ as $n$ approaches infinity. It is well known ... more >>>

__
TR09-033
| 16th April 2009
__

Phokion G. Kolaitis, Swastik Kopparty#### Random Graphs and the Parity Quantifier

The classical zero-one law for first-order logic on random graphs says that for every first-order property $\varphi$ in the theory of graphs and every $p \in (0,1)$, the probability that the random graph $G(n, p)$ satisfies $\varphi$ approaches either $0$ or $1$ as $n$ approaches infinity. It is well known ... more >>>

__
TR09-033
| 16th April 2009
__

Phokion G. Kolaitis, Swastik Kopparty#### Random Graphs and the Parity Quantifier

The classical zero-one law for first-order logic on random graphs says that for every first-order property $\varphi$ in the theory of graphs and every $p \in (0,1)$, the probability that the random graph $G(n, p)$ satisfies $\varphi$ approaches either $0$ or $1$ as $n$ approaches infinity. It is well known ... more >>>

__
TR09-004
| 15th January 2009
__

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan#### Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers

Revisions: 2

__
TR09-004
| 15th January 2009
__

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan#### Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers

Revisions: 2

__
TR09-004
| 15th January 2009
__

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan#### Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers

Revisions: 2

__
TR09-004
| 15th January 2009
__

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan#### Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers

Revisions: 2

__
TR08-020
| 7th March 2008
__

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan#### Decodability of Group Homomorphisms beyond the Johnson Bound

__
TR08-020
| 7th March 2008
__

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan#### Decodability of Group Homomorphisms beyond the Johnson Bound

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 {\em abelian} groups $G$ and $H$, the resulting code is (locally) list-decodable from ... more >>>

__
TR08-020
| 7th March 2008
__

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan#### Decodability of Group Homomorphisms beyond the Johnson Bound

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 {\em abelian} groups $G$ and $H$, the resulting code is (locally) list-decodable from ... more >>>

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

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

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

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

Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam

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

Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam

Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam

Ronen Shaltiel, Swastik Kopparty, Jad Silbak

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

Ronen Shaltiel, Swastik Kopparty, Jad Silbak

Ronen Shaltiel, Swastik Kopparty, Jad Silbak

Ronen Shaltiel, Swastik Kopparty, Jad Silbak

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas

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 {\em approximately} locally list recoverable, as well as globally list recoverable ... more >>>

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

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 $\delta$-far in ... more >>>

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

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

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

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

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

Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf

Algebraic proof systems reduce computational problems to problems about estimating the distance of a sequence of functions $u=(u_1,\ldots, u_k)$, given as oracles, from a linear error correcting code $V$. The soundness of such systems relies on methods that act ``locally'' on $u$ and map it to a single function $u^*$ ... more >>>

Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf

Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar

In this paper, 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 $GF(2)= \{0,1\}$. We show the following results for multilinear forms and tensors.

1. Correlation bounds : We show that a random $d$-linear ... more >>>

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar

In this paper, 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 $GF(2)= \{0,1\}$. We show the following results for multilinear forms and tensors.

1. Correlation bounds : We show that a random $d$-linear ... more >>>

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar

In this paper, 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 $GF(2)= \{0,1\}$. We show the following results for multilinear forms and tensors.

1. Correlation bounds : We show that a random $d$-linear ... more >>>

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar

1. Correlation bounds : We show that a random $d$-linear ... more >>>

Swastik Kopparty, Shubhangi Saraf

We survey the state of the art in constructions of locally testable

codes, locally decodable codes and locally correctable codes of high rate.

Swastik Kopparty, Shubhangi Saraf

We survey the state of the art in constructions of locally testable

codes, locally decodable codes and locally correctable codes of high rate.

Swastik Kopparty, Shubhangi Saraf

We survey the state of the art in constructions of locally testable

codes, locally decodable codes and locally correctable codes of high rate.

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, 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 $\delta$ of a binary

code. The best known tradeoff is the Gilbert-Varshamov bound,

and says that for every $\delta \in (0, 1/2)$, there are ...
more >>>

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

An error correcting code is said to be \emph{locally testable} if

there is a test that checks whether a given string is a codeword,

or rather far from the code, by reading only a small number of symbols

of the string. Locally testable codes (LTCs) are both interesting

in their ...
more >>>

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

there is a test that checks whether a given string is a codeword,

or rather far from the code, by reading only a small number of symbols

of the string. Locally testable codes (LTCs) are both interesting

in their ...
more >>>

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

there is a test that checks whether a given string is a codeword,

or rather far from the code, by reading only a small number of symbols

of the string. Locally testable codes (LTCs) are both interesting

in their ...
more >>>

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

there is a test that checks whether a given string is a codeword,

or rather far from the code, by reading only a small number of symbols

of the string. Locally testable codes (LTCs) are both interesting

in their ...
more >>>

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

there is a test that checks whether a given string is a codeword,

or rather far from the code, by reading only a small number of symbols

of the string. Locally testable codes (LTCs) are both interesting

in their ...
more >>>

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

there is a test that checks whether a given string is a codeword,

or rather far from the code, by reading only a small number of symbols

of the string. Locally testable codes (LTCs) are both interesting

in their ...
more >>>

Swastik Kopparty, 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 binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant ... more >>>

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

Swastik Kopparty, Mrinal Kumar, Michael Saks

We study the problem of indexing irreducible polynomials over finite fields, and give the first efficient algorithm for this problem. Specifically, we show the existence of poly(n, log q)-size circuits that compute a bijection between {1, ... , |S|} and the set S of all irreducible, monic, univariate polynomials of ... more >>>

Swastik Kopparty, Mrinal Kumar, Michael Saks

Amey Bhangale, Swastik Kopparty, Sushant Sachdeva

Given $k$ collections of 2SAT clauses on the same set of variables $V$, can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such simultaneous constraint satisfaction problems, and design the first nontrivial approximation algorithms in this context.

Our main result is that ... more >>>

Amey Bhangale, Swastik Kopparty, Sushant Sachdeva

Given $k$ collections of 2SAT clauses on the same set of variables $V$, can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such simultaneous constraint satisfaction problems, and design the first nontrivial approximation algorithms in this context.

Our main result is that ... more >>>

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

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 polynomial $f(X_1,\ldots,X_n)$, the task of computing arithmetic circuits for the factors ... more >>>

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

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

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

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

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

Venkatesan Guruswami, Swastik Kopparty

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf 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 ... more >>>

Venkatesan Guruswami, Swastik Kopparty

Venkatesan Guruswami, Swastik Kopparty

Venkatesan Guruswami, Swastik Kopparty

Venkatesan Guruswami, Swastik Kopparty

Venkatesan Guruswami, Swastik Kopparty

Alan Guo, Swastik Kopparty, Madhu Sudan

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

Alan Guo, Swastik Kopparty, Madhu Sudan

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

Alan Guo, Swastik Kopparty, Madhu Sudan

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

Alan Guo, Swastik Kopparty, Madhu Sudan

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

Alan Guo, Swastik Kopparty, Madhu Sudan

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

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 (AG) 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" ... more >>>

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

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

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

Swastik Kopparty, Srikanth Srinivasan

In this paper, we introduce and develop the method of certifying polynomials for proving $\mathrm{AC}^0[\oplus]$ circuit lower bounds.

We use this method to show that Approximate Majority cannot be computed by $\mathrm{AC}^0[\oplus]$ circuits of size $n^{1+o(1)}$. This implies a separation between the power of $\mathrm{AC}^0[\oplus]$ circuits of near-linear size and ... more >>>

Swastik Kopparty, Srikanth Srinivasan

In this paper, we introduce and develop the method of certifying polynomials for proving $\mathrm{AC}^0[\oplus]$ circuit lower bounds.

We use this method to show that Approximate Majority cannot be computed by $\mathrm{AC}^0[\oplus]$ circuits of size $n^{1+o(1)}$. This implies a separation between the power of $\mathrm{AC}^0[\oplus]$ circuits of near-linear size and ... more >>>

Swastik Kopparty, Srikanth Srinivasan

In this paper, we introduce and develop the method of certifying polynomials for proving $\mathrm{AC}^0[\oplus]$ circuit lower bounds.

We use this method to show that Approximate Majority cannot be computed by $\mathrm{AC}^0[\oplus]$ circuits of size $n^{1+o(1)}$. This implies a separation between the power of $\mathrm{AC}^0[\oplus]$ circuits of near-linear size and ... more >>>

Swastik Kopparty

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

Swastik Kopparty

Swastik Kopparty

Swastik Kopparty

Swastik Kopparty

Swastik Kopparty

Swastik Kopparty

Swastik Kopparty

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

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin

Eli Ben-Sasson, Swastik Kopparty

{\em Dispersers} and {\em extractors} for affine sources of dimension $d$ in $\mathbb F_p^n$ --- where $\mathbb F_p$ denotes the finite field of prime size $p$ --- are functions $f: \mathbb F_p^n \rightarrow \mathbb F_p$ that behave pseudorandomly when their domain is restricted to any particular affine space $S \subseteq ... more >>>

Eli Ben-Sasson, Swastik Kopparty

Eli Ben-Sasson, Swastik Kopparty

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\varepsilon >

0$, we prove that with high probability a random subspace $C$ of

$\F_q^n$ of dimension $(1-H_q(p)-\varepsilon)n$ has the

property that every Hamming ball of radius $pn$ has at most

$O(1/\varepsilon)$ codewords.

This ... more >>>

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\varepsilon >

0$, we prove that with high probability a random subspace $C$ of

$\F_q^n$ of dimension $(1-H_q(p)-\varepsilon)n$ has the

property that every Hamming ball of radius $pn$ has at most

$O(1/\varepsilon)$ codewords.

This ... more >>>

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\varepsilon >

0$, we prove that with high probability a random subspace $C$ of

$\F_q^n$ of dimension $(1-H_q(p)-\varepsilon)n$ has the

property that every Hamming ball of radius $pn$ has at most

$O(1/\varepsilon)$ codewords.

This ... more >>>

Swastik Kopparty, Shubhangi Saraf

In this paper, we give surprisingly efficient algorithms for list-decoding and testing

{\em random} linear codes. Our main result is that random sparse linear codes are locally testable and locally list-decodable

in the {\em high-error} regime with only a {\em constant} number of queries.

More precisely, we show that ...
more >>>

Swastik Kopparty, Shubhangi Saraf

In this paper, we give surprisingly efficient algorithms for list-decoding and testing

{\em random} linear codes. Our main result is that random sparse linear codes are locally testable and locally list-decodable

in the {\em high-error} regime with only a {\em constant} number of queries.

More precisely, we show that ...
more >>>

Swastik Kopparty, Shubhangi Saraf

In this paper, we give surprisingly efficient algorithms for list-decoding and testing

{\em random} linear codes. Our main result is that random sparse linear codes are locally testable and locally list-decodable

in the {\em high-error} regime with only a {\em constant} number of queries.

More precisely, we show that ...
more >>>

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

We consider the problem of testing if a given function

$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial

in $n$ variables, also known as the Reed-Muller testing problem.

Alon et al.~\cite{AKKLR} proposed and analyzed a natural

$2^{d+1}$-query test for this property and showed that it accepts

more >>>

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial

in $n$ variables, also known as the Reed-Muller testing problem.

Alon et al.~\cite{AKKLR} proposed and analyzed a natural

$2^{d+1}$-query test for this property and showed that it accepts

more >>>

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial

in $n$ variables, also known as the Reed-Muller testing problem.

Alon et al.~\cite{AKKLR} proposed and analyzed a natural

$2^{d+1}$-query test for this property and showed that it accepts

more >>>

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial

in $n$ variables, also known as the Reed-Muller testing problem.

Alon et al.~\cite{AKKLR} proposed and analyzed a natural

$2^{d+1}$-query test for this property and showed that it accepts

more >>>

Phokion G. Kolaitis, Swastik Kopparty

The classical zero-one law for first-order logic on random graphs says that for every first-order property $\varphi$ in the theory of graphs and every $p \in (0,1)$, the probability that the random graph $G(n, p)$ satisfies $\varphi$ approaches either $0$ or $1$ as $n$ approaches infinity. It is well known ... more >>>

Phokion G. Kolaitis, Swastik Kopparty

Phokion G. Kolaitis, Swastik Kopparty

Phokion G. Kolaitis, Swastik Kopparty

Phokion G. Kolaitis, Swastik Kopparty

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

We extend the ``method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction.

\begin{enumerate}

\item We show that every Kakeya set in $\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 ...
more >>>

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

\begin{enumerate}

\item We show that every Kakeya set in $\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 ...
more >>>

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

\begin{enumerate}

\item We show that every Kakeya set in $\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 ...
more >>>

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

\begin{enumerate}

\item We show that every Kakeya set in $\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 ...
more >>>

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan

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 {\em abelian} groups $G$ and $H$, the resulting code is (locally) list-decodable from ... more >>>

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan