Swastik Kopparty
Department of Mathematics and
Department of Computer Science
University of Toronto
swastik.kopparty@utoronto.ca
Research Interests: Theoretical Computer Science, Discrete Mathematics, ErrorCorrecting 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 BenSasson, Dan Carmon and David Levit

Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields
with Eli BenSasson, Dan Carmon and David Levit

Proximity gaps for ReedSolomon codes
with Eli BenSasson, Dan Carmon, Yuval Ishai and Shubhangi Saraf

Geometric rank of tensors and subrank of matrix multiplication
with Guy Moshkovitz and Jeroen Zuiddam

Quasilinear time listdecodable codes for space bounded channels
with Ronen Shaltiel and Jad Silbak

DEEPFRI: Sampling outside the box improves soundness
with Eli BenSasson, 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 RonZewi, Shubhangi Saraf and Shashwat Silas

Improved decoding of folded ReedSolomon and multiplicity codes
with Noga RonZewi, Shubhangi Saraf and Mary Wootters

Worst case to average case reductions for the distance to a code
with Eli BenSasson and Shubhangi Saraf

Syndrome decoding of ReedMuller codes and tensor decomposition over finite fields
with Aditya Potukuchi

Nearoptimal approximation algorithm for simultaneous MAXCUT
with Amey Bhangale, Subhash Khot, Sushant Sachdeva and Deva Thiruvenkatachari

Maximally recoverable codes for gridlike topologies
with Parikshit Gopalan, Guangda Hu, Shubhangi Saraf, Carol Wang and Sergey Yekhanin

Local testing and decoding of highrate errorcorrecting codes (a survey)
with Shubhangi Saraf

Robust Positioning Patterns
with Ross Berkowitz

Locallytestable and locallycorrectable codes approaching the GilbertVarshamov bound
with Sivakanth Gopi, Rafael Oliveira, Noga RonZewi and Shubhangi Saraf

On strictly nonzero integervalued charges
with K.P.S. Bhaskara Rao

Decoding ReedMuller codes on product sets
with John Kim

A CauchyDavenport theorem for linear maps
with Simao Herdade and John Kim

High rate locallycorrectable codes and locallytestable codes with subpolynomial query complexity
with Or Meir, Noga RonZewi 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

Listdecoding 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 CircuitSAT with sublinear query complexity
with Eli BenSasson, Yohay Kaplan, Or Meir and Henning Stichtenoth

Explicit subspace designs
with Venkatesan Guruswami

New affineinvariant codes from lifting
with Alan Guo and Madhu Sudan

A new family of locally correctable codes based on degreelifted algebraic geometry codes
with Eli BenSasson, Ariel Gabizon, Yohay Kaplan and Shubhangi Saraf

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

Listdecoding Multiplicity Codes

On the complexity of powering in finite fields

Highrate codes with sublineartime decoding
with Shubhangi Saraf and Sergey Yekhanin

On the ListDecodability of Random Linear Codes
with Venkatesan Guruswami and Johan Håstad

Local ListDecoding and Testing of Sparse Random Linear Codes from HighError
with Shubhangi Saraf

Optimal Testing of ReedMuller Codes
with Arnab Bhattacharyya, Grant Schoenebeck, Madhu Sudan and David Zuckerman

Affine Dispersers from Subspace Polynomials
with Eli BenSasson

Random Graphs and the Parity Quantifier
with Phokion Kolaitis

Kakeyatype 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 ReadOnce AC0 formulae
with T.S. Jayram and Prasad Raghavendra

The Universal Capacity of of Channels with Given RateDistortion 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 ReedSolomon Codes
with Eli BenSasson and Jaikumar Radhakrishnan

Local links
theory events
PhD Students
Current: Vishvajeet N, 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)
Courses
Courses at Rutgers (links coming soon)
Intro to Discrete Structures (Spring 2021, Undergrad)
Algorithmic Number Theory (Fall 2020, Grad)
Calculus I – Math 151:2224 (Fall 2020, Undergrad)
Topics in Algorithms and Complexity Theory (Spring 2020, Grad)
Topics in Finite Fields (Fall 2019, Grad)
Graph Theory (Fall 2019, Undergrad)
Topics in Complexity and Pseudorandomness (Spring 2018, Grad)
Formal Languages and Automata (Spring 2018, Undergrad)
Combinatorics I (Fall 2017, Grad)
Honors Abstract Algebra (Fall 2017, Undergrad)
Problem Solving Seminar (Fall 2017, Undergrad)
Topics in Complexity and Pseudorandomness (Spring 2017, Grad)
Arithmetic Combinatorics (Fall 2016, Grad)
Problem Solving Seminar (Fall 2016, Undergrad)
ErrorCorrecting Codes (Spring 2016, Grad)
Intro to Discrete Structures I (Spring 2015, Undergrad)
Algorithmic Number Theory (Fall 2014, Grad)
Theory of Numbers (Fall 2014, Undergrad)
Algorithms (Spring 2014, Grad)
Topics in Finite Fields (Fall 2013, Grad)
Problem Solving Seminar (Fall 2013, Undergrad)
Topics in Complexity and Pseudorandomness (Spring 2013, Grad)
Combinatorics I (Fall 2012, Grad)
Problem Solving Seminar (Fall 2012, Undergrad)
Algorithms (Spring 2012, Grad)
Graph Theory (Fall 2011, Grad)
Problem Solving Seminar (Fall 2011, Undergrad)
Videos of miscellaneous talks
Errorcorrecting codes (IAS “mathematical conversation”)
