Nisheeth K. Vishnoi

Proceedings of the Twelfth International Conference on Learning Representations, 2024

2023

On the works of Avi Wigderson.

[BibT_eX]

[DOI]

CoRR, 2023

Maximizing Submodular Functions for Recommendation in the Presence of Biases.

[BibT_eX]

[DOI]

Proceedings of the ACM Web Conference 2023, 2023

Sampling from Structured Log-Concave Distributions via a Soft-Threshold Dikin Walk.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Bias in Evaluation Processes: An Optimization-Based Model.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

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

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Algorithms in the Presence of Biased Inputs (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex Gaussian Perturbations.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

On the Computability of Continuous Maximum Entropy Distributions with Applications.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Iteratively reweighted least squares and slime mold dynamics: connection and convergence.

[BibT_eX]

[DOI]

Math. Program., 2022

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

[BibT_eX]

[DOI]

CoRR, 2022

Fair Ranking with Noisy Protected Attributes.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Sampling from Log-Concave Distributions with Infinity-Distance Guarantees.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

A Convergent and Dimension-Independent Min-Max Optimization Algorithm.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

Selection in the Presence of Implicit Bias: The Advantage of Intersectional Constraints.

[BibT_eX]

[DOI]

Bary S. R. Pradelski

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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).

[BibT_eX]

[DOI]

Rohit Gurjar

SIAM J. Discret. Math., 2021

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces.

[BibT_eX]

[DOI]

Rohit Gurjar

Thomas Thierauf

SIAM J. Comput., 2021

Dynamic Sampling from Graphical Models.

[BibT_eX]

[DOI]

Weiming Feng

Yitong Yin

SIAM J. Comput., 2021

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

[BibT_eX]

[DOI]

CoRR, 2021

Optimization and Sampling Under Continuous Symmetry: Examples and Lie Theory.

[BibT_eX]

[DOI]

CoRR, 2021

An Introduction to Hamiltonian Monte Carlo Method for Sampling.

[BibT_eX]

[DOI]

CoRR, 2021

Greedy adversarial equilibrium: an efficient alternative to nonconvex-nonconcave min-max optimization.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Colin S. McSwiggen

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Coresets for Time Series Clustering.

[BibT_eX]

[DOI]

K. Sudhir

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

Fair Classification with Adversarial Perturbations.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

FOCS 2021 Preface.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the FAccT '21: 2021 ACM Conference on Fairness, 2021

2020

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration.

[BibT_eX]

[DOI]

Javad B. Ebrahimi

SIAM J. Comput., 2020

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

[BibT_eX]

[DOI]

Colin S. McSwiggen

CoRR, 2020

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

[BibT_eX]

[DOI]

CoRR, 2020

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

[BibT_eX]

[DOI]

CoRR, 2020

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

[BibT_eX]

[DOI]

CoRR, 2020

Fair Classification with Noisy Protected Attributes.

[BibT_eX]

[DOI]

CoRR, 2020

Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Coresets for Regressions with Panel Data.

[BibT_eX]

[DOI]

K. Sudhir

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.

[BibT_eX]

[DOI]

Vijay Keswani

Proceedings of the 37th International Conference on Machine Learning, 2020

Interventions for ranking in the presence of implicit bias.

[BibT_eX]

[DOI]

Proceedings of the FAT* '20: Conference on Fairness, 2020

2019

Belief Propagation, Bethe Approximation and Polynomials.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2019

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

[BibT_eX]

[DOI]

CoRR, 2019

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

[BibT_eX]

[DOI]

CoRR, 2019

Fair Online Advertising.

[BibT_eX]

[DOI]

CoRR, 2019

Technical perspective: Isolating a matching when your coins go missing.

[BibT_eX]

[DOI]

Commun. ACM, 2019

A dashboard for controlling polarization in personalization.

[BibT_eX]

[DOI]

AI Commun., 2019

Online sampling from log-concave distributions.

[BibT_eX]

[DOI]

Holden Lee

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.

[BibT_eX]

[DOI]

Shaofeng H.-C. Jiang

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.

[BibT_eX]

[DOI]

Proceedings of the 36th International Conference on Machine Learning, 2019

Stable and Fair Classification.

[BibT_eX]

[DOI]

Proceedings of the 36th International Conference on Machine Learning, 2019

Faster Polytope Rounding, Sampling, and Volume Computation via a Sub-Linear Ball Walk.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Controlling Polarization in Personalization: An Algorithmic Framework.

[BibT_eX]

[DOI]

Proceedings of the Conference on Fairness, Accountability, and Transparency, 2019

Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees.

[BibT_eX]

[DOI]

Proceedings of the Conference on Fairness, Accountability, and Transparency, 2019

Maximum Entropy Distributions: Bit Complexity and Stability.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

Nonconvex sampling with the Metropolis-adjusted Langevin algorithm.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

2018

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

[BibT_eX]

[DOI]

CoRR, 2018

On Geodesically Convex Formulations for the Brascamp-Lieb Constant.

[BibT_eX]

[DOI]

Ozan Yildiz

CoRR, 2018

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

[BibT_eX]

[DOI]

CoRR, 2018

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

[BibT_eX]

[DOI]

CoRR, 2018

Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Multiwinner Voting with Fairness Constraints.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Fair and Diverse DPP-Based Data Summarization.

[BibT_eX]

[DOI]

Proceedings of the 35th International Conference on Machine Learning, 2018

Ranking with Fairness Constraints.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Convex Optimization with Unbounded Nonconvex Oracles using Simulated Annealing.

[BibT_eX]

[DOI]

Proceedings of the Conference On Learning Theory, 2018

On Geodesically Convex Formulations for the Brascamp-Lieb Constant.

[BibT_eX]

[DOI]

Suvrit Sra

Ozan Yildiz

Proceedings of the Approximation, 2018

2017

Convex Optimization with Nonconvex Oracles.

[BibT_eX]

[DOI]

CoRR, 2017

Computing Maximum Entropy Distributions Everywhere.

[BibT_eX]

[DOI]

CoRR, 2017

Group Fairness in Multiwinner Voting.

[BibT_eX]

[DOI]

CoRR, 2017

On Convex Programming Relaxations for the Permanent.

[BibT_eX]

[DOI]

CoRR, 2017

Fair Personalization.

[BibT_eX]

[DOI]

CoRR, 2017

A Dynamics for Advertising on Networks.

[BibT_eX]

[DOI]

Mina Dalirrooyfard

Proceedings of the Web and Internet Economics - 13th International Conference, 2017

Real stable polynomials and matroids: optimization and counting.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

A Distributed Learning Dynamics in Social Groups.

[BibT_eX]

[DOI]

Peter M. Krafft

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Random Walks in Polytopes and Negative Dependence.

[BibT_eX]

[DOI]

Yuval Peres

Mohit Singh

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

On the Complexity of Constrained Determinantal Point Processes.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

2016

The mixing time of the Dikin walk in a polytope - A simple proof.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2016

Evolution and Computing (Dagstuhl Seminar 16011).

[BibT_eX]

[DOI]

Nick Barton

Per Kristian Lehre

Dagstuhl Reports, 2016

Generalized Determinantal Point Processes: The Linear Case.

[BibT_eX]

[DOI]

CoRR, 2016

IRLS and Slime Mold: Equivalence and Convergence.

[BibT_eX]

[DOI]

CoRR, 2016

How to be Fair and Diverse?

[BibT_eX]

[DOI]

CoRR, 2016

Natural Algorithms for Flow Problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Evolutionary Dynamics in Finite Populations Mix Rapidly.

[BibT_eX]

[DOI]

Ioannis Panageas

Piyush Srivastava

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

On a Natural Dynamics for Linear Programming.

[BibT_eX]

[DOI]

Christos H. Papadimitriou

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

On the Computational Complexity of Limit Cycles in Dynamical Systems.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Mixing Time of Markov Chains, Dynamical Systems and Evolution.

[BibT_eX]

[DOI]

Ioannis Panageas

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Evolution and Computation (Invited Talk).

[BibT_eX]

[DOI]

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 ℓ1.

[BibT_eX]

[DOI]

J. ACM, 2015

A Simple Analysis of the Dikin Walk.

[BibT_eX]

[DOI]

CoRR, 2015

The Speed of Evolution.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Faster Algorithms via Approximation Theory.

[BibT_eX]

[DOI]

Found. Trends Theor. Comput. Sci., 2014

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

[BibT_eX]

[DOI]

Rahul Jain

Troy Lee

CoRR, 2014

Entropy, optimization and counting.

[BibT_eX]

[DOI]

Mohit Singh

Proceedings of the Symposium on Theory of Computing, 2014

2013

Lx = b.

[BibT_eX]

[DOI]

Found. Trends Theor. Comput. Sci., 2013

Matrix Inversion Is As Easy As Exponentiation

[BibT_eX]

[DOI]

CoRR, 2013

Approximation Theory and the Design of Fast Algorithms.

[BibT_eX]

[DOI]

CoRR, 2013

Towards Polynomial Simplex-Like Algorithms for Market Equlibria.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Making evolution rigorous: the error threshold.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Stochastic Simulations Suggest that HIV-1 Survives Close to Its Error Threshold.

[BibT_eX]

[DOI]

PLoS Comput. Biol., 2012

A local spectral method for graphs: with applications to improving graph partitions and exploring data graphs locally.

[BibT_eX]

[DOI]

Michael W. Mahoney

J. Mach. Learn. Res., 2012

A Finite Population Model of Molecular Evolution: Theory and Computation.

[BibT_eX]

[DOI]

Narendra M. Dixit

Piyush Srivastava

J. Comput. Biol., 2012

Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2log1-ε n hardness for the closest vector problem with preprocessing.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

A Permanent Approach to the Traveling Salesman Problem.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

2log1-έn Hardness for Closest Vector Problem with Preprocessing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

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

[BibT_eX]

[DOI]

CoRR, 2011

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

[BibT_eX]

[DOI]

CoRR, 2011

Hardness of Approximating the Closest Vector Problem with Pre-Processing.

[BibT_eX]

[DOI]

Comput. Complex., 2011

Towards an SDP-based Approach to Spectral Methods: A Nearly-Linear-Time Algorithm for Graph Partitioning and Decomposition.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

On LP-Based Approximability for Strict CSPs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Algorithms and Hardness for Subspace Approximation.

[BibT_eX]

[DOI]

Amit Deshpande

Madhur Tulsiani

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Biased normalized cuts.

[BibT_eX]

[DOI]

Subhransu Maji

Jitendra Malik

Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition, 2011

2010

Improved Algorithm for Degree Bounded Survivable Network Design Problem.

[BibT_eX]

[DOI]

Anand Louis

Proceedings of the Algorithm Theory, 2010

2009

Deterministically testing sparse polynomial identities of unbounded degree.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

Connections Between Unique Games and Multicut.

[BibT_eX]

[DOI]

David Steurer

Electron. Colloquium Comput. Complex., 2009

On the Optimality of a Class of LP-based Algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Algorithms and Hardness for Subspace Approximation

[BibT_eX]

[DOI]

Amit Deshpande

Kasturi R. Varadarajan

Madhur Tulsiani

CoRR, 2009

A Spectral Algorithm for Improving Graph Partitions

[BibT_eX]

[DOI]

Michael W. Mahoney

CoRR, 2009

On the Fourier spectrum of symmetric Boolean functions.

[BibT_eX]

[DOI]

Mihail N. Kolountzakis

Comb., 2009

2008

On partitioning graphs via single commodity flows.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Unique games on expanding constraint graphs are easy: extended abstract.

[BibT_eX]

[DOI]

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

[BibT_eX]

[DOI]

Proceedings of the High Performance Computing, 2007

2006

Integrality gaps for sparsest cut and minimum linear arrangement problems.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005

Caching with Expiration Times for Internet Applications.

[BibT_eX]

[DOI]

Internet Math., 2005

The Impact of Noise on the Scaling of Collectives: A Theoretical Approach.

[BibT_eX]

[DOI]

Saurabh Agarwal

Rahul Garg

Proceedings of the High Performance Computing, 2005

On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas.

[BibT_eX]

[DOI]

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

Theoretical Aspects of Randomization in Computation.

[BibT_eX]

[DOI]

PhD thesis, 2004

On the Complexity of Hilbert's 17th Problem.

[BibT_eX]

[DOI]

Nikhil R. Devanur

Richard J. Lipton

Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

2003

Deterministic identity testing for multivariate polynomials.

[BibT_eX]

[DOI]

Richard J. Lipton

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Who's The Weakest Link?

[BibT_eX]

[DOI]

Nikhil R. Devanur

Richard J. Lipton

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2003

Non Uniform Random Walks.

[BibT_eX]

[DOI]