I am an associate professor in Computer
Science and Mathematics at the University of Toronto. Prior to this, I was a
faculty member in Computer Science and Mathematics at Rutgers University, and 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 has been supported by a
Sloan Research Fellowship, an NSF CAREER award, the Simons Collaboration on
Algorithms and Geometry and the NSF and an NSERC Discovery grant.

__Teaching__

MAT344:
Introduction to Combinatorics (Fall 2023)

CSC463:
Computational Complexity and Computability (Fall 2023)

CSC2429/MAT1304: Topics in the Theory
of Computation: Algebraic Complexity Theory (Winter 2023)

MAT482: Topics in Mathematics (Linear algebra methods in
combinatorics) (Fall
2022)

CSC463:
Computational Complexity and Computability (Fall 2022)

CSC463:
Computational Complexity and Computability (Winter 2022)

CSC2429
/ MAT1304: Algebraic Gems in
Theoretical Computer Science and Discrete Mathematics (Fall 2021)

MAT344:
Introduction to Combinatorics (Fall 2021)

__Prior Teaching (At Rutgers)__

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)

__Current Students__:
Deepanshu Kush, Devansh Shringi,
Narmada Varadarajan

__Past students:__
Mrinal Kumar, Ben Lund, Charles Wolf, Vishwas Bhargava

__Publications__

·
Near-Optimal
Set-Multilinear Formula Lower Bounds

With
Deepanshu Kush

CCC
2023

·
Linear Independence,
Alternants and Applications

With
Vishwas Bhargava and Ilya Volkovich

STOC
2023

·
Improved Low-Depth Set-Multilinear
Circuit Lower Bounds

With
Deepanshu Kush

CCC
2022

·
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