Nisheeth K. Vishnoi

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1

Subhash Khot, Nisheeth K. Vishnoi · 2005 · 268 citations

Mathematical Programming, Integrality Gap, Computational Complexity Theory +18

Classification with Fairness Constraints

L. Elisa Celis, Lingxiao Huang, Vijay Keswani et al. · 2019 · 218 citations · Full text

Artificial Intelligence, Mathematical Programming, Engineering +16

Unique games on expanding constraint graphs are easy

Sanjeev Arora, Subhash Khot, Alexandra Kolla et al. · 2008 · 117 citations

Mathematical Programming, Engineering, Combinatorial Game +16

Approximating the exponential, the lanczos method and an Õ(<i>m</i>)-time spectral algorithm for balanced separator

Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi · 2012 · 114 citations

Spectral Theory, Numerical Analysis, Graph Sparsity +21

Integrality gaps for sparsest cut and minimum linear arrangement problems

Nikhil R. Devanur, Subhash Khot, Rishi Saket et al. · 2006 · 95 citations

Numerical Analysis, Mathematical Programming, Integrality Gap +18