PUBLICATIONS


Monographs and Expository


  1. Bullet Zeros of Polynomials and their Applications to Theory: A Primer. [pdf]

Nisheeth K. Vishnoi


  1. Bullet Faster Algorithms via Approximation Theory. [pdf]

Sushant Sachdeva, Nisheeth K. Vishnoi

Foundations and Trends in Theoretical Computer Science, Volume 9, Issue 2, 2013.


  1. Bullet Evolution without sex, drugs and Boolean functions. [pdf]

Nisheeth K. Vishnoi


  1. Bullet Lx=b    (Laplacian Solvers and Their Algorithmic Applications)

Nisheeth K. Vishnoi

Foundations and Trends in Theoretical Computer Science, Volume 8, Issue 1-2, 2012.



Published


  1. Bullet Entropy, optimization and counting. [arxiv]

Mohit Singh, Nisheeth K. Vishnoi

STOC 2014.


  1. Bullet Making evolution rigorous- the error threshold. [pdf]

Nisheeth K. Vishnoi

ITCS 2013.


  1. Bullet Towards polynomial simlpex-like algorithms for market equilibria. [pdf]

Jugal Garg, Ruta Mehta, Milind Sohoni, Nisheeth K. Vishnoi

SODA 2013.


  1. Bullet A permanent approach to the traveling salesman problem. [conf]

Nisheeth K. Vishnoi

FOCS 2012.


  1. Bullet A finite population model of molecular evolution: theory and computation. [arxiv]

Narendra M. Dixit, Piyush Srivastava, Nisheeth K. Vishnoi

In Journal of Computational Biology, 19(10): 1176-1202, 2012.


  1. Bullet Stochastic simulations suggest that HIV-1 survives close to its error threshold. [journal]

Kushal Tripathi, Rajesh Balagam, Nisheeth K. Vishnoi, Narendra Dixit

In PLoS Computational Biology 8(9): e1002684, 2012.


  1. Bullet A Local spectral method for graphs: with applications to improving graph partitions and exploring data graphs locally. [journal]

Michael W. Mahoney, Lorenzo Orecchia, Nisheeth K. Vishnoi

In Journal of Machine Learning Research (JMLR),Vol 13., pp. 2339-2365, 2012.


  1. Bullet 2^{\log^{1-\eps} n} hardness for closest vector problem with preprocessing. [arxiv]

Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi

STOC 2012.


  1. Bullet Approximating the exponential, the lanczos method and an \tilde{O}(m)-time spectral algorithm for balanced separator. [arxiv]

Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi

STOC 2012.


  1. BulletHardness of approximating the closest vector problem with pre-processing. [journal]

Misha Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi

Computational Complexity, 2012


  1. BulletBiased normalized cuts. [pdf]

Subhransu Maji, Nisheeth K. Vishnoi, Jitendra Malik

IEEE Computer Vision and Pattern Recognition, 2011.


    1. BulletTowards a SDP-based approach to spectral methods: A nearly-linear time algorithm for graph partitioning and decomposition. [pdf]

    Lorenzo Orecchia, Nisheeth K. Vishnoi

    ACM-SIAM Symposium on Discrete Algorithms, 2011.


    1. Bullet On LP-based approximability for strict CSPs. [pdf]

    Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi

    ACM-SIAM Symposium on Discrete Algorithms, 2011.


    1. Bullet Algorithms and hardness for subspace approximation. [pdf]

    Amit Deshpande, Madhur Tulsiani, Nisheeth K. Vishnoi

    ACM-SIAM Symposium on Discrete Algorithms, 2011.


    1. Bullet Improved algorithm for degree bounded survivable network design problem. [pdf]

    Anand Louis, Nisheeth K. Vishnoi

    12th Scandinavian Symposium and Workshops on Algorithm Theory, 2010.


    1. Bullet On the Fourier spectrum of symmetric Boolean functions. [pdf]

    Mihail N. Kolountzakis, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi

    Combinatorica, Vol. 29, No. 3, pp. 363-387, 2009.


    1. Bullet Deterministically testing sparse polynomial identities of unbounded degree. [pdf]

    Markus Blaser, Moritz Hardt, Richard J. Lipton, Nisheeth K. Vishnoi

    Information Processing Letters 109(3): 187-192, 2009.


    1. Bullet Unique games on expanding constraint graphs are easy. (Extended Abstract) [ACM Digital Library]

    Sanjeev Arora, Subhash A. Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi

    In the 40th ACM Symposium on Theory of Computing, 2008.


    1. Bullet On partitioning graphs via single commodity flows. (Extended Abstract) [pdf]

    Lorenzo Orecchia, Leonard Schulman, Umesh V. Vazirani, Nisheeth K. Vishnoi

    In the 40th ACM Symposium on Theory of Computing, 2008.


  1. Bullet The impact of noise on the scaling of collectives: The nearest neighbor model. [pdf]

  2. Nisheeth K. Vishnoi

    In the 14th International Conference on High Performance Computing, 2007.


  3. Bullet On the computational aspect of risk in playing non-cooperative games. [pdf]

  4. Deeparnab Chakrabarty, Subhash A. Khot, Richard J. Lipton, Nisheeth K. Vishnoi

    In the 18th International Conference on Game Theory, Stony Brook, 2007.


  5. Bullet Integrality gaps for sparsest cut and minimum linear arrangement problems. (Extended abstract) [pdf]

  6. Nikhil Devanur, Subhash Khot, Rishi Saket, Nisheeth K. Vishnoi

    In the 38th ACM Symposium on Theory of Computing, 2006.


  7. Bullet The impact of noise on the scaling of collectives: A theoretical approach. [pdf]

  8. Saurabh Agarwal, Rahul Garg, Nisheeth K. Vishnoi

    In the 14th International Conference on High Performance Computing, 2005.


  9. BulletThe unique games conjecture, integrality gap for cut problems and the embeddability of negative type metrics into l_1. [Extended abstract- pdf] [Full version- arxiv]

  10. Subhash Khot, Nisheeth K. Vishnoi

    In the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005.

    Awarded the Best Paper Award at IEEE FOCS 2005.

    Awarded the IBM Research Pat Goldberg Memorial Award for 2005.


  11. BulletHardness of approximating the closest vector problem with pre-processing. (Extended abstract) [pdf]

  12. Misha Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi

    In the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005.


  13. BulletCaching with expiration times for internet applications. [pdf]

  14. Parikshit Gopalan, Howard Karloff, Aranyak Mehta, Milena Mihail, Nisheeth K. Vishnoi

    In Internet Mathematics, 2005.


  15. Bullet The impact of noise on the scaling of collectives: A theoretical approach. (Extended abstract) [pdf]

  16. Saurabh Agarwal, Rahul Garg, Nisheeth K. Vishnoi

    In the 12th International Conference on High Performance Computing, 2005.



  17. BulletOn the fourier spectrum of symmetric boolean functions with applications to learning symmetric juntas. [pdf]

  18. Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi

    In the 20th IEEE Conference on Computational Complexity, 2005.



  19. BulletOn the complexity of Hilbert's 17th problem. [pdf]

  20. Nikhil R. Devanur, Richard J. Lipton, Nisheeth K. Vishnoi

    In Foundations of Software Technology and Theoretical Computer Science, 24th International

  21. Conference, Chennai, India, 2004.


  22. BulletA Generalization of the Characteristic Polynomial of a Graph. [pdf]

  23. Richard J. Lipton, Nisheeth K. Vishnoi

  24. In 35th Southeastern International Conference on Combinatorics, Graph Theory

  25. and Computing, Boca Raton 2004.


  26. BulletDeterministic identity testing for multivariate polynomials. [pdf]

  27. Richard J. Lipton, Nisheeth K. Vishnoi

  28. In 14th ACM-SIAM Symposium on Discrete Algorithms, 2003.


  29. BulletNon uniform random walks. [pdf]

  30. Nisheeth K. Vishnoi

  31. In Discrete Mathematics and Theoretical Computer Science, vol. AC (2003)

  32. Discrete Random Walks 2003. Editors: Cyril Banderier and Christian Krattenthaler.



  33. BulletWho's �The Weakest Link�? [pdf]

  34. Nikhil Devanur, Richard J. Lipton, Nisheeth K. Vishnoi

  35. In 2nd Symposium on Stochastic Algorithms, Foundations and Applications, 2003.


  36. BulletOn generating graphs with prescribed degree sequences for complex network modeling applications. [pdf]

  37. Milena Mihail, Nisheeth K. Vishnoi

  38. In Approximation and Randomized Algorithms for Communication Networks, 2002.


  39. BulletCaching with expiration times. [pdf]

  40. Parikshit Gopalan, Howard Karloff, Aranyak Mehta, Milena Mihail, Nisheeth K. Vishnoi

  41. In the 13th ACM-SIAM ACM Symposium on Discrete Algorithms, 2002.



  42. BulletAn algebraic proof of Alon's Combinatorial Nullstellensatz. [pdf]

  43. Nisheeth K. Vishnoi

  44. In Congressus Numerantium, vol. 152, 89-91, 2001.




Manuscripts [Available on Request]


  1. Bullet Matrix inversion is as easy as exponentiation. [arxiv]

Sushant Sachdeva, Nisheeth K. Vishnoi


  1. BulletConnections between Unique Games and Multicut. [ECCC]

  2. David Steurer, Nisheeth K. Vishnoi

  3. ECCC Technical Report TR09-125.



  4. BulletOn a cut-matching game for expansion. [Tech Report]

  5. Rohit M. Khandekar, Subhash A. Khot, Lorenzo Orecchia, Nisheeth K. Vishnoi

  6. University of California, Berkeley Technical Report No. UCB/EECS-2007-177.



  7. BulletOn the hardness of minimum linear arrangement.

  8. Nikhil R. Devanur, Subhash A. Khot, Rishi Saket, Nisheeth K. Vishnoi

  9. Manuscript, 2005.



  10. BulletHardness of lattice problems in l_p norm.

  11. Subhash A. Khot, Nisheeth K. Vishnoi

  12. Manuscript, 2003.


  13. BulletGCD of p-1,q-1 for random p,q. [Tech Report]

  14. Nisheeth K. Vishnoi

  15. GIT-CC Technical Report 03-52.


  16. BulletThe geometry of matrix rigidity. [Tech Report]

  17. Joseph M. Landsberg, Jacob Taylor, Nisheeth K. Vishnoi

  18. GIT-CC Technical Report 03-54.