Monographs and Expository

1. Geodesic Convex Optimization: Differentiation on Manifolds, Geodesics, and Convexity. [arXiv]
   

Nisheeth K. Vishnoi

1. A Mini-Course on Convex Optimization (with a view toward designing fast algorithms). [notes]
   

Nisheeth K. Vishnoi

1. Faster Algorithms via Approximation Theory. [pdf]
   

Sushant Sachdeva, Nisheeth K. Vishnoi

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

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

Nisheeth K. Vishnoi

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

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

Nisheeth K. Vishnoi

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

Nisheeth K. Vishnoi

Recent Papers (by topic)

Alogrithms & Complexity, Optimization, Dynamical Systems, Probability

Algorithmic Bias

Natural Algorithms and Evolution

All Papers (in reverse chronological order)

1. Computing maximum entropy distributions everywhere. [arXiv]
   

Damian Straszak, Nisheeth K. Vishnoi

1. On convex programming relaxations for the permanent. [arxiv]
   

Damian Straszak, Nisheeth K. Vishnoi

1. Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees. [arXiv]
   

L. Elisa Celis, Lingxiao Huang, Vijay Keswani, Nisheeth K. Vishnoi

ACM FAT* 2019.

1. An Algorithmic Framework to Control Bias in Bandit-based Personalization. [arXiv]
   

L. Elisa Celis, Sayash Kapoor, Farnood Salehi, Nisheeth K. Vishnoi

ACM FAT* 2019.

1. On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes). [arXiv]
   

Rohit Gurjar, Nisheeth K. Vishnoi

SODA 2019.

1. Dimensionally tight running time bounds for second-order Hamiltonian Monte Carlo. [arXiv]
   

Oren Mangoubi, Nisheeth K. Vishnoi

NIPS 2018.

1. On geodesically convex formulations for the Brascamp-Lieb constant. [arXiv]
   

Suvrit Sra, Nisheeth K. Vishnoi, Ozan Yildiz

APPROX 2018.

1. Fair and Diverse Data Summarization. [arXiv]
   

L. Elisa Celis, Vijay Keswani, Damian Straszak, Amit Deshpande, Tarun Kathuria, Nisheeth K. Vishnoi

ICML 2018.

1. Convex optimization with nonconvex oracles. [arXiv]
   

Oren Mangoubi, Nisheeth K. Vishnoi

COLT 2018.

1. Balanced News Using Constrained Bandit-based Personalization. [Demo Website] [Demo Video]
   

Sayash Kapoor, Vijay Keswani, Nisheeth K. Vishnoi, L. Elisa Celis

IJCAI-ECAI (Demo track) 2018.

1. Multiwinner voting with fairness constraints. [arxiv]
   

L. Elisa Celis, Lingxiao Huang, Nisheeth K. Vishnoi

IJCAI-ECAI 2018.

1. Isolating a vertex via lattices: Polytopes with totally unimodular faces. [arxiv]
   

Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi

ICALP 2018.

1. Ranking with Fairness Constraints. [arxiv]
   

L. Elisa Celis, Damian Straszak, Nisheeth K. Vishnoi

ICALP 2018.

1. A dynamics for advertising on networks. [pdf]
   

L. Elisa Celis, Mina Dalirrooyfard, Nisheeth K. Vishnoi

WINE 2017.

1. Belief Propagation, Bethe Approximation and Polynomials. [arxiv]
   

Damian Straszak, Nisheeth K. Vishnoi

Invited to ALLERTON 2017.

1. Subdeterminant maximization via nonconvex relaxations and anticoncentration. [arXiv]
   

Javad Ebrahimi, Damian Straszak, Nisheeth K. Vishnoi

FOCS 2017.

1. Fair Personalization. [arxiv]
   

L. Elisa Celis, Nisheeth K. Vishnoi

Fairness, Accountability and Transparency in ML, 2017.

1. On the Complexity of Constrained Determinantal Point Processes. [arxiv]
   

L. Elisa Celis, Amit Deshpande, Tarun Kathuria, Damian Straszak, Nisheeth K. Vishnoi

RANDOM 2017.

1. A distributed learning dynamics in social groups. [arxiv]
   

L. Elisa Celis, Peter M. Krafft, Nisheeth K. Vishnoi

PODC 2017.

1. Real stable polynomials and matroids: optimization and counting. [arxiv]
   

Damian Straszak, Nisheeth K. Vishnoi

STOC 2017.

1. IRLS and Slime Mold: Equivalence and Convergence. [arXiv]
   

Damian Straszak, Nisheeth K. Vishnoi

Invited to ITCS 2017.

1. Random walks in polytopes and negative dependence
   

Yuval Peres, Mohit Singh, Nisheeth K. Vishnoi

ITCS 2017.

1. How to be fair and diverse? [arxiv]
   

L. Elisa Celis, Amit Deshpande, Tarun Kathuria, Nisheeth K. Vishnoi

Fairness, Accountability and Transparency in ML, 2016 (Selected for presentation).

1. The Mixing time of the Dikin walk in polytopes -- a simple proof. [journal]
   

Sushant Sachdeva, Nisheeth K. Vishnoi

Operations Research Letters 2016.

1. Mixing time of Markov chains, dynamical systems and evolution. [pdf]
   

Ioannis Panageas, Nisheeth K. Vishnoi

ICALP 2016.

1. On the computational complexity of limit cycles in dynamical systems. [arxiv]
   

Christos H. Papadimitriou, Nisheeth K. Vishnoi

ITCS 2016.

1. On a natural dynamics for linear programming. [arxiv]
   

Damian Straszak, Nisheeth K. Vishnoi

ITCS 2016.

1. Natural algorithms for flow problems. [journal]
   

Damian Straszak, Nisheeth K. Vishnoi

SODA 2016.

1. Evolutionary dynamics in finite populations mix rapidly. [pdf]
   

Ioannis Panageas, Piyush Srivastava, Nisheeth K. Vishnoi

SODA 2016.

1. The unique games conjecture, integrality gap for cut problems and the embeddability of negative type metrics into l_1. [journal]
   

Subhash Khot, Nisheeth K. Vishnoi

Journal of the ACM, 62(1), 2015.

1. The speed of evolution. [pdf]
   

Nisheeth K. Vishnoi

SODA 2015.

1. Entropy, optimization and counting. [arxiv]
   

Mohit Singh, Nisheeth K. Vishnoi

STOC 2014.

1. Almost polynomial factor hardness for Closest Vector Problem with Preprocessing. [journal]
   

Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi

SIAM Journal of Computing, 43(3), 1184–1205, 2014.

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

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

SODA 2013.

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

Nisheeth K. Vishnoi

ITCS 2013.

1. 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. 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. A permanent approach to the traveling salesman problem. [conf]
   

Nisheeth K. Vishnoi

FOCS 2012.

1. 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. 2^{\log^{1-\eps} n} hardness for closest vector problem with preprocessing. [arxiv]
   

Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi

STOC 2012.

1. 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. Hardness of approximating the closest vector problem with pre-processing. [journal]
   

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

Computational Complexity, 2012

1. Biased normalized cuts. [pdf]
   

Subhransu Maji, Nisheeth K. Vishnoi, Jitendra Malik

IEEE Computer Vision and Pattern Recognition, 2011.

1. Towards 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. 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. Algorithms and hardness for subspace approximation. [pdf]
   

Amit Deshpande, Madhur Tulsiani, Nisheeth K. Vishnoi


ACM-SIAM Symposium on Discrete Algorithms, 2011.





1. 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. 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. 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. 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. 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. The impact of noise on the scaling of collectives: The nearest neighbor model. [pdf]
   

Nisheeth K. Vishnoi


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





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

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


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





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

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


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





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

Saurabh Agarwal, Rahul Garg, Nisheeth K. Vishnoi


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





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

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.





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

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


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





7. Caching with expiration times for internet applications. [pdf]
   

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


In Internet Mathematics, 2005.





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

Saurabh Agarwal, Rahul Garg, Nisheeth K. Vishnoi


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





9. 
   

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

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


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





11. 
    

12. On the complexity of Hilbert's 17th problem. [pdf]
    

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


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


13. Conference, Chennai, India, 2004.

    
    

14. A Generalization of the Characteristic Polynomial of a Graph. [pdf]
    

15. Richard J. Lipton, Nisheeth K. Vishnoi
    

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

17. and Computing, Boca Raton 2004.
    




18. Deterministic identity testing for multivariate polynomials. [pdf]
    

19. Richard J. Lipton, Nisheeth K. Vishnoi
    

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




21. Non uniform random walks. [pdf]
    

22. Nisheeth K. Vishnoi
    

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

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




25. 
    

26. Who's �The Weakest Link�? [pdf]
    

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

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




29. On generating graphs with prescribed degree sequences for complex network modeling applications. [pdf]
    

30. Milena Mihail, Nisheeth K. Vishnoi
    

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




32. Caching with expiration times. [pdf]
    

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

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




35. 
    

36. An algebraic proof of Alon's Combinatorial Nullstellensatz. [pdf]
    

37. Nisheeth K. Vishnoi
    

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

Manuscripts [Available on Request]

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

Sushant Sachdeva, Nisheeth K. Vishnoi

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

2. David Steurer, Nisheeth K. Vishnoi
   

3. ECCC Technical Report TR09-125.
   

4. 
   




5. On a cut-matching game for expansion. [Tech Report]
   

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

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

8. 
   




9. On the hardness of minimum linear arrangement.
   

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

11. Manuscript, 2005.
    




12. 
    

13. Hardness of lattice problems in l_p norm.
    

14. Subhash A. Khot, Nisheeth K. Vishnoi
    

15. Manuscript, 2003.
    




16. GCD of p-1,q-1 for random p,q. [Tech Report]
    

17. Nisheeth K. Vishnoi
    

18. GIT-CC Technical Report 03-52.
    




19. The geometry of matrix rigidity. [Tech Report]
    

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

21. GIT-CC Technical Report 03-54.