BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Swastik Kopparty

Swastik Kopparty appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational ComplexityInformation Theorymath.COmath.ITmath.NTData Structures and Algorithmsmath.CAmath.GNmath.LOmath.PR

Catalog footprint

What is connected

16works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2026arXiv

Recovering polynomials over finite fields from noisy character values

Let $g(X)$ be a polynomial over a finite field ${\mathbb F}_q$ with degree $o(q^{1/2})$, and let $χ$ be the quadratic residue character. We give a polynomial time algorithm to recover $g(X)$ (up to perfect square factors) given the values of $χ\circ g$ on ${\mathbb F}_q$, with up to a constant fraction of the values having errors. This was previously unknown even for the case of no errors. We give a similar algorithm for additive characters of polynomials over fields of characteristic $2$. This gives the first polynomial time algorithm for decoding dual-BCH codes of polynomial dimension from a constant fraction of errors. Our algorithms use ideas from Stepanov's polynomial method proof of the classical Weil bounds on character sums, as well as from the Berlekamp-Welch decoding algorithm for Reed-Solomon codes. A crucial role is played by what we call *pseudopolynomials*: high degree polynomials, all of whose derivatives behave like low degree polynomials on ${\mathbb F}_q$. Both these results can be viewed as algorithmic versions of the Weil bounds for this setting.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Maximally Recoverable Codes for Grid-like Topologies

The explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Yet, the codes being deployed in practice are fairly short. In this work, we address what we view as the main coding theoretic barrier to deploying longer codes in storage: at large lengths, failures are not independent and correlated failures are inevitable. This motivates designing codes that allow quick data recovery even after large correlated failures, and which have efficient encoding and decoding. We propose that code design for distributed storage be viewed as a two-step process. The first step is choose a topology of the code, which incorporates knowledge about the correlated failures that need to be handled, and ensures local recovery from such failures. In the second step one specifies a code with the chosen topology by choosing coefficients from a finite field. In this step, one tries to balance reliability (which is better over larger fields) with encoding and decoding efficiency (which is better over smaller fields). This work initiates an in-depth study of this reliability/efficiency tradeoff. We consider the field-size needed for achieving maximal recoverability: the strongest reliability possible with a given topology. We propose a family of topologies called grid-like topologies which unify a number of topologies considered both in theory and practice, and prove a collection of results about maximally recoverable codes in such topologies including the first super-polynomial lower bound on the field size.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On strictly nonzero integer-valued charges

A charge (finitely additive measure) defined on a Boolean algebra of sets taking values in a group $G$ is called a strictly nonzero (SNZ) charge if it takes the identity value in $G$ only for the zero element of the Boolean algebra. A study of such charges was initiated by Rudiger Göbel and K.P.S. Bhaskara Rao in 2002. Our main result is a solution to one of the questions posed in that paper: we show that for every cardinal $\aleph$, the Boolean algebra of clopen sets of $\{0,1\}^\aleph$ has a strictly nonzero integer-valued charge. The key lemma that we prove is that there exists a strictly nonzero integer-valued permutation-invariant charge on the Boolean algebra of clopen sets of $\{0,1\}^{\aleph_0}$. Our proof is based on linear-algebraic arguments, as well as certain kinds of polynomial approximations of binomial coefficients. We also show that there is no integer-valued SNZ charge on ${\mathcal{P}}(N)$. Finally, we raise some interesting problems on integer-valued SNZ charges.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Cauchy-Davenport theorem for linear maps

We prove a version of the Cauchy-Davenport theorem for general linear maps. For subsets $A,B$ of the finite field $\mathbb{F}_p$, the classical Cauchy-Davenport theorem gives a lower bound for the size of the sumset $A+B$ in terms of the sizes of the sets $A$ and $B$. Our theorem considers a general linear map $L: \mathbb{F}_p^n \to \mathbb{F}_p^m$, and subsets $A_1, \ldots, A_n \subseteq \mathbb{F}_p$, and gives a lower bound on the size of $L(A_1 \times A_2 \times \ldots \times A_n)$ in terms of the sizes of the sets $A_1, \ldots, A_n$. Our proof uses Alon's Combinatorial Nullstellensatz and a variation of the polynomial method.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Decoding Reed-Muller codes over product sets

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

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

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 degree n over a finite field F_q. This has applications in pseudorandomness, and answers an open question of Alon, Goldreich, Håstad and Peralta[AGHP]. Our approach uses a connection between irreducible polynomials and necklaces ( equivalence classes of strings under cyclic rotation). Along the way, we give the first efficient algorithm for indexing necklaces of a given length over a given alphabet, which may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

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

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 relative distance, and query complexity $\exp(\tilde{O}(\sqrt{\log n}))$. Previously such codes were known to exist only with $Ω(n^β)$ query complexity (for constant $β> 0$), and there were several, quite different, constructions known. Our codes are based on a general distance-amplification method of Alon and Luby~\cite{AL96_codes}. We show that this method interacts well with local correctors and testers, and obtain our main results by applying it to suitably constructed LCCs and LTCs in the non-standard regime of \emph{sub-constant relative distance}. Along the way, we also construct LCCs and LTCs over large alphabets, with the same query complexity $\exp(\tilde{O}(\sqrt{\log n}))$, which additionally have the property of approaching the Singleton bound: 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 $\exp(\tilde{O}(\sqrt{\log n}))$ query complexity does not require any sacrifice in terms of rate and distance! Such a result was previously not known for any $o(n)$ query complexity. Our results on LCCs also immediately give locally-decodable codes (LDCs) with the same parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Some remarks on multiplicity codes

Multiplicity codes are algebraic error-correcting codes generalizing classical polynomial evaluation codes, and are based on evaluating polynomials and their derivatives. This small augmentation confers upon them better local decoding, list-decoding and local list-decoding algorithms than their classical counterparts. We survey what is known about these codes, present some variations and improvements, and finally list some interesting open problems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The complexity of computing the minimum rank of a sign pattern matrix

We show that computing the minimum rank of a sign pattern matrix is NP hard. Our proof is based on a simple but useful connection between minimum ranks of sign pattern matrices and the stretchability problem for pseudolines arrangements. In fact, our hardness result shows that it is already hard to determine if the minimum rank of a sign pattern matrix is $\leq 3$. We complement this by giving a polynomial time algorithm for determining if a given sign pattern matrix has minimum rank $\leq 2$. Our result answers one of the open problems from Linial et al. [Combinatorica, 27(4):439--463, 2007].

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Simultaneous Approximation of Constraint Satisfaction Problems

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 for every CSP $F$, for $k < \tilde{O}(\log^{1/4} n)$, there is a polynomial time constant factor Pareto approximation algorithm for $k$ simultaneous Max-$F$-CSP instances. Our methods are quite general, and we also use them to give an improved approximation factor for simultaneous Max-w-SAT (for $k <\tilde{O}(\log^{1/3} n)$). In contrast, for $k = ω(\log n)$, no nonzero approximation factor for $k$ simultaneous Max-$F$-CSP instances can be achieved in polynomial time (assuming the Exponential Time Hypothesis). These problems are a natural meeting point for the theory of constraint satisfaction problems and multiobjective optimization. We also suggest a number of interesting directions for future research.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

New affine-invariant codes from lifting

In this work we explore error-correcting codes derived from the "lifting" of "affine-invariant" codes. Affine-invariant codes are simply linear codes whose coordinates are a vector space over a field and which are invariant under affine-transformations of the coordinate space. Lifting takes codes defined over a vector space of small dimension and lifts them to higher dimensions by requiring their restriction to every subspace of the original dimension to be a codeword of the code being lifted. While the operation is of interest on its own, this work focusses on new ranges of parameters that can be obtained by such codes, in the context of local correction and testing. In particular we present four interesting ranges of parameters that can be achieved by such lifts, all of which are new in the context of affine-invariance and some may be new even in general. The main highlight is a construction of high-rate codes with sublinear time decoding. The only prior construction of such codes is due to Kopparty, Saraf and Yekhanin \cite{KSY}. All our codes are extremely simple, being just lifts of various parity check codes (codes with one symbol of redundancy), and in the final case, the lift of a Reed-Solomon code. We also present a simple connection between certain lifted codes and lower bounds on the size of "Nikodym sets". Roughly, a Nikodym set in $\mathbb{F}_q^m$ is a set $S$ with the property that every point has a line passing through it which is almost entirely contained in $S$. While previous lower bounds on Nikodym sets were roughly growing as $q^m/2^m$, we use our lifted codes to prove a lower bound of $(1 - o(1))q^m$ for fields of constant characteristic.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Kakeya-type sets in finite vector spaces

For a finite vector space $V$ and a non-negative integer $r\le\dim V$ we estimate the smallest possible size of a subset of $V$, containing a translate of every $r$-dimensional subspace. In particular, we show that if $K\subset V$ is the smallest subset with this property, $n$ denotes the dimension of $V$, and $q$ is the size of the underlying field, then for $r$ bounded and $r<n\le rq^{r-1}$ we have $|V\setminus K|=Θ(nq^{n-r+1})$. This improves previously known bounds $|V\setminus K|=Ω(q^{n-r+1})$ and $|V\setminus K|=O(n^2q^{n-r+1})$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On the List-Decodability of Random Linear Codes

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $ε> 0$, we prove that with high probability a random subspace $C$ of $\F_q^n$ of dimension $(1-H_q(p)-ε)n$ has the property that every Hamming ball of radius $pn$ has at most $O(1/ε)$ codewords. This answers a basic open question concerning the list-decodability of linear codes, showing that a list size of $O(1/ε)$ suffices to have rate within $ε$ of the "capacity" $1-H_q(p)$. Our result matches up to constant factors the list-size achieved by general random codes, and gives an exponential improvement over the best previously known list-size bound of $q^{O(1/ε)}$. The main technical ingredient in our proof is a strong upper bound on the probability that $\ell$ random vectors chosen from a Hamming ball centered at the origin have too many (more than $Θ(\ell)$) vectors from their linear span also belong to the ball.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Optimal Testing of Reed-Muller Codes

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. The Gowers norm is based on a natural 2^{d+1}-query test for this property. Alon et al. [AKKLR05] rediscovered this test and showed that it accepts every degree d polynomial with probability 1, while it rejects functions that are Omega(1)-far with probability Omega(1/(d 2^{d})). We give an asymptotically optimal analysis of this test, and show that it rejects functions that are (even only) Omega(2^{-d})-far with Omega(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 [BLR93] 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 [GT09,LMS08]. 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 [VW07]. 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 [GKNR09] for graph properties.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Homomorphism Domination Exponent

We initiate a study of the homomorphism domination exponent of a pair of graphs F and G, defined as the maximum real number c such that |Hom(F,T)| \geq |Hom(G,T)|^c for every graph T. The problem of determining whether HDE(F,G) \geq 1 is known as the homomorphism domination problem and its decidability is an important open question arising in the theory of relational databases. We investigate the combinatorial and computational properties of the homomorphism domination exponent, proving upper and lower bounds and isolating classes of graphs F and G for which HDE(F,G) is computable. In particular, we present a linear program computing HDE(F,G) in the special case where F is chordal and G is series-parallel.

0 citations0 reviewsNo code linkedOpen access