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)

__Publications__

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

__Links__