33 citations · 42 across the 7 of their papers we have counts for
9 papers
The Complexity of NISQ
Sitan Chen, Jordan Cotler, Hsin-Yuan Huang +1
The recent proliferation of NISQ devices has made it imperative to understand their computational power. In this work, we define and study the complexity class , wh…
Learning (Very) Simple Generative Models Is Hard
Sitan Chen, Jerry Li, Yuanzhi Li
Motivated by the recent empirical successes of deep generative models, we study the computational complexity of the following unsupervised learning problem. For an unknown neural n…
Learning Polynomial Transformations
Sitan Chen, Jerry Li, Yuanzhi Li +1
We consider the problem of learning high dimensional polynomial transformations of Gaussians. Given samples of the form , where is hidden and $p:…
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…
Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs
Sitan Chen, Jerry Li, Yuanzhi Li +1
Arguably the most fundamental question in the theory of generative adversarial networks (GANs) is to understand to what extent GANs can actually learn the underlying distribution.…
Learning Structured Distributions From Untrusted Batches: Faster and Simpler
Sitan Chen, Jerry Li, Ankur Moitra
We revisit the problem of learning from untrusted batches introduced by Qiao and Valiant [QV17]. Recently, Jain and Orlitsky [JO19] gave a simple semidefinite programming approach…