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.

__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:__

__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