57 citations · 478 across the 75 of their papers we have counts for
86 papers
Delegation and Verification Under AI
Lingxiao Huang, Wenyang Xiao, Nisheeth K. Vishnoi
As AI systems enter institutional workflows, workers must decide whether to delegate task execution to AI and how much effort to invest in verifying AI outputs, while institutions…
Path Dependence under Adaptive AI Delegation
Lingxiao Huang, Nisheeth K. Vishnoi
Repeated AI assistance can improve immediate task performance while reducing the skill available for future independent work. We develop a mathematical framework for this long-run…
Matchings Under Biased and Correlated Evaluations
Amit Kumar, Nisheeth K. Vishnoi
We study a two-institution stable matching model in which candidates from two distinct groups are evaluated using partially correlated signals that are group-biased. This extends p…
Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy
Phuc Tran, Nisheeth K. Vishnoi, Van H. Vu
A central challenge in machine learning is to understand how noise or measurement errors affect low-rank approximations, particularly in the spectral norm. This question is especia…
Perturbation Bounds for Low-Rank Inverse Approximations under Noise
Phuc Tran, Nisheeth K. Vishnoi
Low-rank pseudoinverses are widely used to approximate matrix inverses in scalable machine learning, optimization, and scientific computing. However, real-world matrices are often…
Coresets for Clustering Under Stochastic Noise
Lingxiao Huang, Zhize Li, Nisheeth K. Vishnoi +2
We study the problem of constructing coresets for -clustering when the input dataset is corrupted by stochastic noise drawn from a known distribution. In this setting, eval…
Strategic Costs of Perceived Bias in Fair Selection
L. Elisa Celis, Lingxiao Huang, Milind Sohoni +1
Meritocratic systems, from admissions to hiring, aim to impartially reward skill and effort. Yet persistent disparities across race, gender, and class challenge this ideal. Some at…
A Mathematical Framework for AI-Human Integration in Work
L. Elisa Celis, Lingxiao Huang, Nisheeth K. Vishnoi
The rapid rise of Generative AI (GenAI) tools has sparked debate over their role in complementing or replacing human workers across job contexts. We present a mathematical framewor…
Efficient Diffusion Models for Symmetric Manifolds
Oren Mangoubi, Neil He, Nisheeth K. Vishnoi
We introduce a framework for designing efficient diffusion models for -dimensional symmetric-space Riemannian manifolds, including the torus, sphere, special orthogonal group an…
Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations
Oren Mangoubi, Nisheeth K. Vishnoi
We consider the problem of approximating a covariance matrix with a rank- matrix under -differential privacy. We present and analyze a complex…
Centralized Selection with Preferences in the Presence of Biases
L. Elisa Celis, Amit Kumar, Nisheeth K. Vishnoi +1
This paper considers the scenario in which there are multiple institutions, each with a limited capacity for candidates, and candidates, each with preferences over the institutions…
Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers
Oren Mangoubi, Nisheeth K. Vishnoi
We consider the problem of sampling from a log-concave distribution constrained to a polytope , where $A\in \mathbb{R}^…
Bias in Evaluation Processes: An Optimization-Based Model
L. Elisa Celis, Amit Kumar, Anay Mehrotra +1
Biases with respect to socially-salient attributes of individuals have been well documented in evaluation processes used in settings such as admissions and hiring. We view such an…
On the works of Avi Wigderson
Boaz Barak, Yael Kalai, Ran Raz +2
This is an overview of some of the works of Avi Wigderson, 2021 Abel prize laureate. Wigderson's contributions span many fields of computer science and mathematics. In this survey…
Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex Gaussian Perturbations
Oren Mangoubi, Nisheeth K. Vishnoi
We consider the problem of approximating a covariance matrix with a rank- matrix under -differential privacy. We present and analyze a complex…
Subset Selection Based On Multiple Rankings in the Presence of Bias: Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions
Niclas Boehmer, L. Elisa Celis, Lingxiao Huang +2
We consider the problem of subset selection where one is given multiple rankings of items and the goal is to select the highest ``quality'' subset. Score functions from the multiwi…
Maximizing Submodular Functions for Recommendation in the Presence of Biases
Anay Mehrotra, Nisheeth K. Vishnoi
Subset selection tasks, arise in recommendation systems and search engines and ask to select a subset of items that maximize the value for the user. The values of subsets often dis…
Fair Ranking with Noisy Protected Attributes
Anay Mehrotra, Nisheeth K. Vishnoi
The fair-ranking problem, which asks to rank a given set of items to maximize utility subject to group fairness constraints, has received attention in the fairness, information ret…
Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion
Oren Mangoubi, Nisheeth K. Vishnoi
Given a symmetric matrix and a vector , we present new bounds on the Frobenius-distance utility of the Gaussian mechanism for approximating by a matrix whose spectrum is…
Private Matrix Approximation and Geometry of Unitary Orbits
Oren Mangoubi, Yikai Wu, Satyen Kale +2
Consider the following optimization problem: Given matrices and , maximize where varies over the unitary group . Th…
Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk
Oren Mangoubi, Nisheeth K. Vishnoi
Given a Lipschitz or smooth convex function for a bounded polytope defined by inequalities, we consider the problem of sampli…
Selection in the Presence of Implicit Bias: The Advantage of Intersectional Constraints
Anay Mehrotra, Bary S. R. Pradelski, Nisheeth K. Vishnoi
In selection processes such as hiring, promotion, and college admissions, implicit bias toward socially-salient attributes such as race, gender, or sexual orientation of candidates…
Fairness for AUC via Feature Augmentation
Hortense Fong, Vineet Kumar, Anay Mehrotra +1
We study fairness in the context of classification where the performance is measured by the area under the curve (AUC) of the receiver operating characteristic. AUC is commonly use…
Sampling from Log-Concave Distributions with Infinity-Distance Guarantees
Oren Mangoubi, Nisheeth K. Vishnoi
For a -dimensional log-concave distribution constrained to a convex body , the problem of outputting samples from a distribution which is $\varep…