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.

 

CV

 

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

St. Johns College

Fergusson College

Swastik Kopparty