Swastik Kopparty

Research Interests: Theoretical Computer Science, Discrete Mathematics, Error-Correcting Codes, Complexity Theory, Probabilistic and Interactive Proofs, Finite Fields, Randomness and Pseudorandomness.

Previously, I had been a faculty member at Rutgers University for 10 years. Before that, I did my postdoc at the Institute for Advanced Study, my PhD at MIT, and my undergrad at the University of California, Riverside.

I am a Scientific Advisor to StarkWare.

Papers

• Elliptic Curve Fast Fourier Transform (ECFFT) Part II: Scalable and Transparent Proofs over All Large Fields
          with Eli Ben-Sasson, Dan Carmon and David Levit
  
• Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields
          with Eli Ben-Sasson, Dan Carmon and David Levit
  
• Proximity gaps for Reed-Solomon codes
          with Eli Ben-Sasson, Dan Carmon, Yuval Ishai and Shubhangi Saraf
  
• Geometric rank of tensors and subrank of matrix multiplication
          with Guy Moshkovitz and Jeroen Zuiddam
  
• Quasilinear time list-decodable codes for space bounded channels
          with Ronen Shaltiel and Jad Silbak
  
• DEEP-FRI: Sampling outside the box improves soundness
          with Eli Ben-Sasson, Lior Goldberg and Shubhangi Saraf
  
• On multilinear forms: bias, correlation and tensor rank
          with Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami and Mrinal Kumar
  
• On list recovery of high rate tensor codes
          with Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf and Shashwat Silas
  
• Improved decoding of folded Reed-Solomon and multiplicity codes
          with Noga Ron-Zewi, Shubhangi Saraf and Mary Wootters
  
• Worst case to average case reductions for the distance to a code
          with Eli Ben-Sasson and Shubhangi Saraf
  
• Syndrome decoding of Reed-Muller codes and tensor decomposition over finite fields
          with Aditya Potukuchi
  
• Near-optimal approximation algorithm for simultaneous MAXCUT
          with Amey Bhangale, Subhash Khot, Sushant Sachdeva and Deva Thiruvenkatachari
  
• Maximally recoverable codes for grid-like topologies
          with Parikshit Gopalan, Guangda Hu, Shubhangi Saraf, Carol Wang and Sergey Yekhanin
  
• Local testing and decoding of high-rate error-correcting codes (a survey)
          with Shubhangi Saraf
  
• Robust Positioning Patterns
          with Ross Berkowitz
  
• Locally-testable and locally-correctable codes approaching the Gilbert-Varshamov bound
          with Sivakanth Gopi, Rafael Oliveira, Noga Ron-Zewi and Shubhangi Saraf
  
• On strictly nonzero integer-valued charges
          with K.P.S. Bhaskara Rao
  
• Decoding Reed-Muller codes on product sets
          with John Kim
  
• A Cauchy-Davenport theorem for linear maps
          with Simao Herdade and John Kim
  
• High rate locally-correctable codes and locally-testable codes with subpolynomial query complexity
          with Or Meir, Noga Ron-Zewi and Shubhangi Saraf
  
• Indexing necklaces and irreducible polynomials over finite fields
          with Mrinal Kumar and Mike Saks
  
• The complexity of computing the minimum rank of a sign pattern matrix
          with Amey Bhangale
  
• A local central limit theorem for triangles in a random graph
          with Justin Gilmer
  
• List-decoding algorithms for lifted codes
          with Alan Guo
  
• Simultaneous approximation of constraint satisfaction problems
          with Amey Bhangale and Sushant Sachdeva
  
• Some remarks on multiplicity codes (a survey)
  
• Equivalence of polynomial identity testing and multivariate polynomial factorization
          with Shubhangi Saraf and Amir Shpilka
  
• Roots and coefficients of polynomials over finite fields
          with Qiang Wang
  
• Constant rate PCPs for Circuit-SAT with sublinear query complexity
          with Eli Ben-Sasson, Yohay Kaplan, Or Meir and Henning Stichtenoth
  
• Explicit subspace designs
          with Venkatesan Guruswami
  
• New affine-invariant codes from lifting
          with Alan Guo and Madhu Sudan
  
• 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
  
• Certifying polynomials for AC0(Parity), with applications
          with Srikanth Srinivasan
  
• List-decoding Multiplicity Codes
  
• On the complexity of powering in finite fields
  
• High-rate codes with sublinear-time decoding
          with Shubhangi Saraf and Sergey Yekhanin
  
• On the List-Decodability of Random Linear Codes
          with Venkatesan Guruswami and Johan Håstad
  
• Local List-Decoding and Testing of Sparse Random Linear Codes from High-Error
          with Shubhangi Saraf
  
• Optimal Testing of Reed-Muller Codes
          with Arnab Bhattacharyya, Grant Schoenebeck, Madhu Sudan and David Zuckerman
  
• Affine Dispersers from Subspace Polynomials
          with Eli Ben-Sasson
  
• Random Graphs and the Parity Quantifier
          with Phokion Kolaitis
  
• Kakeya-type sets in finite vector spaces
          with Vsevolod Lev, Shubhangi Saraf and Madhu Sudan
  
• Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers
          with Zeev Dvir, Shubhangi Saraf and Madhu Sudan
  
• Tolerant Linearity Testing and Locally Testable Codes
          with Shubhangi Saraf
  
• On the Communication Complexity of Read-Once AC0 formulae
          with T.S. Jayram and Prasad Raghavendra
  
• The Universal Capacity of of Channels with Given Rate-Distortion in the absence of Common Randomness
          with Mukul Agarwal and Sanjoy Mitter
  
• The Homomorphism Domination Exponent
          with Benjamin Rossman
  
• Detecting Rational Points on Hypersurfaces over Finite Fields
          with Sergey Yekhanin
  
• Decodability of Group Homomorphisms beyond the Johnson Bound
          with Irit Dinur, Elena Grigorescu and Madhu Sudan
  
• The Minimum Rank Problem: a counterexample
          with K.P.S. Bhaskara Rao
  
• Local Decoding and Testing of Group Homomorphisms
          with Elena Grigorescu and Madhu Sudan
  
• Subspace Polynomials and List Decoding of Reed-Solomon Codes
          with Eli Ben-Sasson and Jaikumar Radhakrishnan
  

Local links

theory events

PhD Students

Current: Harry Sha, Gal Gross

Graduated: Brian Garnett (2016), John Kim (2016), Ross Berkowitz (2017), Amey Bhangale (2017), Mrinal Kumar (2017), Danny Scheinerman (2018), Abhishek Bhrushundi (2020), Aditya Potukuchi (2020), Justin Semonsen (2020), Vishvajeet N (2022)

Courses

• Computability and Logic (Winter 2023)
  
• Combinatorial Methods (Winter 2023)
  
• Topics in Error Correcting Codes (Fall 2022)
  
• The Discrete Math Toolkit (Winter 2022)
  
• Formal Languages and Automata (Fall 2021)
  
• Algorithms in Algebra and Number Theory (Fall 2021)
  

Videos of miscellaneous talks

Error-correcting codes (IAS “mathematical conversation”)