Shubhangi Saraf

32-G636, CSAIL, MIT

Cambridge, MA, USA 02139.

shibs@mit.edu

I am a third year PhD student in the EECS department and theory of computation group at MIT, advised by Madhu Sudan. Prior to this, I did my undergrad in the mathematics department, also at MIT. I also spent a year as a math exchange student at the University of Cambridge, UK.

I am interested in problems with an algebraic flavor in computational complexity and pseudorandomness.

Publications

· Blackbox polynomial identity testing for depth-3 circuits

with Neeraj Kayal

FOCS 2009, to appear

· Extensions to the method of multiplicities, with applications to Kakeya sets and mergers

with Zeev Dvir, Swastik Kopparty and Madhu Sudan

FOCS 2009, to appear

· Tolerant linearity testing and locally testable codes

with Swastik Kopparty

RANDOM 2009, to appear

· Improved lower bound on the size of Kakeya sets over finite fields