Allen Liu

CoRR, 2024

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

[BibT_eX]

[DOI]

Sitan Chen

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

Learning Quantum Hamiltonians at Any Temperature in Polynomial Time.

[BibT_eX]

[DOI]

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

Structure Learning of Hamiltonians from Real-Time Evolution.

[BibT_eX]

[DOI]

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

High-Temperature Gibbs States are Unentangled and Efficiently Preparable.

[BibT_eX]

[DOI]

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

2023

Robustly Learning General Mixtures of Gaussians.

[BibT_eX]

[DOI]

J. ACM, June, 2023

A New Approach to Learning Linear Dynamical Systems.

[BibT_eX]

[DOI]

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

Robust Voting Rules from Algorithmic Robust Statistics.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Constant Approximation for Individual Preference Stable Clustering.

[BibT_eX]

[DOI]

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

Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Matrix Completion in Almost-Verification Time.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 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

The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination.

[BibT_eX]

[DOI]

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

Semi-Random Sparse Recovery in Nearly-Linear Time.

[BibT_eX]

[DOI]

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

2022

Tight Bounds for State Tomography with Incoherent Measurements.

[BibT_eX]

[DOI]

CoRR, 2022

Clustering mixtures with almost optimal separation in polynomial time.

[BibT_eX]

[DOI]

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

Robust Model Selection and Nearly-Proper Learning for GMMs.

[BibT_eX]

[DOI]

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

Minimax Rates for Robust Community Detection.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 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

The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication.

[BibT_eX]

[DOI]

Mark Sellke

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

Learning GMMs with Nearly Optimal Robustness Guarantees.

[BibT_eX]

[DOI]

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

2021

Sparsification for Sums of Exponentials and its Algorithmic Applications.

[BibT_eX]

[DOI]

CoRR, 2021

How to Decompose a Tensor with Group Structure.

[BibT_eX]

[DOI]

CoRR, 2021

Settling the robust learnability of mixtures of Gaussians.

[BibT_eX]

[DOI]

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

Optimal Contextual Pricing and Extensions.

[BibT_eX]

[DOI]

Renato Paes Leme

Jon Schneider

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Variable Decomposition for Prophet Inequalities and Optimal Ordering.

[BibT_eX]

[DOI]

Balasubramanian Sivan

Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

Margin-Independent Online Multiclass Learning via Convex Geometry.

[BibT_eX]

[DOI]

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

Distributed Load Balancing: A New Framework and Improved Guarantees.

[BibT_eX]

[DOI]

Sara Ahmadian

Binghui Peng

Morteza Zadimoghaddam

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

Competing Optimally Against An Imperfect Prophet.

[BibT_eX]

[DOI]

Balasubramanian Sivan

CoRR, 2020

Contextual Search for General Hypothesis Classes.

[BibT_eX]

[DOI]

Renato Paes Leme

Jon Schneider

CoRR, 2020

Tensor Completion Made Practical.

[BibT_eX]

[DOI]

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

Myersonian Regression.

[BibT_eX]

[DOI]

Renato Paes Leme

Jon Schneider

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

Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

2019

Fourier and Circulant Matrices are Not Rigid.

[BibT_eX]

[DOI]

Zeev Dvir

Electron. Colloquium Comput. Complex., 2019

2018

Efficiently Learning Mixtures of Mallows Models.

[BibT_eX]

[DOI]