List of Papers with Commentary

Randomness and Complexity

Random Graphs and the Parity Quantifier
Phokion Kolaitis, Swastik Kopparty. STOC 2009

The remarkable 0-1 law for first order logic on random graphs says that for any first order property of graphs $\mathcal P$, the probability that the random graph G(n, p) (for growing n) has the property $\mathcal P$ approaches either 0 or 1. Since its discovery, 0-1 laws have been generalized to a diverse collection of logics which can express more graph properties than first order logic can. The frequently encountered nemesis to all generalizations is the PARITY barrier: any logic that can express the property "there are an odd number of vertices" cannot obey a 0-1 law. In fact, there is virtually no understanding of the asymptotic behavior on random graphs of any logic facing the PARITY barrier.

This paper studies the power of $FO(\oplus)$, first order logic augmented with the parity quantifier, on random graphs. The parity quantifier $\oplus$ is a quantifier that captures counting mod 2. Almost by definition, $FO(\oplus)$ faces the PARITY barrier. Our main result is a "modular convergence law" which precisely captures the asymptotic behavior of $FO(\oplus)$ on random graphs.

The key ingredients of our result are (1) an algebraic technique, based on a new generalization of an analytic tool called the Gowers norm, for approximating $\textsc{FO}(\oplus)$-properties by low-degree polynomials over finite fields, and (2) an adaptation of the method of quantifier elimination from mathematical logic. The first ingredient has analogies with the Razborov-Smolensky method for lower-bounds for $\textsc{AC}^0(\oplus)$ (the class of polynomial-size, bounded-depth circuits with AND, OR, NOT and parity gates). The Razborov-Smolensky method also involves approximations by low-degree polynomials, although in our case we get a stronger approximation, using lower-degree polynomials. These improvements also allow us to to show that (i) there exist explicit pseudorandom generators that fool $\textsc{FO}(\oplus)$ sentences, and (ii) there exist explicit functions f that are exponentially hard-on-average for $\textsc{FO}(\oplus)$ formulae. Obtaining similar results for all of $\textsc{AC}^0(\oplus)$ is one of the major goals of modern complexity theory.

Our methods also allow us to explore some basic and natural questions about subgraphs of random graphs. Specifically, we study the joint distribution of the subgraph counts mod 2 of small graphs inside a random graph. This study encompasses questions such as: what is the probability that a random graph has an odd number of triangles and an even number of 7-cycles? Via our general approach based on polynomials and Gowers' norms, we essentially characterize this joint distribution, and in particular, we show that the subgraph counts mod 2 of all small connected graphs inside a random graph essentially behave like independent unbiased random bits.

Affine Dispersers from Subspace Polynomials
Eli Ben-Sasson, Swastik Kopparty. STOC 2009

An (n,d)-affine disperser is a function $f : \{0,1\}^n \rightarrow \{0,1\}$, such that for every d-dimensional affine subspace A over $\mathbb{F} _2$, f is not constant when restricted to A. Equivalently, it is a 2-coloring of $\mathbb{F} _2^n$, such that every d-dimensional affine subspace is not monochromatic. Affine dispersers arise in the context of determinstically extracting pure random bits from an impure source of structured randomness.

The probabilistic method shows that a random function $f : \{0,1\}^n \rightarrow \{0,1\}$ is a $(n, O(\log n))$-affine disperser. The whole problem is to find explicit affine dispersers. The best known explicit constructions of affine dispersers were due to Barak-Kindler-Shaltiel-Sudakov-Wigderson and Bourgain, who gave explicit $(n, \delta n)$-affine dispersers for every constant $\delta > 0$ (Bourgain in fact constructs a stronger object called an affine extractor). Both these results rely on recent results from additive combinatorics, most notably the sum-product theorem of Bourgain-Katz-Tao.

This paper constructs explicit affine dispersers for sublinear dimension d. Specifically, it gives a construction of an explicit $(n, n^{1-\epsilon})$-affine disperser for constant $\epsilon > 0$ (we can in fact take $\epsilon = 1/5$). The construction itself is very simple to describe: one views $\{0,1\}^n$ as $\mathbb{F} _{2^m}^s$, and defines f(x) to be the evaluation of a certain simple s-variate polynomial over $\mathbb{F} _{2^m}$ at x. The methods used in the analysis are entirely elementary, and make use of simple-but-powerful algebraic objects called subspace polynomials. One of the key technical ingredients is a different (and in some ways, stronger) incarnation of the sum-product phenomenon: the presence of large subfields in a finite field can be detected in the zero/nonzero-ness of the coefficients of its subspace polynomials.

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

This paper introduces an extension to some powerful algebraic techniques, "the polynomial method" and "the method of multiplicities", to get several results of interest in randomness extraction and combinatorics. These techniques have been at the heart of several major results in coding theory, combinatorics and complexity theory, including the list-decoding of Reed-Solomon codes by Sudan and Guruswami-Sudan, the resolution of the finite field Kakeya conjecture by Dvir, and the subsequent construction of randomness extractors by Dvir-Wigderson. Our extensions further refine these techniques, and lead to near-optimal bounds on the size of Kakeya sets, and the first constructions of randomness extractors with logarithmic seed-length and vanishingly small "entropy loss".

The polynomial method is a general method studying combinatorial properties of subsets of vector spaces. In particular, it can be used to rule out the existence of small sets satisfying some strong algebraic/geometric properties. At the high level, it consists of 3 main steps:

• Interpolation: interpolate a low-degree polynomial vanishing on any purported such set;
• Extrapolation: using the properties of the set, deduce that this polynomial in fact vanishes on many more points in the vector space;
• Contradiction: the abundance of roots of this low-degree polynomial then leads to a contradiction (to the Schwartz-Zippel lemma).

The method of multiplicities augments the interpolation step of the above method by interpolating a low-degree polynomial that vanishes with high multiplicity on each point of the set of interest. This augmentation often leads to tighter analyses.

Our extension develops these methods even further. The 3 steps of the extended method can be summarized as follows:

• Interpolation with high multiplicity: interpolate a low-degree polynomial vanishing on the purported such set with high multiplicity;
• Extrapolation with high multiplicity: using the properties of the set, deduce that this polynomial vanishes with high multiplicity on many more points of the vector space;
• Contradiction with high multiplicity: the abundance of high-multiplicity roots of this low-degree polynomial then leads to a contradiction (to a multiplicity-enhanced version of the Schwartz-Zippel lemma).

We develop a number of basic technical results about derivatives of polynomials and multiplicities needed to implement this method. For instance, we strengthen the Schwartz-Zippel lemma to show that the expected multiplicity of zeroes of a non-zero degree d polynomial at a random point in Sⁿ, for any finite subset S of the underlying field, is at most d/|S|.

Via this extended method of multiplicities, we derive the following results of interest in randomness extraction and combinatorics:

• We show that every Kakeya set (a set of points that contains a line in every direction) in $\mathbb{F} _q^n$ must be of size at least qⁿ/2ⁿ. This bound is tight to within a 2 + o(1) factor for every n as $q \to \infty$, compared to previous bounds that were off by exponential factors in n.
• We give an improved construction of "randomness mergers". Mergers are seeded functions that take as input $\Lambda$ (possibly correlated) random variables in $\{0,1\}^N$ and a short random seed, and output a single random variable in $\{0,1\}^N$ that is statistically close to having entropy $(1-\delta) \cdot N$ when one of the $\Lambda$ input variables is distributed uniformly. The seed we require is only $(1/\delta)\cdot \log \Lambda$-bits long, which significantly improves upon previous construction of mergers.
• Using our new mergers, we show how to construct randomness extractors that use logarithmic length seeds while extracting 1 - o(1) fraction of the min-entropy of the source. Previous results could extract only a constant fraction of the entropy while maintaining logarithmic seed length.

Polynomials uncorrelated with Polynomials
Eli Ben-Sasson, Swastik Kopparty. Manuscript

One of the big challenges facing modern complexity theory is to find functions that are hard-on-average for specific models of computation. A very simple and concrete instance of this challenge is the problem of finding functions which have superpolynomially small correlation with $AC^0(\oplus)$ circuits (constant depth circuits with unbounded fan-in AND, OR, XOR and NOT gates). Through the foundational work of Razborov and Smolensky, this problem reduces to the problem of finding functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which have superpolynomially small correlation with $\mathbb{F} _2$-polynomials of degree ${\rm polylog}(n)$. In this work, we find a simple and natural class of functions that has small correlation with all polynomials of degree d, for $d < \log(n)$. This matches a result of Viola and Wigderson.

Let us describe an example of such a function $f : \{0,1\}^n \rightarrow \{0,1\}$. Identify $\{0,1\}^n$ with the big finite field $\mathbb{F} _{{(2^n)}}$ in an $\mathbb{F} _2$-linear fashion. For $x \in \mathbb{F} _{2^n}$, to compute f(x), first raise x to the $7^{\rm th}$-power, and then take its first bit. We show that this f has exponentially small correlation with degree 2 polynomials. A similar recipe gives functions that have exponentially small correlation with degree d polynomials for every constant d, and vanishingly small correlation with degree d polynomials for $d = O(\log n)$. These functions could potentially have exponentially small correlation with degree d polynomials even for $d = {\rm polylog}(n)$

In the language of coding theory, our results imply a surprising dichotomy, generalizing the classical Carlitz-Uchiyama-Weil theorem, between the dual-BCH codes dBCH(n, t) and the Reed-Muller codes RM(n, d). Specifically, for any constants t, d, any codeword of the dual-BCH code dBCH(n,t) is either (a) a codeword in RM(n, d), or (b) $1/2-2^{-\Omega(n)}$ far from all codewords of RM(n,d).

Coding Theory

Tolerant Linearity Testing and Locally Testable Codes
Swastik Kopparty, Shubhangi Saraf. RANDOM 2009
Local Testing and List Decoding of Random Sparse Linear Codes from High Error
Swastik Kopparty, Shubhangi Saraf. Manuscript, coming soon

A code $C \subseteq \{0,1\}^n$ is said to be locally testable if there is a randomized algorithm A (the "tester"), such that A can determine if a given string $r \in \{0,1\}^n$ (the "received word") is close to some element of C or not by just accessing a constant number of bits of r. Locally testable codes form the combinatorial heart of probabilistically checkable proofs (PCPs) and have been extensively studied. In this series of papers, we studied local testability from a different viewpoint, and thus showed the local testability of several families of codes. One of the striking results this leads to is that random sparse linear codes are locally testable with a constant number of queries even in the presence of $49\%$-noise rate. Local testability at such high noise rate was earlier only known to exist in highly-structured algebraic codes.

In the first paper, we began by reformulating the property of local testability of a code into the problem of linearity testing under a non-uniform distribution. We then studied this generalized linearity testing problem directly. Our main result in this paper was a criterion for linearity to be testable under a given distribution. We then showed that several natural classes of distributions satisfy this criterion, thus showing that linearity is testable under these distributions, and that certain codes associated to these distributions are locally testable. In particular, this gives a simple and short proof of a neat result of Kaufman and Sudan that random sparse linear codes are locally testable from $1\%$-noise rate. We also raised a tantalizing conjecture, that would imply that every sparse linear code is locally testable.

The second paper studies the testability and decodability of random sparse linear codes in the presence of very high noise rates. We show that such codes can be locally tested and locally list-decoded from $(\frac{1}{2}-\epsilon)$-fraction errors using only $\mathop{\rm poly}(\frac{1}{\epsilon})$ queries to the received word, for every $\epsilon > 0$. This improves the result of Kaufman and Sudan mentioned above (which only dealt with the low-noise regime).

We also give sub-exponential time algorithms for list-decoding arbitrary unbiased (but not necessarily sparse) linear codes in the high-error regime. In particular, this yields the first sub-exponential time algorithm even for the problem of (unique-)decoding random linear codes of inverse-polynomial rate from a fixed positive fraction of errors.

On the List Decodability of Random Linear Codes
Venkatesan Guruswami, Johan Håstad, Swastik Kopparty. Manuscript, coming soon

We study the list-decodability of random linear codes near the list-decoding capacity. Given p > 0 and an integer q, let C_{p, q} be the list-decoding capacity for p-fraction errors over q-ary alphabets; namely (1) for every R < C_p,q, there is a q-ary code $\mathcal C$ of rate R such that $\mathcal C$ can be list-decoded from p-fraction errors with bounded list-size, and (2) for every R > C_p,q, for every binary code $\mathcal C$ of rate R, $\mathcal C$ cannot be list-decoded from p-fraction errors with bounded list-size.

The classical example of a highly list-decodable q-ary code $\mathcal C$ of rate $R = C_{p,q} - \epsilon$ approaching the list-decoding capacity is a random nonlinear code, for which it is known that with high probability, $\mathcal C$ is list-decodable from p-fraction errors with $O(\frac{1}{\epsilon})$ list-size. On the other hand, for random q-ary linear codes of rate $R = C_{p,q} - \epsilon$, the best known list-size bound for list-decoding from p-fraction errors was as bad as exponential in ${\frac{1}{\epsilon}}$ (in fact, for q > 2, even the existence of a linear code with such good list-decodability was unknown). The goal of this work is to address this rare disparity between the power of general codes and linear codes.

We show that for every prime power q and every $p \in (0,1 - 1/q)$, there is indeed a $O(\frac{1}{\epsilon})$ bound on the list size for list decoding random q-ary linear codes of rate $C_{p,q} - \epsilon$ from p-fraction errors. In particular, we give a high-probability version of the theorem of Guruswami, Håstad, Sudan and Zuckerman, which showed the existence of such linear codes for q = 2. 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 $\Theta(\ell)$) vectors from their linear span also belong to the ball. This "limited correlation" between linear subspaces and Hamming balls seems like a basic and powerful probabilistic fact that might find other applications.

Subspace Polynomials and List-Decoding of Reed-Solomon Codes
Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan. FOCS 2006

The Reed-Solomon code RS[N,K] is a simple algebraic code based on univariate polynomials, and occupies a central place in coding theory and complexity theory. A codeword of RS[N,K] is the vector of evaluations at N distinct points, of all degree K univariate polynomials over a finite field. The seminal work of Sudan and Gursuwami-Sudan gave an efficient algorithm for list-decoding Reed-Solomon codes; the algorithm could correct errors even when nearly all the symbols of codeword got corrupted! This algorithm had an enormous impact on coding theory and complexity theory, with applications to hardness amplification, pseudorandom generators and extractors.

Quantitatively, the Guruswami-Sudan algorithm list-decodes Reed-Solomon codes RS[N,K] from $\sqrt{NK}$ agreements; i.e., given any received word, the algorithm finds all codewords of RS[N,K] that have agreement at least $\sqrt{NK}$ with the received word. In terms of the rate, the algorithm list-decodes codes of rate R from R^1/2-fraction agreements. Given the ubiquity of the Guruswami-Sudan algorithm, it is natural to ask if the algorithm can be made to recover from more errors; can the required agreement for the Guruswami-Sudan list-decoding algorithm be reduced?

This paper gave the first (and till date, only) progress on this question. We show that when list decoding from a radius that is slightly more than the Guruswami-Sudan radius, the number of codewords in the list could become superpolynomial, thus ruling out the possibility of polynomial time algorithms for list-decoding in this regime. Concretely, if one considers the code RS[N,K] with K = N^0.8, then the Guruswami-Sudan algorithm can list-decode from N^0.9-fraction agreements, while our result shows that list-decoding from N^0.894-fraction agreements could lead to superpolynomial size lists. One implication of our results is that for every $\epsilon > 0$, there is no polynomial-time algorithm that list decodes Reed-Solomon codes of rate R from $R^{1/2 + \epsilon}$-fraction agreements.

Our proof employs a magical family of polynomials called subspace polynomials. The critical feature of these polynomials is that they are simultaneously sparse and have an abundance of roots, a rare occurrence of structure in the jungle of polynomials over finite fields.

Decoding of Group Homomorphisms beyond the Johnson bound
Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan. STOC 2008
Local Decoding and Testing of Homomorphisms
Elena Grigorescu, Swastik Kopparty, Madhu Sudan. RANDOM 2006

In this series of papers, we studied the local list-decodability of Hadamard-like codes associated to general abelian groups G and H, and generalized the Goldreich-Levin local list-decoding algorithm for the Hadamard code uniformly to all these codes. The Hadamard code is a binary code of distance 1/2. The codewords of the Hadamard code are precisely the group homomorphisms, or linear functions, between the groups ${\mathbb Z}_2^n$ and ${\mathbb Z}_2$. For general groups G and H, we study the analogous code $\mathsf {Hom}(G,H)$, the set of all group homomorphisms from G to H.

We show that for every pair of abelian groups G and H, the code $\mathsf {Hom}(G,H)$ is locally list-decodable from a fraction of errors arbitrarily close to its distance. At the heart of this result is the corresponding combinatorial list-decodability bound: There is a fixed polynomial $p(\cdot)$ such that for every pair of abelian groups G and H, if the minimum distance of the code $\mathsf {Hom}(G,H)$ is $\Delta$, then for every $\epsilon > 0$ and every function $f:G\to H$, the number of homomorphisms within distance $\Delta - \epsilon$ from f is at most $p(1/\epsilon)$. In the earlier paper, this result was proved with the weakness that the polynomial $p(\cdot)$ depending on H.

We thus give a broad class of codes whose list-decoding radius exceeds the "Johnson bound". Examples of such codes are rare in the literature, and for the ones that do exist, "combinatorial" techniques to analyze their list-decodability are limited. Our work is an attempt to add to the body of such techniques. We use the fact that abelian groups decompose into simpler ones and thus codes derived from homomorphisms over abelian groups may be viewed as certain "compositions" of simpler codes. We give techniques to lift list-decoding bounds for the component codes to bounds for the composed code. We believe these techniques may be of general interest.

Recently, Gopalan, Guruswami and Raghavendra gave another proof of this result for $G = \mathbb{F} _p^n$ and $H = \mathbb{F} _p^m$ with near-optimal quantitative parameters, and generalized it to arbitrary "interleaved" codes.

Optimal testing of Reed-Muller Codes
Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman. Manuscript

We consider the problem of testing if a given function f mapping $\mathbb{F} _2^n$ to $\mathbb{F} _2$, is close to some degree d polynomial over $\mathbb{F} _2$ in n variables, also known as the Reed-Muller testing problem. Alon, Kaufman, Krivilevich, Litsyn and Ron proposed and analyzed a natural 2^d+1-query test for this property, and showed that the test accepts every degree d polynomial with probability 1, while rejecting functions that are $\Omega(1)$-far with probability $\Omega(1/(d 2^{d}))$. We give an asymptotically optimal analysis of their test, showing 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).

Our proof works by induction on n, and yields a new analysis of even the classical Blum-Luby-Rubinfeld linearity test, for the setting of functions mapping $\mathbb{F} _2^n$ to $\mathbb{F} _2$. The optimality follows from a tighter analysis of counterexamples to the "inverse conjecture for the Gowers norm" constructed by Lovett-Meshulam-Samorodnitsky and Green-Tao.

Our result gives a new relationship between the $(d+1)^{\rm {st}}$-Gowers norm of a function and its maximal correlation with degree d polynomials. For functions highly correlated with degree d polynomials, this relationship is asymptotically optimal. Our improved analysis of the AKKLR-test also improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson. Finally, the optimality of our result also implies a "query-hierarchy" result for property testing of linear-invariant properties: For every function q(n), it gives a linear-invariant property that is testable with O(q(n))-queries, but not with o(q(n))-queries, complementing an analogous result of Goldreich-Krivilevich-Newman-Rozenberg for graph properties.

Local List Decoding of Reed-Muller Codes over Large Fields upto the Johnson Radius
Kristian Brander, Swastik Kopparty. Manuscript, coming soon

In this note, we show how to locally list-decode Reed-Muller codes over large fields upto the Johnson radius. Our algorithm is a variant of the ingenious local list-decoding algorithm of Sudan, Trevisan and Vadhan, where the agreement required was a constant factor more than what our algorithm requires.

Assorted Theory

On the Communication Complexity of Read-Once AC⁰ formulae
T.S. Jayram, Swastik Kopparty, Prasad Raghavendra. CCC 2009

We study the 2-party randomized communication complexity of read-once $\textsc{AC}^0$ formulae. For balanced AND-OR trees T with n inputs, depth d, and OR gates at the bottom layer, we show that the communication complexity of the function $f^T(x,y) = T(x \wedge y)$ is $\Omega(n/4^d)$, where $x\wedge y$ is the bit-wise AND of x and y. Using this, we show that for general AND-OR trees T with n inputs and depth d, the communication complexity of f^T(x,y) is $n/2^{\Omega(d\log d)}$. These results generalize the classical results on the communication complexity of set-disjointness due to Kalyansundaram-Schnitger and Razborov, (where T is an OR-gate) and recent a recent result of Jayram-Kumar-Sivakumar on the communication complexity of the ${\sc Tribes}$ functions (where T is a depth-2 read-once formula).

Our techniques build on and extend the information complexity methodology for proving lower bounds on randomized communication complexity. Our analysis for trees of depth d proceeds in two steps: (1) reduction to measuring the information complexity of binary depth-d trees, and (2) proving lower bounds on the information complexity of binary trees. In order to execute this program, we carefully construct input distributions under which both these steps can be carried out simultaneously. We believe the tools we develop will prove useful in further studies of information complexity in particular, and communication complexity in general.

Similar results were obtained independently and simultaneously by Leonardos and Saks.

The Homomorphism Domination Exponent
Swastik Kopparty, Benjamin Rossman. Submitted

A well known corollary of the Kruskal-Katona theorem states that a graph with e edges can have at most e^3/2 triangles. More generally one may ask: given two graphs F and G, if we know that a third graph T has a copies of F as a subgraph, what can we say about the number of copies of G in T? This paper is an attempt to pursue a systematic study of a general question of this type.

We initiate a study of the homomorphism domination exponent of a pair of graphs F and G, $\mathsf{hde}(F,G)$, defined as the maximum real number c such that $\vert\mathsf {Hom}(F,T)\vert \ge \vert\mathsf {Hom}(G,T)\vert^c$ for every graph T (where $\mathsf {Hom}(H_1, H_2)$ denotes the set of homomorphisms from H₁ to H₂). The problem of determining whether $\mathsf{hde}(F,G) \ge 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 $\mathsf{hde}(F,G)$ is computable. In particular, we present a linear program computing $\mathsf{hde}(F,G)$ in the special case where F is chordal and G is series-parallel. In particular, this includes the case of both F and G being trees, where decidability of the homomorphism domination problem was unknown prior to this work.

Detecting Rational Points on Hypersurfaces over Finite Fields
Swastik Kopparty, Sergey Yekhanin. CCC 2008

Given a homogeneous polynomial p(X) over $\mathbb{F} _q$ in n variables and degree d, consider the projective hypersurface of $\mathbb{F} _q$-rational points, $V_p = \{x \in \mathbb P\mathbb{F} _q^n: p(x) = 0\}$, defined by p(X). This paper studies the problem of efficiently determining whether V_p is nonempty. This is equivalent to deciding whether there is an $x \in \mathbb{F} _q^n$, with $x \neq \vec{0}$, such that p(x) = 0. For unrestricted n, d and q, this problem is $\textsc{NP}$-hard.

Let us impose the following (strange) conditions on n, d and q:

• d is a prime,
• d < 2n
• $q \geq \Omega(n^4)$.

Our main result is that under these conditions, given black-box access to evaluations of p, we can decide whether V_p is nonempty in randomized time polynomial in n, d and $\log q$. Furthermore, relaxing any one of these conditions, makes the question $\textsc{NP}$-hard again. In particular, "2" cannot be replaced by " $2+\epsilon$" for any $\epsilon > 0$, we cannot drop the condition that d is prime, nor can we allow q to be constant!

Given access to merely $\mathrm{poly}(n, d, \log q)$ evaluations of p(X), our algorithm infers the existence of a nontrivial root of p(X), without actually finding one. This inference is made by exploiting the rich algebraic structure of polynomials and their factorization patterns.

The Universal Capacity of Channels with Given Rate-Distortion in the absence of Common Randomness
Mukul Agarwal, Swastik Kopparty, Sanjoy Mitter. Allerton 2009

Recently Agarwal, Mitter and Sahai studied the universal capacity of a set of channels where each channel in the set communicates a random source to within a distortion level D, in the model where the transmitter and receiver have access to common randomness. This paper studies the universal capacity for this channel set in the case when there is no access to common randomness. We show that when the distortion level D is positive, the universal capacity is 0.

A framework for Pursuit-Evasion Games in Rⁿ
Swastik Kopparty, Chinya Ravishankar. IPL 2005

We present a framework for solving pursuit evasion games in $\mathbb R^n$ for the case of N pursuers and a single evader. We give two algorithms that capture the evader in a number of steps linear in the original pursuer-evader distances. We also show how to generalize our results to a convex playing field with finitely many hyperplane boundaries that serve as obstacles.

The one-pursuer version of this problem played on the positive quadrant in $\mathbb R^2$, is known as David Gale's Lion and Man problem, and was given a very elegant solution by Sgall. We show that a limiting version of his algorithm allows multiple pursuers to achieve pursuit quickly over all of $\mathbb R^n$.

The minimum rank problem: a counterexample
Swastik Kopparty, K. P. S. Bhaskara Rao. Linear Algebra and its Applications, 2008

We provide a counterexample to a recent conjecture of Arav, Hall, Li, Koyoncu and Rao, which states that the minimum rank, over the reals, of every sign-pattern matrix can be realized by a rational matrix. Our proof uses one of the equivalences of the conjecture and some constructions in projective geometry due to Maclane. As a consequence of the counterexample, we show that there is a graph for which the minimum rank over the reals is strictly smaller than the minimum rank over the rationals. We also make some comments on the minimum rank of sign pattern matrices over different subfields of $\mathbb R$.

Assorted Systems

How to Construct a Correct and Scalable iBGP Configuration
Mythili Vutukuru, Paul Valiant, Swastik Kopparty, Hari Balakrishnan. INFOCOM 2006

This paper presents, analyzes and experimentally evaluates the first (to our knowledge) algorithm to construct an iBGP session configuration that is both provably correct and uses significantly fewer iBGP sessions than a full mesh. The algorithm uses the notion of a graph separator - a small set of nodes whose removal partitions a graph into connected components of roughly equal sizes - to choose route reflectors and iBGP sessions in a way that guarantees correctness.

Roads, Codes and Spatiotemporal Queries
Sandeep Gupta, Swastik Kopparty, Chinya Ravishankar. PODS 2004

We present a novel coding-based technique for answering spatial and spatiotemporal queries on objects moving along a system of curves on the plane such as many road networks. We handle join, range, intercept, and other spatial and spatiotemporal queries under these assumptions, with distances being measured along the trajectories. Most work to date has studied the significantly simpler case of objects moving in straight lines on the plane. Our work is an advance toward solving the problem in its more general form.

Split-TCP for Mobile Ad-hoc Networks
Swastik Kopparty, Srikanth V. Krishnamurthy, Michalis Faloutsos, Satish K. Tripathi. GLOBECOM 2002

This paper defines a variant of TCP which experimentally performs better than standard TCP on mobile ad-hoc networks.