Swastik Kopparty
Department of Mathematics &
Department of Computer Science
Hill Center, Room 432,
Rutgers University.
swastik.kopparty@rutgers.edu
swastik.kopparty@gmail.com

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

 

Papers

o   Constant rate PCPs for Circuit-SAT with sublinear query complexity
 with Eli Ben-Sasson, Yohay Kaplan and Or Meir
 (including an appendix by Henning Stichtenoth)
 (video)

o   Explicit subspace designs
 with Venkatesan Guruswami
 (video)

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
 (video)
 

o   List-decoding Multiplicity Codes
 (video)

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
 (video)

 

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

Courses

Algorithms (Spring 2014, Grad)

Topics in Finite Fields (Fall 2013, Grad)

Undergraduate Problem Solving Seminar (Fall 2013)

Topics in Complexity Theory 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)