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