85 citations · 237 across the 30 of their papers we have counts for
7 papers · 1 filter
Simple Graph Density Inequalities with no Sum of Squares Proofs
Grigoriy Blekherman, Annie Raymond, Mohit Singh +1
Establishing inequalities among graph densities is a central pursuit in extremal combinatorics. A standard tool to certify the nonnegativity of a graph density expression is to wri…
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh +3
Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rou…
The Price of Fair PCA: One Extra Dimension
Samira Samadi, Uthaipon Tantipongpipat, Jamie Morgenstern +2
We investigate whether the standard dimensionality reduction technique of PCA inadvertently produces data representations with different fidelity for two different populations. We…
Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency
Sebastian Perez-Salazar, Ishai Menache, Mohit Singh +1
Cloud computing has motivated renewed interest in resource allocation problems with new consumption models. A common goal is to share a resource, such as CPU or I/O bandwidth, amon…
Efficient algorithms for robust submodular maximization under matroid constraints
Sebastian Pokutta, Mohit Singh, Alfredo Torrico
In this work, we consider robust submodular maximization with matroid constraints. We give an efficient bi-criteria approximation algorithm that outputs a small family of feasible…
Approximation Algorithms for D-optimal Design
Mohit Singh, Weijun Xie
Experimental design is a classical statistics problem and its aim is to estimate an unknown -dimensional vector from linear measurements where a Gaussian noise is introduced…