As of July 2021, I have moved to the
University of Toronto.
Here is my new website.
Teaching
Graph Theory (Rutgers University, Spring
2021)
Graph Theory (Rutgers University, Spring
2020)
Computational Complexity (Rutgers
University, Fall 2019)
Cryptography (Rutgers University, Spring
2018)
Special Topics in Discrete
Mathematics (Rutgers University, Spring
2018)
Computational Complexity (Rutgers
University, Fall 2017)
Graduate Combinatorics II (Rutgers
University, Spring 2017)
Graduate Algorithms (Rutgers University,
Fall 2016)
Advanced Undergraduate Problem
Solving Seminar (Rutgers University, Fall 2016)
Graduate Combinatorics II (Rutgers
University, Spring 2015)
Introduction to Discrete Structures I, CS 205
(Rutgers University, Fall 2014)
Mathematics
Problem Solving Seminar (Rutgers University, Fall 2014)
Topics in Discrete Geometry
(Rutgers University, Spring 2014)
Cryptography (Rutgers University,
Spring 2014)
Computational Complexity
(Rutgers University, Fall 2013)
Graph Theory (Rutgers
University, Spring 2013)
Algebraic gems of theoretical
computer science (Rutgers University, Fall 2012)
Links:
Current Students: Vishwas Bhargava
Past students: Mrinal Kumar, Ben Lund, Charles Wolf,
Publications
·
Reconstruction algorithms
for low-rank tensors and depth-3 multilinear circuits
With Vishwas Bhargava and Ilya Volkovich
STOC 2021
·
Proximity
Gaps for Reed-Solomon Codes
With Eli
Ben-Sasson, Dan Carmon, Yuval Ishai
and Swastik Kopparty
FOCS 2020
·
Reconstruction
of Depth-4 Multilinear Circuits
With Vishwas
Bhargava and Ilya Volkovich
SODA 2020
·
DEEP-FRI:
Sampling Outside the Box Improves Soundness
With Eli
Ben-Sasson, Lior Goldberg and
Swastik Kopparty
ITCS 2020
·
On
list recovery of high-rate tensor codes
With Swastik
Kopparty, Nicolas Resch, Noga
Ron-Zewi and Shashwat Silas
APPROX-RANDOM
2019
·
Deterministic
factorization of sparse polynomials with bounded individual degree
With Vishwas
Bhargava and Ilya Volkovich
FOCS 2018
·
Improved
decoding of Folded Reed-Solomon and Multiplicity Codes
With Swastik
Kopparty, Noga Ron-Zewi and Mary Wootters
FOCS 2018
·
Worst
case to average case reductions for the distance to a code
With Eli
Ben-Sasson and Swastik Kopparty
CCC 2018
·
Towards an algebraic natural proofs barrier via polynomial identity testing
With Joshua Grochow, Mrinal Kumar and Michael Saks
·
Finite field Kakeya
and Nikodym sets in three dimensions
With Ben
Lund and Charles Wolf
SIDMA 2018
·
On the number of
ordinary lines determined by sets in complex space
With Abdul Basit, Zeev Dvir,
Charles Wolf
SOCG 2017
·
Locally testable and Locally
correctable Codes Approaching the Gilbert-Varshamov
Bound
With Sivakanth Gopi, Swastik Kopparty,
Rafael Oliveira and Noga Ron-Zewi
SODA 2017
·
Maximally Recoverable Codes with
Grid-like Topologies
With
Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Carol Wang and Sergey Yekhanin
SODA 2017
·
Local testing and decoding of
high rate error correcting codes
With Swastik
Kopparty
Guest
Column, SIGACT News 2016
·
High-rate locally-testable
codes with quasi-polylogarithmic query complexity
With Swastik
Kopparty, Or Meir and Noga
Ron-Zewi
STOC 2016
(merged with the paper below)
·
High rate locally-correctable and
locally-testable codes with sub-polynomial query complexity
With Swastik
Kopparty, Or Meir and Noga
Ron-Zewi
STOC 2016
(merged with the paper above)
·
Arithmetic circuits with locally low
algebraic rank
With Mrinal
Kumar
CCC 2016
·
Sums of products of polynomials in
few variables : lower bounds and polynomial identity
testing
With Mrinal
Kumar
CCC 2016
·
Incidence Bounds for Block
Designs
With Ben
Lund
SIDMA 2016
·
On the power of homogeneous depth
4 arithmetic circuits
With Mrinal
Kumar
FOCS 2014
·
Lower bounds for approximate LDCs
With Jop Briet, Zeev
Dvir and Guangda Hu
ICALP 2014
·
Equivalence of Polynomial
Identity Testing and Deterministic Multivariate Polynomial Factorization
With Swastik
Kopparty and Amir Shpilka
CCC 2014
·
Recent progress on lower
bounds for arithmetic circuits
CCC 2014 (Invited
article)
·
Superpolynomial
lower bounds for general homogeneous depth 4 arithmetic circuits
With Mrinal
Kumar
ICALP 2014
·
Breaking the Quadratic Barrier for 3-LCCs
over the Reals
With Zeev Dvir and Avi
Wigderson
STOC 2014
·
The Limits of Depth Reduction for
Arithmetic Formulas: It’s all about the top fan-in
With Mrinal
Kumar
STOC 2014
·
Lower Bounds for Depth 4 Homogenous
Circuits with Bounded Top Fanin
With
Mrinal Kumar
ECCC
· Improved Rank Bounds for Design Matrices and a New Proof of
Kelly’s Theorem
With Zeev Dvir and Avi Wigderson
Forum
of Mathematics- Sigma
·
Sylvester-Gallai
Type Theorems for Approximate Collinearity
With
Albert Ai, Zeev Dvir and Avi Wigderson
Forum
of Mathematics- Sigma
· A New Family of Locally Correctable Codes based on Degree Lifted
Algebraic Geometry Codes
With Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan and Swastik Kopparty
STOC
2013
·
The Method of Multiplicities
Ph.D.
Thesis, MIT
·
Tight Lower Bounds for 2-Query
LCCs over Finite Fields
With
Arnab Bhattacharyya, Zeev Dvir
and Amir Shpilka
FOCS
2011
·
Noisy Interpolation
of Sparse Polynomials, and Applications
With
Sergey Yekhanin
CCC
2011
·
Blackbox Identity Testing for Depth-4
Multilinear Circuits
With
Ilya Volkovich
STOC
2011
·
High-rate codes with
sublinear-time decoding
With
Swastik Kopparty and Sergey Yekhanin
STOC
2011
·
Kakeya-type
sets in finite vector spaces
With Swastik Kopparty, Vsevolod F. Lev and
Madhu Sudan
Journal of Algebraic
Combinatorics
· Local list-decoding
and testing of random linear codes from high-error
With Swastik Kopparty
STOC 2010
·
Blackbox
polynomial identity testing for depth-3 circuits
With Neeraj Kayal
FOCS
2009
· Extensions to the method of multiplicities, with
applications to Kakeya sets and mergers
With Zeev Dvir, Swastik Kopparty and Madhu Sudan
FOCS
2009
·
Tolerant linearity testing and
locally testable codes
With Swastik
Kopparty
RANDOM 2009
·
Improved lower bound on the size of Kakeya sets over finite fields
With
Madhu Sudan
Analysis
and PDE, 2008
·
Acute and non-obtuse triangulations of
polyhedral surfaces
European
Journal of Combinatorics, 2009