6 citations · 39 across the 21 of their papers we have counts for
23 papers
Matrix Completion in Almost-Verification Time
Jonathan A. Kelner, Jerry Li, Allen Liu +2
We give a new framework for solving the fundamental problem of low-rank matrix completion, i.e., approximating a rank- matrix (where $m…
Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems
Ainesh Bakshi, Allen Liu, Ankur Moitra +1
Recently Chen and Poor initiated the study of learning mixtures of linear dynamical systems. While linear dynamical systems already have wide-ranging applications in modeling time-…
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination
Clément L. Canonne, Samuel B. Hopkins, Jerry Li +2
We consider the question of Gaussian mean testing, a fundamental task in high-dimensional distribution testing and signal processing, subject to adversarial corruptions of the samp…
A New Approach to Learning Linear Dynamical Systems
Ainesh Bakshi, Allen Liu, Ankur Moitra +1
Linear dynamical systems are the foundational statistical model upon which control theory is built. Both the celebrated Kalman filter and the linear quadratic regulator require kno…
Minimax Rates for Robust Community Detection
Allen Liu, Ankur Moitra
In this work, we study the problem of community detection in the stochastic block model with adversarial node corruptions. Our main result is an efficient algorithm that can tolera…
When Does Adaptivity Help for Quantum State Learning?
Sitan Chen, Brice Huang, Jerry Li +2
We consider the classic question of state tomography: given copies of an unknown quantum state , output which is close to in some sense,…
Tight Bounds for Quantum State Certification with Incoherent Measurements
Sitan Chen, Brice Huang, Jerry Li +1
We consider the problem of quantum state certification, where we are given the description of a mixed state , copies of a mixed state $ρ\in \mathb…
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…
The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication
Allen Liu, Mark Sellke
We study the stochastic multi-player multi-armed bandit problem. In this problem, players cooperate to maximize their total reward from arms. However the players cannot…
Robust Voting Rules from Algorithmic Robust Statistics
Allen Liu, Ankur Moitra
Maximum likelihood estimation furnishes powerful insights into voting theory, and the design of voting rules. However the MLE can usually be badly corrupted by a single outlying sa…
BERT_SE: A Pre-trained Language Representation Model for Software Engineering
Eliane Maria De Bortoli Fávero, Dalcimar Casanova
The application of Natural Language Processing (NLP) has achieved a high level of relevance in several areas. In the field of software engineering (SE), NLP applications are based…
Margin-Independent Online Multiclass Learning via Convex Geometry
Guru Guruganesh, Allen Liu, Jon Schneider +1
We consider the problem of multi-class classification, where a stream of adversarially chosen queries arrive and must be assigned a label online. Unlike traditional bounds which se…
Robust Model Selection and Nearly-Proper Learning for GMMs
Jerry Li, Allen Liu, Ankur Moitra
In learning theory, a standard assumption is that the data is generated from a finite mixture model. But what happens when the number of components is not known in advance? The pro…
Algorithms from Invariants: Smoothed Analysis of Orbit Recovery over
Allen Liu, Ankur Moitra
In this work we study orbit recovery over , where the goal is to recover a function on the sphere from noisy, randomly rotated copies of it. We assume that the function is a…
Learning GMMs with Nearly Optimal Robustness Guarantees
Allen Liu, Ankur Moitra
In this work we solve the problem of robustly learning a high-dimensional Gaussian mixture model with components from -corrupted samples up to accuracy in…
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…
Tensor Completion Made Practical
Allen Liu, Ankur Moitra
Tensor completion is a natural higher-order generalization of matrix completion where the goal is to recover a low-rank tensor from sparse observations of its entries. Existing alg…
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…
Bilinear generalized Radon transforms in the plane
Allan Greenleaf, Alex Iosevich, Ben Krause +1
Let be arc-length measure on and denote rotation by an angle . Define a model bilinear generalized Radon transform, $$B_θ(f,g)(x)=\int…
Wavelet decomposition and bandwidth of functions defined on vector spaces over finite fields
A. Iosevich, A. Liu, A. Mayeli +1
In this paper we study how zeros of the Fourier transform of a function are related to the structure of the function itself. In particular, we in…