Papers
o
Proximity gaps for ReedSolomon codes
with Eli BenSasson,
Dan Carmon, Yuval Ishai and Shubhangi
Saraf
o
Geometric rank of tensors and subrank
of matrix multiplication
with Guy Moshkovitz
and Jeroen Zuiddam
o
Quasilinear time listdecodable codes for
space bounded channels
with Ronen Shaltiel
and Jad Silbak
o
DEEPFRI: Sampling outside the box improves soundness
with Eli BenSasson,
Lior Goldberg and Shubhangi
Saraf
o
On multilinear forms: bias, correlation and
tensor rank
with Abhishek Bhrushundi,
Prahladh Harsha, Pooya Hatami and Mrinal Kumar
o
On list recovery of high rate tensor codes
with Nicolas Resch, Noga RonZewi, Shubhangi Saraf and Shashwat Silas
o
Improved decoding of folded ReedSolomon and
multiplicity codes
with Noga
RonZewi, Shubhangi Saraf and Mary Wootters
o
Worst case to average case reductions for the distance to a
code
with Eli BenSasson
and Shubhangi Saraf
o
Syndrome decoding of ReedMuller codes and tensor
decomposition over finite fields
with Aditya Potukuchi
o
Nearoptimal approximation algorithm for simultaneous
MAXCUT
with Amey Bhangale, Subhash Khot, Sushant Sachdeva and Deva Thiruvenkatachari
o
Maximally recoverable codes for gridlike topologies
with Parikshit
Gopalan, Guangda Hu, Shubhangi Saraf, Carol Wang and
Sergey Yekhanin
o
Local testing and decoding of highrate
errorcorrecting codes (a survey)
with Shubhangi
Saraf
o
Robust Positioning Patterns
with Ross Berkowitz
o
Locallytestable and locallycorrectable codes
approaching the GilbertVarshamov bound
with Sivakanth
Gopi, Rafael Oliveira, Noga
RonZewi and Shubhangi Saraf
o
On strictly nonzero integervalued charges
with K.P.S. Bhaskara
Rao
o
Decoding ReedMuller codes on product
sets
with John Kim
o
A CauchyDavenport theorem for linear maps
with Simao Herdade and John Kim
o
High rate locallytestable codes with quasipolylogarithmic query complexity
with Or Meir, Noga
RonZewi and Shubhangi Saraf
o
High rate locallycorrectable codes and locallytestable
codes with subpolynomial query complexity
with Or Meir, Noga
RonZewi and Shubhangi
Saraf
o
Indexing necklaces and irreducible polynomials over
finite fields
with Mrinal
Kumar and Mike Saks
(video)
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
Listdecoding algorithms for lifted codes
with Alan Guo
o
Simultaneous approximation of constraint satisfaction
problems
with Amey Bhangale and Sushant Sachdeva
o Efficient indexing of necklaces and irreducible
polynomials over finite fields
with Mrinal Kumar and Mike Saks
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 CircuitSAT with sublinear query
complexity
with Eli BenSasson,
Yohay Kaplan, Or Meir and Henning Stichtenoth
(video)
o
Explicit subspace designs
with Venkatesan
Guruswami
(video)
o
New affineinvariant codes from lifting
with Alan Guo
and Madhu Sudan
o
A new family of locally correctable codes based on
degreelifted algebraic geometry codes
with Eli BenSasson,
Ariel Gabizon, Yohay
Kaplan and Shubhangi Saraf
o
Certifying polynomials for AC^{0}(Parity),
with applications
with Srikanth Srinivasan
(video)
o
Listdecoding Multiplicity Codes
(video)
o
On the complexity of powering in finite fields
(video 1, video 2)
o
Highrate codes with sublineartime decoding
with Shubhangi Saraf and Sergey Yekhanin
(video 1, video
2)
o
On the ListDecodability
of Random Linear Codes
with Venkatesan Guruswami and Johan Håstad
o
Local ListDecoding and Testing of Sparse Random Linear
Codes from HighError
with Shubhangi Saraf
o
Optimal Testing of ReedMuller Codes
with Arnab Bhattacharyya, Grant Schoenebeck, Madhu Sudan and
David Zuckerman
o
Affine Dispersers from Subspace Polynomials
with Eli BenSasson
(video)
o
Random Graphs and the Parity Quantifier
with Phokion Kolaitis
o
Kakeyatype 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 ReadOnce AC^{0} formulae
with T.S. Jayram
and Prasad Raghavendra
o
The Universal Capacity of of
Channels with Given RateDistortion 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 ReedSolomon Codes
with Eli BenSasson
and Jaikumar Radhakrishnan

Local links
CS theory
seminar, discrete
math seminar, discrete math
mailing list,
CS theory
mailing list
Ph.D. Students
Current: Vishvajeet Nagargoje
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
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
Some
open problems about codes (Intractability center)
Errorcorrecting
codes (IAS “mathematical conversation”)
