All reports by Author Swastik Kopparty:

__
TR24-069
| 8th April 2024
__

Swastik Kopparty, Amnon Ta-Shma, Kedem Yakirevitch#### Character sums over AG codes

__
TR23-177
| 18th November 2023
__

Kiran Kedlaya, Swastik Kopparty#### On the degree of polynomials computing square roots mod p

Revisions: 1

__
TR23-160
| 29th October 2023
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf#### Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes

Revisions: 1

__
TR23-092
| 28th June 2023
__

Swastik Kopparty, Vishvajeet N#### Extracting Mergers and Projections of Partitions

__
TR22-110
| 1st August 2022
__

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit#### Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves

__
TR21-103
| 18th July 2021
__

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit#### Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields

Revisions: 1

__
TR20-083
| 30th May 2020
__

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

Revisions: 3

__
TR20-029
| 6th March 2020
__

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

__
TR19-090
| 27th June 2019
__

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

Revisions: 2

__
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

__
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-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: 3

__
TR15-047
| 2nd April 2015
__

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

__
TR14-001
| 4th January 2014
__

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

__
TR12-044
| 22nd April 2012
__

Swastik Kopparty#### List-Decoding Multiplicity Codes

__
TR10-148
| 23rd September 2010
__

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

__
TR10-044
| 12th March 2010
__

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

__
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-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-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

Swastik Kopparty, Amnon Ta-Shma, Kedem Yakirevitch

The Stepanov-Bombieri proof of the Hasse-Weil bound also gives non-trivial bounds on the bias of character sums over curves with small genus, for any low-degree function $f$ that is not completely biased. For high genus curves, and in particular for curves used in AG codes over constant size fields, the ... more >>>

Kiran Kedlaya, Swastik Kopparty

For an odd prime $p$, we say $f(X) \in {\mathbb F}_p[X]$ computes square roots in $\mathbb F_p$ if, for all nonzero perfect squares $a \in \mathbb F_p$, we have $f(a)^2 = a$.

When $p \equiv 3$ mod $4$, it is well known that $f(X) = X^{(p+1)/4}$ computes square ...
more >>>

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

In this note, we give very simple constructions of unique neighbor expander graphs starting from spectral or combinatorial expander graphs of mild expansion. These constructions and their analysis are simple variants of the constructions of LDPC error-correcting codes from expanders, given by

Sipser-Spielman~\cite{SS96} (and Tanner~\cite{Tanner81}), and their analysis. We also ...
more >>>

Swastik Kopparty, Vishvajeet N

We study the problem of extracting randomness from somewhere random sources, and related combinatorial phenomena: partition analogues of Shearer's lemma on projections.

A somewhere-random source is a tuple $(X_1, \ldots, X_t)$ of (possibly correlated) $\{0,1\}^n$-valued random variables $X_i$ where for some unknown $i \in [t]$, $X_i$ is guaranteed to be ... more >>>

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

Concretely efficient interactive oracle proofs (IOPs) are of interest due to their applications to scaling blockchains, their minimal security assumptions, and their potential future-proof resistance to quantum attacks.

Scalable IOPs, in which prover time scales quasilinearly with the computation size and verifier time scales poly-logarithmically with it, have been known ... more >>>

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

Over finite fields $F_q$ containing a root of unity of smooth order $n$ (smoothness means $n$ is the product of small primes), the Fast Fourier Transform (FFT) leads to the fastest known algebraic algorithms for many basic polynomial operations, such as multiplication, division, interpolation and multi-point evaluation. These operations can ... 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 >>>

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

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

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

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, 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, 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, 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

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, 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 >>>

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

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

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

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

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

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