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)
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