I am an associate professor in the Department of Mathematics
and the Department of Computer Science at Rutgers University. Prior to coming
to Rutgers, I was a postdoc in the School of Mathematics, at the Institute for
Advanced Study in Princeton. Even before that I was PhD student in the EECS
department and theory of computation group at MIT. I am extremely fortunate to
have had Madhu Sudan as my
advisor.

I am broadly interested in all areas of theoretical computer
science and discrete mathematics. My research has focused on complexity theory,
algebraic computation, error correcting codes and discrete geometry.

My research is supported by a SLOAN research fellowship, an
NSF CAREER award and the Simons Collaboration of Algorithms and Geometry.

In Spring 2019 I will be on Sabbatical at the Institute for
Advanced Study in Princeton.

Coming soon: CCC 2020

__Teaching__

Computational Complexity (Rutgers University, Fall 2019)

Cryptography (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__

·
__DEEP-FRI:
Sampling Outside the Box Improves Soundness__

With Eli
Ben-Sasson, Lior Goldberg and
Swastik Kopparty

·
__On list
recovery of high-rate tensor codes__

With Swastik
Kopparty, Nicolas Resch, Noga
Ron-Zewi and Shashwat Silas

·
__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 (to
appear)

·
__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