Shubhangi Saraf
School
of Mathematics
Institute
for Advanced Study
Princeton,
NJ 08540
shubhangi@ias.edu
I am a postdoc in the School of Mathematics, at the
Institute for Advanced Study in Princeton.
Prior to this 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 very excited to be joining the faculty of Rutgers
University in September 2012!
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