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