2024
Near-Optimal Trace Reconstruction for Mildly Separated Strings.
CoRR, 2024
Model Stealing for Any Low-Rank Language Model.
CoRR, 2024
Optimal high-precision shadow estimation.
CoRR, 2024
An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024
Learning Quantum Hamiltonians at Any Temperature in Polynomial Time.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024
Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting.
Proceedings of the Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, 2024
Structure Learning of Hamiltonians from Real-Time Evolution.
Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024
High-Temperature Gibbs States are Unentangled and Efficiently Preparable.
Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024
2023
Robustly Learning General Mixtures of Gaussians.
J. ACM, June, 2023
A New Approach to Learning Linear Dynamical Systems.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023
Robust Voting Rules from Algorithmic Robust Statistics.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023
Constant Approximation for Individual Preference Stable Clustering.
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.
Proceedings of the International Conference on Machine Learning, 2023
Matrix Completion in Almost-Verification Time.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023
When Does Adaptivity Help for Quantum State Learning?
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.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023
Semi-Random Sparse Recovery in Nearly-Linear Time.
Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023
2022
Tight Bounds for State Tomography with Incoherent Measurements.
CoRR, 2022
Clustering mixtures with almost optimal separation in polynomial time.
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.
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.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022
Tight Bounds for Quantum State Certification with Incoherent Measurements.
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.
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022
Learning GMMs with Nearly Optimal Robustness Guarantees.
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022
2021
Sparsification for Sums of Exponentials and its Algorithmic Applications.
CoRR, 2021
How to Decompose a Tensor with Group Structure.
CoRR, 2021
Settling the robust learnability of mixtures of Gaussians.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021
Optimal Contextual Pricing and Extensions.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
Variable Decomposition for Prophet Inequalities and Optimal Ordering.
Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021
Margin-Independent Online Multiclass Learning via Convex Geometry.
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.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021
2020
Competing Optimally Against An Imperfect Prophet.
CoRR, 2020
Contextual Search for General Hypothesis Classes.
CoRR, 2020
Tensor Completion Made Practical.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020
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.
Proceedings of the Conference on Learning Theory, 2020
2019
Fourier and Circulant Matrices are Not Rigid.
Electron. Colloquium Comput. Complex., 2019
2018
Efficiently Learning Mixtures of Mallows Models.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018