Shubhangi Saraf

Department of Mathematics and

Department of Computer Science

Hill Centre, Room 426

Rutgers University


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.





Algebraic gems of theoretical computer science (Rutgers University, Fall 2012)



·        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



·        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



St. Johns College

Fergusson College

Swastik Kopparty