Nikhil Srivastava

Nikhil Srivastava

I am interested in theoretical computer science, linear algebra, random matrices, and convex geometry.

Previously, I was at Princeton, MSRI, IAS, Yale, and Union.

Some 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, SICOMP special issue (2011). [arXiv] [slides]
  6. Twice-Ramanujan Sparsifiers (with J. Batson and D. Spielman), STOC 2009, SICOMP special issue (2012). [arXiv] [slides] [video] and [bourbaki notes] by Assaf Naor.
  7. An Elementary Proof of the Restricted Invertibility Theorem (with D. Spielman), Israel J. Math 190 (2012). [arXiv] [video]
  8. On Contact Points of Convex BodiesGeometric Aspects of Functional Analysis, Springer Lec. Notes in Math. (2012) [PDF] 
  9. Covariance Estimation for Distributions with 2+epsilon Moments (with R. Vershynin), to appear in Annals of Probability. [arXiv] [slides]
  10. Graph Densification (with M. Hardt and M. Tulsiani), ITCS 2012. [PDF]
  11. Zero-One Rounding of Singular Vectors (with A. Deshpande and R. Kannan), ICALP 2012. [PDF]
  12. A New Approach to Computing Maximum Flows using Electrical Flows (with Y. Lee and S. Rao), STOC 2013. [PDF] [slides]
  13. Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees (with A. Marcus and D. Spielman)., FOCS 2013, best paper award. [arXiv] [slides]
  14. Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem (with A. Marcus and D. Spielman). [arXiv] and [blog post]
  15. Spectral Sparsification of Graphs: Theory and Algorithms (with J. Batson, D. Spielman, and S-H. Teng), Communications of the ACM 2013. [PDF] and [technical perspective] by Assaf Naor.

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

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

General Audience Talk on Graph Sparsification: [vimeo] (Kavli Frontiers of Science, Agra 2013)

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

CV [pdf]