Text Box: Shubhangi Saraf
Department of Mathematics and
Department of Computer Science

University of Toronto
Email: shubhangi.saraf@utoronto.ca

 

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