Hardness of sampling solutions from the Symmetric Binary Perceptron.
CoRR, 2024
Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree.
Random Struct. Algorithms, October, 2023
Fast relaxation of the random field Ising dynamics.
CoRR, 2023
An Information-Theoretic View of Stochastic Localization.
IEEE Trans. Inf. Theory, 2022
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022
Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022
Efficient Z<sub>2</sub> synchronization on Z<sup>d</sup> under symmetry-preserving side information.
CoRR, 2021
Algorithmic pure states for the negative spherical perceptron.
CoRR, 2020
Decoding From Pooled Data: Phase Transitions of Message Passing.
IEEE Trans. Inf. Theory, 2019
Decoding from Pooled Data: Sharp Information-Theoretic Bounds.
SIAM J. Math. Data Sci., 2019
On the computational tractability of statistical estimation on amenable graphs.
CoRR, 2019
The Kikuchi Hierarchy and Tensor PCA.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019
Tight query complexity lower bounds for PCA via finite sample deformed wigner law.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018
Estimation in the Spiked Wigner Model: A Short Proof of the Replica Formula.
Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018
Detection limits in the high-dimensional spiked rectangular model.
Proceedings of the Conference On Learning Theory, 2018
Finite Size Corrections and Likelihood Ratio Fluctuations in the Spiked Wigner Model.
CoRR, 2017
On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation.
CoRR, 2017
Asymptotic behavior of ℓ<sub>p</sub>-based Laplacian regularization in semi-supervised learning.
CoRR, 2016
Asymptotic behavior of \(\ell_p\)-based Laplacian regularization in semi-supervised learning.
Proceedings of the 29th Conference on Learning Theory, 2016
Fast Randomized Kernel Ridge Regression with Statistical Guarantees.
Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015
Computing the log-determinant of symmetric, diagonally dominant matrices in near-linear time.
CoRR, 2014
Fast Randomized Kernel Methods With Statistical Guarantees.
CoRR, 2014