IMG_1163Swastik Kopparty
Department of Mathematics &
Department of Computer Science
Hill Center, Room 432,
Rutgers University.
(don’t use


I am interested in the Theory of Computing, Error-Correcting Codes, Complexity Theory, Combinatorics, Finite Fields, Randomness and Pseudorandomness.



o   Locally-testable and locally-correctable codes approaching the Gilbert-Varshamov bound
 with Sivakanth Gopi, Rafael Oliveira, Noga Ron-Zewi and Shubhangi Saraf

o   On strictly nonzero integer-valued charges
 with K.P.S. Bhaskara Rao

o   Decoding Reed-Muller codes on product sets
 with John Kim

o   A Cauchy-Davenport theorem for linear maps
 with Simao Herdade and John Kim

o   High rate locally-testable codes with quasipolylogarithmic query complexity
 with Or Meir, Noga Ron-Zewi and Shubhangi Saraf

o   High rate locally-correctable codes and locally-testable codes with subpolynomial query complexity
 with Or Meir, Noga Ron-Zewi and Shubhangi Saraf

o   Indexing necklaces and irreducible polynomials over finite fields
 with Mrinal Kumar and Mike Saks

o   The complexity of computing the minimum rank of a sign pattern matrix
 with Amey Bhangale

o   A local central limit theorem for triangles in a random graph
 with Justin Gilmer

o   List-decoding algorithms for lifted codes
 with Alan Guo

o   Simultaneous approximation of constraint satisfaction problems
 with Amey Bhangale and Sushant Sachdeva

o   Some remarks on multiplicity codes
 (a survey)

o   Equivalence of polynomial identity testing and multivariate polynomial factorization
 with Shubhangi Saraf and Amir Shpilka

o   Roots and coefficients of polynomials over finite fields
 with Qiang Wang

o   Constant rate PCPs for Circuit-SAT with sublinear query complexity
 with Eli Ben-Sasson, Yohay Kaplan, Or Meir and Henning Stichtenoth

o   Explicit subspace designs
 with Venkatesan Guruswami

o   New affine-invariant codes from lifting
 with Alan Guo and Madhu Sudan    


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


o   Certifying polynomials for AC0(Parity), with applications
 with Srikanth Srinivasan

o   List-decoding Multiplicity Codes

o   On the complexity of powering in finite fields
 (video 1, video 2)

o   High-rate codes with sublinear-time decoding

 with Shubhangi Saraf and Sergey Yekhanin
 (video 1, video 2)


o   On the List-Decodability of Random Linear Codes

 with Venkatesan Guruswami and Johan Håstad


o   Local List-Decoding and Testing of Sparse Random Linear Codes from High-Error

 with Shubhangi Saraf


o   Optimal Testing of Reed-Muller Codes

 with Arnab Bhattacharyya, Grant Schoenebeck, Madhu Sudan and David Zuckerman


o   Affine Dispersers from Subspace Polynomials

 with Eli Ben-Sasson


o   Random Graphs and the Parity Quantifier

 with Phokion Kolaitis


o   Kakeya-type sets in finite vector spaces
 with Vsevolod Lev, Shubhangi Saraf and Madhu Sudan

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

 with Zeev Dvir, Shubhangi Saraf and Madhu Sudan


o   Tolerant Linearity Testing and Locally Testable Codes

 with Shubhangi Saraf


o   On the Communication Complexity of Read-Once AC0 formulae

 with T.S. Jayram and Prasad Raghavendra


o   The Universal Capacity of of Channels with Given Rate-Distortion in the absence of Common Randomness

 with Mukul Agarwal and Sanjoy Mitter

o   The Homomorphism Domination Exponent

 with Benjamin Rossman


o   Detecting Rational Points on Hypersurfaces over Finite Fields

 with Sergey Yekhanin


o   Decodability of Group Homomorphisms beyond the Johnson Bound

 with Irit Dinur, Elena Grigorescu and Madhu Sudan


o   The Minimum Rank Problem: a counterexample

 with K.P.S. Bhaskara Rao


o   Local Decoding and Testing of Group Homomorphisms

 with Elena Grigorescu and Madhu Sudan


o   Subspace Polynomials and List Decoding of Reed-Solomon Codes

 with Eli Ben-Sasson and Jaikumar Radhakrishnan


Local links

CS theory seminar, discrete math seminar, discrete math mailing list,
CS theory reading group

Ph.D. Students

Ross Berkowitz, Amey Bhangale, Abhishek Bhrushundi, Brian Garnett, John Kim, Mrinal Kumar


Arithmetic Combinatorics (Fall 2016, Grad)

Undergraduate Problem Solving Seminar (Fall 2016)


Error-Correcting Codes (Spring 2016, Grad)
Intro to Discrete Structures I (Spring 2015)

Algorithmic Number Theory (Fall 2014, Grad)

Theory of Numbers (Fall 2014, Undergrad)

Algorithms (Spring 2014, Grad)

Topics in Finite Fields (Fall 2013, Grad)

Undergraduate Problem Solving Seminar (Fall 2013)

Topics in Complexity and Pseudorandomness (Spring 2013, Grad)

Combinatorics (Fall 2012, Grad)                                          

Undergraduate Problem Solving Seminar (Fall 2012)

Algorithms (Spring 2012, Grad)
Graph Theory (Fall 2011, Grad)
Undergraduate Problem Solving Seminar (Fall 2011)


Videos of miscellaneous talks


Some open problems about codes (Intractability center)

Error-correcting codes (IAS “mathematical conversation”)