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__

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)

__Links:__

__Students__: Mrinal Kumar, Ben Lund, Charles
Wolf

__Publications__

·
__Towards an algebraic natural proofs
barrier via polynomial identity testing__

With Joshua Grochow, Mrinal Kumar and Michael
Saks

·
__On the number of
ordinary lines determined by sets in complex space__

With Abdul Basit, Zeev Dvir,
Charles Wolf

·
__Finite field Kakeya and Nikodym sets
in three dimensions__

With Ben Lund and
Charles Wolf

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

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

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