Sitan Chen

Allen Liu

CoRR, 2024

Faster Diffusion-based Sampling with Randomized Midpoints: Sequential and Parallel.

[BibT_eX]

[DOI]

Shivam Gupta

Linda Cai

CoRR, 2024

Learning general Gaussian mixtures with efficient score matching.

[BibT_eX]

[DOI]

Vasilis Kontonis

Kulin Shah

CoRR, 2024

Provably learning a multi-head attention layer.

[BibT_eX]

[DOI]

Yuanzhi Li

CoRR, 2024

An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography.

[BibT_eX]

[DOI]

Allen Liu

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Critical windows: non-asymptotic theory for feature emergence in diffusion models.

[BibT_eX]

[DOI]

Marvin Li

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Optimal Tradeoffs for Estimating Pauli Observables.

[BibT_eX]

[DOI]

Weiyuan Gong

Qi Ye

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

A faster and simpler algorithm for learning shallow networks.

[BibT_eX]

[DOI]

Shyam Narayanan

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Futility and utility of a few ancillas for Pauli channel learning.

[BibT_eX]

[DOI]

Weiyuan Gong

CoRR, 2023

Learning Polynomial Transformations via Generalized Tensor Decompositions.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Learning Mixtures of Gaussians Using the DDPM Objective.

[BibT_eX]

[DOI]

Kulin Shah

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

The probability flow ODE is provably fast.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-type Samplers.

[BibT_eX]

[DOI]

Giannis Daras

Alex Dimakis

Proceedings of the International Conference on Machine Learning, 2023

Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions.

[BibT_eX]

[DOI]

Proceedings of the Eleventh International Conference on Learning Representations, 2023

When Does Adaptivity Help for Quantum State Learning?

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Learning Narrow One-Hidden-Layer ReLU Networks.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Learning to predict arbitrary quantum processes.

[BibT_eX]

[DOI]

Hsin-Yuan Huang

John Preskill

CoRR, 2022

The Complexity of NISQ.

[BibT_eX]

[DOI]

CoRR, 2022

Tight Bounds for State Tomography with Incoherent Measurements.

[BibT_eX]

[DOI]

CoRR, 2022

Learning Polynomial Transformations.

[BibT_eX]

[DOI]

CoRR, 2022

Kalman filtering with adversarial corruptions.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Learning (Very) Simple Generative Models Is Hard.

[BibT_eX]

[DOI]

Yuanzhi Li

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Symmetric Sparse Boolean Matrix Factorization and Applications.

[BibT_eX]

[DOI]

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs.

[BibT_eX]

[DOI]

Proceedings of the Tenth International Conference on Learning Representations, 2022

Tight Bounds for Quantum State Certification with Incoherent Measurements.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Toward Instance-Optimal State Certification With Incoherent Measurements.

[BibT_eX]

[DOI]

Ryan O'Donnell

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Rethinking Algorithm Design for Modern Challenges in Data Science.

[BibT_eX]

[DOI]

PhD thesis, 2021

Quantum advantage in learning from experiments.

[BibT_eX]

[DOI]

CoRR, 2021

A Hierarchy for Replica Quantum Advantage.

[BibT_eX]

[DOI]

CoRR, 2021

Efficiently Learning Any One Hidden Layer ReLU Network From Queries.

[BibT_eX]

[DOI]

CoRR, 2021

Symmetric Boolean Factor Analysis with Applications to InstaHide.

[BibT_eX]

[DOI]

CoRR, 2021

Algorithmic foundations for the diffraction limit.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Efficiently Learning One Hidden Layer ReLU Networks From Queries.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

On InstaHide, Phase Retrieval, and Sparse Matrix Factorization.

[BibT_eX]

[DOI]

Proceedings of the 9th International Conference on Learning Representations, 2021

Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Learning Deep ReLU Networks Is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Exponential Separations Between Learning With and Without Quantum Memory.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

On InstaHide, Phase Retrieval, and Sparse Matrix Factorization.

[BibT_eX]

[DOI]

Zhao Song

Danyang Zhuo

CoRR, 2020

Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability.

[BibT_eX]

[DOI]

CoRR, 2020

Learning mixtures of linear regressions in subexponential time via Fourier moments.

[BibT_eX]

[DOI]

Zhao Song

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Efficiently learning structured distributions from untrusted batches.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Evolvability.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Learning Structured Distributions From Untrusted Batches: Faster and Simpler.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Entanglement is Necessary for Optimal Quantum Property Testing.

[BibT_eX]

[DOI]

Sébastien Bubeck

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Learning Polynomials in Few Relevant Dimensions.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

2019

Beyond the low-degree algorithm: mixtures of subcubes and their applications.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Improved Bounds for Randomly Sampling Colorings via Linear Programming.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Linear Programming Bounds for Randomly Sampling Colorings.

[BibT_eX]

[DOI]

CoRR, 2018

Learning Mixtures of Product Distributions via Higher Multilinear Moments.

[BibT_eX]

[DOI]

CoRR, 2018

2016

Basis collapse for holographic algorithms over all domain sizes.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

Pseudorandomness for Read-Once, Constant-Depth Circuits.

[BibT_eX]

[DOI]

Thomas Steinke

Salil P. Vadhan

CoRR, 2015

2014

Cellular Automata to More Efficiently Compute the Collatz Map.

[BibT_eX]

[DOI]