
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
 Tight Bounds on Plurality (with A. Taylor), IPL 96 (2005). [PDF]
 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]
 On the Longest Path Algorithm for Reconstructing Trees from Distance
Matrices (with L. Reyzin), IPL
101 (2007). [PDF]
 Learning and Verifying Graphs Using Queries, with a Focus on Edge
Counting (with L. Reyzin), ALT 2007. [PDF] [slides]
 Graph Sparsification by Effective Resistances (with D.
Spielman), STOC 2008. To appear in SICOMP.
[arXiv] [slides]
 TwiceRamanujan Sparsifiers (with J. Batson and D.
Spielman), STOC 2009. To appear in SICOMP.
[arXiv]
[slides]
[video]
 An Elementary Proof of the Restricted Invertibility Theorem (with
D. Spielman), to appear in Israel J. Math.
[arXiv] [video]
 On Contact Points of Convex Bodies, to appear in Geometric
Aspects of Functional Analysis, Springer Lec. Notes in Math.
[PDF]
 Covariance Estimation for Distributions with 2+epsilon Moments
(with R. Vershynin), to appear in Annals of Probability. [arXiv]
 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]
