Books, Monographs and Surveys

1. On the works of Avi Wigderson. [arxiv]
   

Boaz Barak, Yael Kalai, Ran Raz, Salil Vadhan, Nisheeth K. Vishnoi

1. Optimization and Sampling Under Continuous Symmetry: Examples and Lie Theory. [arxiv]
   

Jonathan Leake and Nisheeth K. Vishnoi

1. An Introduction to Hamiltonian Monte Carlo Method for Sampling. [arxiv]
   

Nisheeth K. Vishnoi

1. The Dynamics of Lagrange and Hamilton. [pdf]
   

Nisheeth K. Vishnoi

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

Nisheeth K. Vishnoi

1. Algorithms for Convex Optimization. [book]

   Nisheeth K. Vishnoi
   

   Cambridge University Press, 2021.
   

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

All Papers (in reverse chronological order)

1. Faster Sampling from Log-Concave Distributions over Polytopes via Efficient Linear Solvers. [pdf]
   

   Oren Mangoubi, Nisheeth K. Vishnoi
   

   ICLR 2024.
   

   
   

   1. Bias in Evaluation Processes: An Optimization-Based Model. [arxiv]
      

      L. Elisa Celis, Amit Kumar, Anay Mehrotra, Nisheeth K. Vishnoi
      

      NeurIPS 2023.
      

      
      

      1. Sampling from Structured Log-Concave Distributions via a Soft-Threshold Dikin Walk. [arxiv]
         

         Oren Mangoubi, Nisheeth K. Vishnoi
         

         NeurIPS 2023.
         

         
         

         1. Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex Gaussian Perturbations. [arxiv]
            

            Oren Mangoubi, Nisheeth K. Vishnoi
            

            COLT 2023.
            

            
            

            1. Subset Selection Based On Multiple Rankings in the Presence of Bias: Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions. [arxiv]
               

               Niclas Boehmer, L. Elisa Celis, Lingxiao Huang, Anay Mehrotra, Nisheeth K. Vishnoi
               

               ICML 2023.
               

               
               

               1. Maximizing Submodular Functions for Recommendation in the Presence of Biases. [arxiv]
                  

                  Anay Mehrotra, Nisheeth K. Vishnoi
                  

                  The Web Conference (WWW) 2023.
                  

                  
                  

                  1. Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion. [arxiv]
                     

                     Oren Mangoubi, Nisheeth K. Vishnoi
                     

                     NeurIPS 2022.
                     

                     
                     

                     1. Fair Ranking with Noisy Protected Attributes. [arxiv]
                        

                        Anay Mehrotra, Nisheeth K. Vishnoi
                        

                        NeurIPS 2022.
                        

                        
                        

                        1. Sampling from Log-Concave Distributions with Infinity-Distance Guarantees. [arxiv]
                           

                           Oren Mangoubi, Nisheeth K. Vishnoi
                           

                           NeurIPS 2022.
                           

                           
                           

                           1. Iteratively reweighted least squares and slime mold dynamics: connection and convergence. [pdf]
                              

                              Damian Straszak, Nisheeth K. Vishnoi
                              

                              Mathematical Programming, Series A, 2022.
                              

                              
                              

                              1. A Convergent and Dimension-Independent First-Order Algorithm for Min-Max Optimization. [arxiv]
                                 

                                 Vijay Keswani, Oren Mangoubi, Sushant Sachdeva, Nisheeth K. Vishnoi
                                 

                                 ICML 2022.
                                 

                                 
                                 

                                 1. Private Matrix Approximation and Geometry of Unitary Orbits. [arxiv]
                                    

                                    Oren Mangoubi, Yikai Wu, Satyen Kale, Abhradeep Thakurta, Nisheeth K. Vishnoi
                                    

                                    COLT 2022.
                                    

                                    
                                    

                                    1. Selection in the Presence of Implicit Bias: The Advantage of Intersectional Constraints. [arxiv]
                                       

                                       Anay Mehrotra, Bary R. Pradleski, Nisheeth K. Vishnoi
                                       

                                       ACM FAccT 2022.
                                       

                                       
                                       

                                       1. Fairness for AUC via Feature Augmentation. [arxiv]
                                          

                                          Hortense Fong, Vineet Kumar, Anay Mehrotra, Nisheeth K. Vishnoi
                                          

                                          ACM FAccT 2022.
                                          

                                          
                                          

                                          1. Coresets for Time Series Clustering. [arxiv]
                                             

                                             K. Sudhir, Lingxiao Huang, Nisheeth K. Vishnoi
                                             

                                             NeurIPS 2021.
                                             

                                             
                                             

                                             1. Fair Classification with Adversarial Perturbations. [arxiv]
                                                

                                                L. Elisa Celis, Anay Mehrotra, Nisheeth K. Vishnoi
                                                

                                                NeurIPS 2021.
                                                

                                                
                                                

                                                1. Fair Classification with Noisy Protected Attributes: A Framework with Provable Guarantees. [arxiv]
                                                   

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

                                                   ICML 2021.
                                                   

                                                   
                                                   

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

                                                   Rohit Gurjar, Nisheeth K. Vishnoi
                                                   

                                                   SIAM J. Discrete Math, 2021.
                                                   

                                                   
                                                   

                                                   1. Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. [journal]
                                                      

                                                      Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi
                                                      

                                                      SIAM J. Computing, 2021.
                                                      

                                                      
                                                      

                                                      1. Dynamic Sampling from Graphical Models. [journal]
                                                         

                                                         Weiming Feng, Nisheeth K. Vishnoi, Yitong Yin
                                                         

                                                         SIAM J. Computing, 2021.
                                                         

                                                         
                                                         

                                                         1. Sampling Matrices from Harish-Chandra--Itzykson-Zuber Densities with Application to Quantum Inference and Differential Privacy. [conf] [arxiv]
                                                            

                                                            Jonathan Leake, Colin McSwiggen, Nisheeth K. Vishnoi
                                                            

                                                            STOC 2021.
                                                            

                                                            
                                                            

                                                            1. Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex-Nonconcave Min-Max Optimization. [arxiv]
                                                               

                                                               Oren Mangoubi, Nisheeth K. Vishnoi
                                                               

                                                               STOC 2021.
                                                               

                                                               
                                                               

                                                               1. The Effect of the Rooney Rule on Implicit Bias in the Long Term. [arxiv]
                                                                  

                                                                  L. Elisa Celis, Chris Hays, Anay Mehrotra, Nisheeth K. Vishnoi
                                                                  

                                                                  ACM FAccT 2021.
                                                                  

                                                                  
                                                                  

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

                                                                  Javad Ebrahimi, Damian Straszak, Nisheeth K. Vishnoi
                                                                  

                                                                  SIAM J. Computing, 2020.
                                                                  

                                                                  
                                                                  

                                                                  1. Coresets for Regressions with Panel Data. [arxiv]
                                                                     

                                                                     Lingxiao Huang, K. Sudhir, Nisheeth K. Vishnoi
                                                                     

                                                                     NeurIPS 2020.
                                                                     

                                                                  
                                                                  

                                                                  1. Data preprocessing to mitigate bias: A maximum entropy based approach. [pdf]
                                                                     

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

                                                                     ICML 2020.
                                                                     

                                                                  
                                                                  

                                                                  1. On the Computability of Continuous Maximum Entropy Distributions with Applications. [arxiv]
                                                                     

                                                                  Jonathan Leake, Nisheeth K. Vishnoi
                                                                  

                                                                  STOC 2020.
                                                                  

                                                                  
                                                                  

                                                                  1. Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal. [arxiv]
                                                                     

                                                                  Lingxiao Huang, Nisheeth K. Vishnoi
                                                                  

                                                                  STOC 2020.
                                                                  

                                                                  
                                                                  

                                                                  1. Interventions for Ranking in the Presence of Implicit Bias. [arxiv]
                                                                     

                                                                  L. Elisa Celis, Anay Mehrotra, Nisheeth K. Vishnoi
                                                                  

                                                                  ACM FAT* 2020.
                                                                  

                                                                  
                                                                  

                                                                  1. Coresets for clustering with fairness constraints. [arxiv]
                                                                     

                                                                  Lingxiao Huang, Shaofeng Jiang, Nisheeth K. Vishnoi
                                                                  

                                                                  NeurIPS 2019.
                                                                  

                                                                  
                                                                  

                                                                  1. Online Sampling from Log-Concave Distributions. [arxiv]
                                                                     

                                                                  Holden Lee, Oren Mangoubi, Nisheeth K. Vishnoi
                                                                  

                                                                  NeurIPS 2019.
                                                                  

                                                                  
                                                                  

                                                                  1. Faster algorithms for polytope rounding, sampling, and volume computation via a sublinear "Ball Walk''. [arxiv]
                                                                     

                                                                  Oren Mangoubi, Nisheeth K. Vishnoi
                                                                  

                                                                  FOCS 2019.
                                                                  

                                                                  
                                                                  

                                                                  1. Towards controlling discrimination in online ad auctions. [arxiv]
                                                                     

                                                                  L. Elisa Celis, Anay Mehrotra, Nisheeth K. Vishnoi
                                                                  

                                                                  ICML 2019.
                                                                  

                                                                  
                                                                  

                                                                  1. Stable and Fair Classification. [arxiv]
                                                                     

                                                                  Lingxiao Huang, Nisheeth K. Vishnoi
                                                                  

                                                                  ICML 2019.
                                                                  

                                                                  
                                                                  

                                                                  1. Nonconvex Sampling with the Metropolis-Adjusted Langevin Algorithm. [arxiv]
                                                                     

                                                                  Oren Mangoubi, Nisheeth K. Vishnoi
                                                                  

                                                                  COLT 2019.
                                                                  

                                                                  
                                                                  

                                                                  1. Maximum entropy distributions: Bit complexity and stability. [arXiv]
                                                                     

                                                                  Damian Straszak, Nisheeth K. Vishnoi
                                                                  

                                                                  COLT 2019.
                                                                  

                                                                  
                                                                  

                                                                  1. Dynamic Sampling from Graphical Models. [arxiv]
                                                                     

                                                                  Weiming Feng, Yitong Yin, Nisheeth K. Vishnoi
                                                                  

                                                                  STOC 2019.
                                                                  

                                                                  
                                                                  

                                                                  1. Isolating a Matching When Your Coins Go Missing.
                                                                     

                                                                  Nisheeth K. Vishnoi
                                                                  

                                                                  Communications of the ACM, 2019.
                                                                  

                                                                  Invited Technical perspective.
                                                                  

                                                                  
                                                                  

                                                                  1. A Dashboard for Controlling Polarization in Personalization.
                                                                     

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

                                                                  AI Communications, 2019.
                                                                  

                                                                  Invited publication.
                                                                  

                                                                  
                                                                  

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

                                                                  Damian Straszak, Nisheeth K. Vishnoi
                                                                  

                                                                  IEEE Transactions on Information Theory, 2019.
                                                                  

                                                                  
                                                                  

                                                                  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. Controlling polarization in personalization. [pdf]
                                                                     

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

                                                                  ACM FAT* 2019.
                                                                  

                                                                  Awarded the Best Technical Paper at 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
                                                                  

                                                                  NeurIPS 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. [pdf]
                                                                  

                                                               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. [conf] [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.