# Nisheeth K. Vishnoi

Affiliations:
• Yale University
• Microsoft Research

According to our database1, Nisheeth K. Vishnoi authored at least 123 papers between 2002 and 2022.

Collaborative distances:
• Dijkstra number2 of two.
• Erdős number3 of two.

## ACM Fellow

ACM Fellow 2019, "For contributions to theoretical computer science and its connections with mathematics, sciences, and social sciences".

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2022
Iteratively reweighted least squares and slime mold dynamics: connection and convergence.
Math. Program., 2022

Faster Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk.
CoRR, 2022

A Convergent and Dimension-Independent Min-Max Optimization Algorithm.
Proceedings of the International Conference on Machine Learning, 2022

Selection in the Presence of Implicit Bias: The Advantage of Intersectional Constraints.
Proceedings of the FAccT '22: 2022 ACM Conference on Fairness, Accountability, and Transparency, Seoul, Republic of Korea, June 21, 2022

Fairness for AUC via Feature Augmentation.
Proceedings of the FAccT '22: 2022 ACM Conference on Fairness, Accountability, and Transparency, Seoul, Republic of Korea, June 21, 2022

Private Matrix Approximation and Geometry of Unitary Orbits.
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021
On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes).
SIAM J. Discret. Math., 2021

Dynamic Sampling from Graphical Models.
SIAM J. Comput., 2021

Sampling from Log-Concave Distributions with Infinity-Distance Guarantees and Applications to Differentially Private Optimization.
CoRR, 2021

Optimization and Sampling Under Continuous Symmetry: Examples and Lie Theory.
CoRR, 2021

An Introduction to Hamiltonian Monte Carlo Method for Sampling.
CoRR, 2021

Greedy adversarial equilibrium: an efficient alternative to nonconvex-nonconcave min-max optimization.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Sampling matrices from Harish-Chandra-Itzykson-Zuber densities with applications to Quantum inference and differential privacy.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Coresets for Time Series Clustering.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Fair Classification with Noisy Protected Attributes: A Framework with Provable Guarantees.
Proceedings of the 38th International Conference on Machine Learning, 2021

FOCS 2021 Preface.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

The Effect of the Rooney Rule on Implicit Bias in the Long Term.
Proceedings of the FAccT '21: 2021 ACM Conference on Fairness, 2021

2020
Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration.
SIAM J. Comput., 2020

A Polynomial-Time Algorithm and Applications for Matrix Sampling from Harish-Chandra-Itzykson-Zuber Densities.
CoRR, 2020

On the Computability of Continuous Maximum Entropy Distributions: Adjoint Orbits of Lie Groups.
CoRR, 2020

A Provably Convergent and Practical Algorithm for Min-max Optimization with Applications to GANs.
CoRR, 2020

A Second-order Equilibrium in Nonconvex-Nonconcave Min-max Optimization: Existence and Algorithm.
CoRR, 2020

Fair Classification with Noisy Protected Attributes.
CoRR, 2020

On the computability of continuous maximum entropy distributions with applications.
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal.
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Coresets for Regressions with Panel Data.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Data preprocessing to mitigate bias: A maximum entropy based approach.
Proceedings of the 37th International Conference on Machine Learning, 2020

Interventions for ranking in the presence of implicit bias.
Proceedings of the FAT* '20: Conference on Fairness, 2020

2019
Belief Propagation, Bethe Approximation and Polynomials.
IEEE Trans. Inf. Theory, 2019

Fair Distributions from Biased Samples: A Maximum Entropy Optimization Framework.
CoRR, 2019

Faster algorithms for polytope rounding, sampling, and volume computation via a sublinear "Ball Walk".
CoRR, 2019

CoRR, 2019

Technical perspective: Isolating a matching when your coins go missing.
Commun. ACM, 2019

A dashboard for controlling polarization in personalization.
AI Commun., 2019

Online sampling from log-concave distributions.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Coresets for Clustering with Fairness Constraints.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Toward Controlling Discrimination in Online Ad Auctions.
Proceedings of the 36th International Conference on Machine Learning, 2019

Stable and Fair Classification.
Proceedings of the 36th International Conference on Machine Learning, 2019

Faster Polytope Rounding, Sampling, and Volume Computation via a Sub-Linear Ball Walk.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Controlling Polarization in Personalization: An Algorithmic Framework.
Proceedings of the Conference on Fairness, Accountability, and Transparency, 2019

Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees.
Proceedings of the Conference on Fairness, Accountability, and Transparency, 2019

Maximum Entropy Distributions: Bit Complexity and Stability.
Proceedings of the Conference on Learning Theory, 2019

Nonconvex sampling with the Metropolis-adjusted Langevin algorithm.
Proceedings of the Conference on Learning Theory, 2019

2018
Geodesic Convex Optimization: Differentiation on Manifolds, Geodesics, and Convexity.
CoRR, 2018

On Geodesically Convex Formulations for the Brascamp-Lieb Constant.
CoRR, 2018

Dimensionally Tight Running Time Bounds for Second-Order Hamiltonian Monte Carlo.
CoRR, 2018

An Algorithmic Framework to Control Bias in Bandit-based Personalization.
CoRR, 2018

Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Balanced News Using Constrained Bandit-based Personalization.
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Multiwinner Voting with Fairness Constraints.
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Fair and Diverse DPP-Based Data Summarization.
Proceedings of the 35th International Conference on Machine Learning, 2018

Ranking with Fairness Constraints.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Convex Optimization with Unbounded Nonconvex Oracles using Simulated Annealing.
Proceedings of the Conference On Learning Theory, 2018

On Geodesically Convex Formulations for the Brascamp-Lieb Constant.
Proceedings of the Approximation, 2018

2017
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces.
Electron. Colloquium Comput. Complex., 2017

Convex Optimization with Nonconvex Oracles.
CoRR, 2017

Computing Maximum Entropy Distributions Everywhere.
CoRR, 2017

Group Fairness in Multiwinner Voting.
CoRR, 2017

On Convex Programming Relaxations for the Permanent.
CoRR, 2017

Fair Personalization.
CoRR, 2017

A Dynamics for Advertising on Networks.
Proceedings of the Web and Internet Economics - 13th International Conference, 2017

Real stable polynomials and matroids: optimization and counting.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

A Distributed Learning Dynamics in Social Groups.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Random Walks in Polytopes and Negative Dependence.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

On the Complexity of Constrained Determinantal Point Processes.
Proceedings of the Approximation, 2017

2016
The mixing time of the Dikin walk in a polytope - A simple proof.
Oper. Res. Lett., 2016

Evolution and Computing (Dagstuhl Seminar 16011).
Dagstuhl Reports, 2016

Generalized Determinantal Point Processes: The Linear Case.
CoRR, 2016

IRLS and Slime Mold: Equivalence and Convergence.
CoRR, 2016

How to be Fair and Diverse?
CoRR, 2016

Natural Algorithms for Flow Problems.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Evolutionary Dynamics in Finite Populations Mix Rapidly.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

On a Natural Dynamics for Linear Programming.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

On the Computational Complexity of Limit Cycles in Dynamical Systems.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Mixing Time of Markov Chains, Dynamical Systems and Evolution.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Evolution and Computation (Invited Talk).
Proceedings of the 31st Conference on Computational Complexity, 2016

2015
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ<sub>1</sub>.
J. ACM, 2015

A Simple Analysis of the Dikin Walk.
CoRR, 2015

The Speed of Evolution.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014
Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing.
SIAM J. Comput., 2014

Faster Algorithms via Approximation Theory.
Found. Trends Theor. Comput. Sci., 2014

A quadratically tight partition bound for classical communication complexity and query complexity.
CoRR, 2014

Entropy, optimization and counting.
Proceedings of the Symposium on Theory of Computing, 2014

2013
Lx = b.
Found. Trends Theor. Comput. Sci., 2013

Matrix Inversion Is As Easy As Exponentiation
CoRR, 2013

Approximation Theory and the Design of Fast Algorithms.
CoRR, 2013

Towards Polynomial Simplex-Like Algorithms for Market Equlibria.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Making evolution rigorous: the error threshold.
Proceedings of the Innovations in Theoretical Computer Science, 2013

2012
Stochastic Simulations Suggest that HIV-1 Survives Close to Its Error Threshold.
PLoS Comput. Biol., 2012

A local spectral method for graphs: with applications to improving graph partitions and exploring data graphs locally.
J. Mach. Learn. Res., 2012

A Finite Population Model of Molecular Evolution: Theory and Computation.
J. Comput. Biol., 2012

Approximating the exponential, the lanczos method and an Õ(<i>m</i>)-time spectral algorithm for balanced separator.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2<sup>log1-ε <i>n</i></sup> hardness for the closest vector problem with preprocessing.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

A Permanent Approach to the Traveling Salesman Problem.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
2<sup>log<sup>1-έ</sup>n</sup> Hardness for Closest Vector Problem with Preprocessing.
Electron. Colloquium Comput. Complex., 2011

Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator
CoRR, 2011

$2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing
CoRR, 2011

Hardness of Approximating the Closest Vector Problem with Pre-Processing.
Comput. Complex., 2011

Towards an SDP-based Approach to Spectral Methods: A Nearly-Linear-Time Algorithm for Graph Partitioning and Decomposition.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

On LP-Based Approximability for Strict CSPs.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Algorithms and Hardness for Subspace Approximation.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Biased normalized cuts.
Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition, 2011

2010
Improved Algorithm for Degree Bounded Survivable Network Design Problem.
Proceedings of the Algorithm Theory, 2010

2009
Deterministically testing sparse polynomial identities of unbounded degree.
Inf. Process. Lett., 2009

Connections Between Unique Games and Multicut.
Electron. Colloquium Comput. Complex., 2009

On the Optimality of a Class of LP-based Algorithms.
Electron. Colloquium Comput. Complex., 2009

Algorithms and Hardness for Subspace Approximation
CoRR, 2009

A Spectral Algorithm for Improving Graph Partitions
CoRR, 2009

On the Fourier spectrum of symmetric Boolean functions.
Comb., 2009

2008
On partitioning graphs via single commodity flows.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Unique games on expanding constraint graphs are easy: extended abstract.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007
The Impact of Noise on the Scaling of Collectives: The Nearest Neighbor Model [Extended Abstract].
Proceedings of the High Performance Computing, 2007

2006
Integrality gaps for sparsest cut and minimum linear arrangement problems.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005
Caching with Expiration Times for Internet Applications.
Internet Math., 2005

The Impact of Noise on the Scaling of Collectives: A Theoretical Approach.
Proceedings of the High Performance Computing, 2005

On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
Theoretical Aspects of Randomization in Computation.
PhD thesis, 2004

On the Complexity of Hilbert's 17th Problem.
Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

2003
Deterministic identity testing for multivariate polynomials.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003