Disordered systems insights on computational hardness
D Gamarnik, C Moore… - Journal of Statistical …, 2022 - iopscience.iop.org
In this review article we discuss connections between the physics of disordered systems,
phase transitions in inference problems, and computational hardness. We introduce two …
phase transitions in inference problems, and computational hardness. We introduce two …
Beyond worst-case analysis
T Roughgarden - Communications of the ACM, 2019 - dl.acm.org
Beyond worst-case analysis Page 1 88 COMMUNICATIONS OF THE ACM | MARCH 2019 |
VOL. 62 | NO. 3 review articles COMPARING DIFFERENT ALGORITHMS is hard. For almost …
VOL. 62 | NO. 3 review articles COMPARING DIFFERENT ALGORITHMS is hard. For almost …
Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio
These notes survey and explore an emerging method, which we call the low-degree
method, for understanding statistical-versus-computational tradeoffs in high-dimensional …
method, for understanding statistical-versus-computational tradeoffs in high-dimensional …
The Franz-Parisi criterion and computational trade-offs in high dimensional statistics
Many high-dimensional statistical inference problems are believed to possess inherent
computational hardness. Various frameworks have been proposed to give rigorous …
computational hardness. Various frameworks have been proposed to give rigorous …
Reducibility and statistical-computational gaps from secret leakage
M Brennan, G Bresler - Conference on Learning Theory, 2020 - proceedings.mlr.press
Inference problems with conjectured statistical-computational gaps are ubiquitous
throughout modern statistics, computer science, statistical physics and discrete probability …
throughout modern statistics, computer science, statistical physics and discrete probability …
The power of sum-of-squares for detecting hidden structures
We study planted problems-finding hidden structures in random noisy inputs-through the
lens of the sum-of-squares semidefinite programming hierarchy (SoS). This family of …
lens of the sum-of-squares semidefinite programming hierarchy (SoS). This family of …
Noisy tensor completion via the sum-of-squares hierarchy
In the noisy tensor completion problem we observe m entries (whose location is chosen
uniformly at random) from an unknown n_1\times n_2\times n_3 tensor T. We assume that T …
uniformly at random) from an unknown n_1\times n_2\times n_3 tensor T. We assume that T …
A precise high-dimensional asymptotic theory for boosting and minimum--norm interpolated classifiers
A precise high-dimensional asymptotic theory for boosting and minimum-l1-norm
interpolated classifiers Page 1 The Annals of Statistics 2022, Vol. 50, No. 3, 1669–1695 …
interpolated classifiers Page 1 The Annals of Statistics 2022, Vol. 50, No. 3, 1669–1695 …
[HTML][HTML] Reducibility and computational lower bounds for problems with planted sparse structure
M Brennan, G Bresler… - Conference On Learning …, 2018 - proceedings.mlr.press
Recently, research in unsupervised learning has gravitated towards exploring statistical-
computational gaps induced by sparsity. A line of work initiated in Berthet and Rigollet …
computational gaps induced by sparsity. A line of work initiated in Berthet and Rigollet …
Computational barriers to estimation from low-degree polynomials
Computational barriers to estimation from low-degree polynomials Page 1 The Annals of
Statistics 2022, Vol. 50, No. 3, 1833–1858 https://doi.org/10.1214/22-AOS2179 © Institute of …
Statistics 2022, Vol. 50, No. 3, 1833–1858 https://doi.org/10.1214/22-AOS2179 © Institute of …