Nikhil Srivastava
35 Olden St, Princeton NJ 08540.
sn at sc dot notecnirp dot ude, backwards.

I am a postdoc at Princeton/CCI; previously I was a member of MSRI and IAS, and a student at Yale and Union. In Summer 2012, I will join MSR India as a researcher.

I am interested in spectral graph theory, linear algebra, and convex geometry.

Papers

  1. Tight Bounds on Plurality (with A. Taylor), IPL 96 (2005). [PDF]
  2. Voting with Rubber Bands, Weights, and Strings (with D. Cervone, R. Dai, D. Gnoutcheff,
    G. Lanterman, A. Mackenzie, A. Morse, and W. Zwicker), to appear in Mathematical Social Sciences. [LINK]
  3. On the Longest Path Algorithm for Reconstructing Trees from Distance Matrices (with L. Reyzin), IPL 101 (2007). [PDF]
  4. Learning and Verifying Graphs Using Queries, with a Focus on Edge Counting (with L. Reyzin), ALT 2007. [PDF] [slides]
  5. Graph Sparsification by Effective Resistances (with D. Spielman), STOC 2008. To appear in SICOMP. [arXiv] [slides]
  6. Twice-Ramanujan Sparsifiers (with J. Batson and D. Spielman), STOC 2009. To appear in SICOMP. [arXiv] [slides] [video]
  7. An Elementary Proof of the Restricted Invertibility Theorem (with D. Spielman), to appear in Israel J. Math. [arXiv] [video]
  8. On Contact Points of Convex Bodies, to appear in Geometric Aspects of Functional Analysis, Springer Lec. Notes in Math. [PDF]
  9. Covariance Estimation for Distributions with 2+epsilon Moments (with R. Vershynin), to appear in Annals of Probability. [arXiv]
  10. Graph Densification (with M. Hardt and M. Tulsiani), ITCS 2012. [PDF]

Thesis: Spectral Sparsification and Restricted Invertibility [PDF] [slides]
        Advisor: Dan Spielman.

Tutorial: Spectral Sparsification and Geometric Applications, given at MSRI. [1], [2], [3].

Teaching : COS 521 Advanced Algorithms (Princeton, Spring 2012)

CV [PDF]