Shubhangi Saraf

Department of Mathematics and

Department of Computer Science

Hill Centre, Room 426

Rutgers University

shubhangi.saraf@rutgers.edu

 

I am an assistant professor in the Department of Mathematics and the Department of Computer Science at Rutgers University. Prior to coming to Rutgers, I was 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. My research has focused on complexity theory and property testing. More specifically, I am interested in the complexity of arithmetic computation, the role of randomness in computing, and in sublinear-time algorithms for codes and other combinatorial structures.

 

CV

 

Teaching

Algebraic gems of theoretical computer science (Rutgers University, Fall 2012)

Graph Theory (Rutgers University, Spring 2013)

Computational Complexity (Rutgers University, Fall 2013)

Topics in Discrete Geometry (Rutgers University, Spring 2014)

Cryptography (Rutgers University, Spring 2014)

 

 

Links:

Rutgers/Dimacs Theory Seminar

Discrete Math Seminar

 

 

Publications

 

·      On the power of homogeneous depth 4 arithmetic circuits

With Mrinal Kumar

FOCS 2014 (to appear)

 

·      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 (to appear)

 

·      Sylvester-Gallai Type Theorems for Approximate Collinearity

With Albert Ai, Zeev Dvir and Avi Wigderson

Forum of Mathematics- Sigma (to appear)

 

·       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 (to appear)

        

·       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