Shubhangi Saraf
Department of Mathematics and
Department of Computer Science
University of Toronto
Email:
shubhangi.saraf@utoronto.ca
I am a Professor
in the departments of 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 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, an NSERC Discovery grant and a McLean award.
Current Students: Devansh Shringi, Narmada Varadarajan,
Somnath Bhattacharjee, Rishabh Kothary, Artur
Kravtsov
Past students: Deepanshu Kush, Mrinal Kumar, Ben Lund, Charles Wolf, Vishwas Bhargava
Publications
·
Constant-depth circuits for
polynomial GCD over any characteristic
With Somnath
Bhattacharjee, Mrinal Kumar, Shanthanu Rai, Varun
Ramanathan and Ramprasad Saptharishi
·
Closure under factorization
from a result of Furstenberg
With
Somnath Bhattacharjee, Mrinal Kumar, Shanthanu Rai,
Varun Ramanathan and Ramprasad Saptharishi
·
Deterministic factorization
of constant depth algebraic circuits in subexponential
time
With Somnath
Bhattacharjee, Mrinal Kumar, Varun Ramanathan and Ramprasad Saptharishi
FOCS
2025
·
Reconstruction of Depth 3
Arithmetic Circuits with Top Fan-In 3
With
Devansh Shringi
CCC
2025
·
Lower Bounds for
Set-Multilinear Branching Programs
With Prerona Chatterjee, Deepanshu Kush and Amir Shpilka
CCC 2024
·
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