Description: Macintosh HD:Users:shubhangi:Dropbox:cozo&cozo:sigact lcc ltc survey:sigact survey round 2:tosubmit:IMG_0778.JPGText Box: Shubhangi Saraf
Department of Mathematics and
Department of Computer Science
Hill Center, Room 426
Rutgers University


I am an associate 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 and discrete mathematics. My research has focused on complexity theory, algebraic computation, error correcting codes and discrete geometry.



Computational Complexity (Rutgers University, Fall 2017)

Graduate Combinatorics II (Rutgers University, Spring 2017)

Graduate Algorithms (Rutgers University, Fall 2016)

Advanced Undergraduate Problem Solving Seminar (Rutgers University, Fall 2016)

Graduate Combinatorics II (Rutgers University, Spring 2015)

Introduction to Discrete Structures I, CS 205 (Rutgers University, Fall 2014)

Mathematics Problem Solving Seminar (Rutgers University, Fall 2014)

Topics in Discrete Geometry (Rutgers University, Spring 2014)

Cryptography (Rutgers University, Spring 2014)

Computational Complexity (Rutgers University, Fall 2013)

Graph Theory (Rutgers University, Spring 2013)

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




Rutgers/Dimacs Theory Seminar

Discrete Math Seminar


Students:  Mrinal Kumar, Ben Lund, Charles Wolf




·      Towards an algebraic natural proofs barrier via polynomial identity testing

With Joshua Grochow, Mrinal Kumar and Michael Saks



·      Finite field Kakeya and Nikodym sets in three dimensions

With Ben Lund and Charles Wolf


·      On the number of ordinary lines determined by sets in complex space

With Abdul Basit, Zeev Dvir, Charles Wolf

SOCG 2017


·      Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound

With Sivakanth Gopi, Swastik Kopparty, Rafael Oliveira and Noga Ron-Zewi

SODA 2017


·      Maximally Recoverable Codes with Grid-like Topologies

With Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Carol Wang and Sergey Yekhanin

SODA 2017


·      Local testing and decoding of high rate error correcting codes

With Swastik Kopparty

Guest Column, SIGACT News 2016


·      High-rate locally-testable codes with quasi-polylogarithmic query complexity

With Swastik Kopparty, Or Meir and Noga Ron-Zewi

STOC 2016 (merged with the paper below)


·      High rate locally-correctable and locally-testable codes with sub-polynomial query complexity

With Swastik Kopparty, Or Meir and Noga Ron-Zewi

STOC 2016 (merged with the paper above)


·      Arithmetic circuits with locally low algebraic rank

With Mrinal Kumar

CCC 2016


·      Sums of products of polynomials in few variables : lower bounds and polynomial identity testing

With Mrinal Kumar

CCC 2016


·      Incidence Bounds for Block Designs

With Ben Lund



·      On the power of homogeneous depth 4 arithmetic circuits

With Mrinal Kumar

FOCS 2014


·      Lower bounds for approximate LDCs

With Jop Briet, Zeev Dvir and Guangda Hu

ICALP 2014


·      Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization

With Swastik Kopparty and Amir Shpilka

CCC 2014


·      Recent progress on lower bounds for arithmetic circuits

CCC 2014  (Invited article)


·      Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits

With Mrinal Kumar

ICALP 2014


·      Breaking the Quadratic Barrier for 3-LCCs over the Reals

With Zeev Dvir and Avi Wigderson

STOC 2014


·      The Limits of Depth Reduction for Arithmetic Formulas: It’s all about the top fan-in

With Mrinal Kumar

STOC 2014


·      Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin

With Mrinal Kumar



·       Improved Rank Bounds for Design Matrices and a New Proof of Kelly’s Theorem

With Zeev Dvir and Avi Wigderson

Forum of Mathematics- Sigma


·      Sylvester-Gallai Type Theorems for Approximate Collinearity

With Albert Ai, Zeev Dvir and Avi Wigderson

Forum of Mathematics- Sigma


·       A New Family of Locally Correctable Codes based on Degree Lifted Algebraic Geometry Codes

With Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan and Swastik Kopparty

STOC 2013


·      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


·       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