Efficient Algorithms for High-Dimensional Estimation
back to top
-
Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point,
with Hongjie Chen, Jingqiu Ding, Yiding Hua
NeurIPS 2025, arxiv
-
SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More,
with Ilias Diakonikolas, Samuel Hopkins, Ankit Pensia
STOC 2025, arxiv
-
SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications,
with Ilias Diakonikolas, Samuel Hopkins, Ankit Pensia
STOC 2025, arxiv
Invited to SICOMP Special Issue for STOC 2025
-
Testably Learning Polynomial Threshold Functions,
with Lucas Slot, Manuel Wiedmer
NeurIPS 2024, arxiv
-
Robust Mixture Learning when Outliers Overwhelm Small Groups,
with Daniil Dmitriev, Rares Buhai, Alexander Wolters, Gleb Novikov, Amartya Sanyal, David Steurer, Fanny Yang
NeurIPS 2024, arxiv (author ordering by contribution)
-
Robust Mean Estimation Without Moments for Symmetric Distributions,
with Gleb Novikov, David Steurer,
NeurIPS 2023, arxiv
-
Fast algorithm for overcomplete order-3 tensor decomposition,
with Jingqiu Ding, Tommaso
d’Orsi, Chih-Hung Liu, David
Steurer,
COLT 2022, arxiv
-
Consistent Estimation for PCA and Sparse Regression with Oblivious
Outliers,
with Tommaso d’Orsi, Chih-Hung
Liu, Rajai Nasser, Gleb Novikov, David Steurer,
NeurIPS
2021, arxiv
-
SoS Degree Reduction with Applications to Clustering and Robust
Moment Estimation,
with David Steurer,
SODA 2021, arxiv
Recipient of the ETH medal for outstanding master theses
Computational Complexity of Average-Case Problems
back to top
-
Rigorous Implications of the Low-Degree Heuristic,
with Jun-Ting Hsieh, Daniel Kane, Pravesh Kothari, Jerry Li, Sidhanth Mohanty
STOC 2026, arxiv
-
Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations,
with Kiril Bangachev, Guy Bresler, Vinod Vaikuntanathan
STOC 2025, arxiv
-
Improved Hardness Results for Learning Intersections of Halfspaces,
COLT 2024, arxiv
Best Student Paper Award
-
Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression,
with Rares Buhai, Jingqiu Ding,
COLT 2024, arxiv
-
Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice
Problems,
COLT 2023, arxiv
-
Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise,
with Rajai Nasser,
COLT 2022, arxiv
Differentially Private Algorithms
back to top
-
Sample-Optimal Private Regression in Polynomial Time,
with Prashanti Anderson, Ainesh Bakshi, Mahbod Majid
STOC 2025, arxiv
-
Private estimation algorithms for stochastic block models and mixture models,
with Hongjie Chen, Vincent
Cohen-Addad, Tommaso
d’Orsi, Alessandro Epasto, Jacob Imola, David Steurer,
NeurIPS 2023 (spotlight), arxiv