1 citations · 1 across the 1 of their papers we have counts for
6 papers
Semi-Random Sparse Recovery in Nearly-Linear Time
Jonathan A. Kelner, Jerry Li, Allen Liu +2
Sparse recovery is one of the most fundamental and well-studied inverse problems. Standard statistical formulations of the problem are provably solved by general convex programming…
Settling the Robust Learnability of Mixtures of Gaussians
Allen Liu, Ankur Moitra
This work represents a natural coalescence of two important lines of work: learning mixtures of Gaussians and algorithmic robust statistics. In particular we give the first provabl…
Variable Decomposition for Prophet Inequalities and Optimal Ordering
Allen Liu, Renato Paes Leme, Martin Pal +2
We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number o…
Optimal Contextual Pricing and Extensions
Allen Liu, Renato Paes Leme, Jon Schneider
In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in and only observes the purchasing decisi…
Fourier and Circulant Matrices are Not Rigid
Zeev Dvir, Allen Liu
The concept of matrix rigidity was first introduced by Valiant in 1977. Roughly speaking, a matrix is rigid if its rank cannot be reduced significantly by changing a small number o…
Efficiently Learning Mixtures of Mallows Models
Allen Liu, Ankur Moitra
Mixtures of Mallows models are a popular generative model for ranking data coming from a heterogeneous population. They have a variety of applications including social choice, reco…