Papers
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
Constant rate PCPs for CircuitSAT with sublinear
query complexity
with Eli BenSasson,
Yohay Kaplan and Or Meir
(including an appendix by 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
