Alexander S. Wein

SIAM J. Comput., February, 2024

Low-degree phase transitions for detecting a planted clique in sublinear time.

[BibT_eX]

[DOI]

Jay Mardia

Kabir Aladin Verchand

CoRR, 2024

Information-Theoretic Thresholds for Planted Dense Cycles.

[BibT_eX]

[DOI]

Shenduo Zhang

CoRR, 2024

2023

Time Lower Bounds for the Metropolis Process and Simulated Annealing.

[BibT_eX]

[DOI]

CoRR, 2023

Detection of Dense Subhypergraphs by Low-Degree Polynomials.

[BibT_eX]

[DOI]

Abhishek Dhawan

CoRR, 2023

Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials.

[BibT_eX]

[DOI]

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

Is It Easier to Count Communities Than Find Them?

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Near-optimal fitting of ellipsoids to random points.

[BibT_eX]

[DOI]

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

Detection-Recovery Gap for Planted Dense Cycles.

[BibT_eX]

[DOI]

Shenduo Zhang

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

Is Planted Coloring Easier than Planted Clique?

[BibT_eX]

[DOI]

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

2022

The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics.

[BibT_eX]

[DOI]

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

Lattice-Based Methods Surpass Sum-of-Squares in Clustering.

[BibT_eX]

[DOI]

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

Statistical and Computational Phase Transitions in Group Testing.

[BibT_eX]

[DOI]

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

2021

The Average-Case Time Complexity of Certifying the Restricted Isometry Property.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2021

Circuit Lower Bounds for the p-Spin Optimization Problem.

[BibT_eX]

[DOI]

David Gamarnik

Aukosh Jagannath

CoRR, 2021

Optimal Spectral Recovery of a Planted Vector in a Subspace.

[BibT_eX]

[DOI]

CoRR, 2021

Average-Case Integrality Gap for Non-Negative Principal Component Analysis.

[BibT_eX]

[DOI]

Dmitriy Kunisky

Proceedings of the Mathematical and Scientific Machine Learning, 2021

Counterexamples to the Low-Degree Conjecture.

[BibT_eX]

[DOI]

Justin Holmgren

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

Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Optimal Low-Degree Hardness of Maximum Independent Set.

[BibT_eX]

[DOI]

CoRR, 2020

Computational Barriers to Estimation from Low-Degree Polynomials.

[BibT_eX]

[DOI]

Tselil Schramm

CoRR, 2020

Computationally efficient sparse clustering.

[BibT_eX]

[DOI]

Matthias Löffler

CoRR, 2020

Computational Hardness of Certifying Bounds on Constrained PCA Problems.

[BibT_eX]

[DOI]

Dmitriy Kunisky

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Low-Degree Hardness of Random Optimization Problems.

[BibT_eX]

[DOI]

David Gamarnik

Aukosh Jagannath

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Free Energy Wells and Overlap Gap Property in Sparse PCA.

[BibT_eX]

[DOI]

Gérard Ben Arous

Ilias Zadik

Proceedings of the Conference on Learning Theory, 2020

2019

Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio.

[BibT_eX]

[DOI]

Dmitriy Kunisky

CoRR, 2019

Subexponential-Time Algorithms for Sparse PCA.

[BibT_eX]

[DOI]

CoRR, 2019

Spectral methods from tensor networks.

[BibT_eX]

[DOI]

Ankur Moitra

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

The Kikuchi Hierarchy and Tensor PCA.

[BibT_eX]

[DOI]

Ahmed El Alaoui

Cristopher Moore

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Overcomplete Independent Component Analysis via SDP.

[BibT_eX]

[DOI]

Anastasia Podosinnikova

Amelia Perry

Francis R. Bach

Alexandre d'Aspremont

David A. Sontag

Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

2018

Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models.

[BibT_eX]

[DOI]

CoRR, 2018

Notes on computational-to-statistical gaps: predictions using statistical physics.

[BibT_eX]

[DOI]

Amelia Perry

CoRR, 2018

2017

Estimation under group actions: recovering orbits from invariants.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Message-passing algorithms for synchronization problems over compact groups.

[BibT_eX]

[DOI]

CoRR, 2016

Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization.

[BibT_eX]

[DOI]

CoRR, 2016

Statistical limits of spiked tensor models.

[BibT_eX]

[DOI]

Amelia Perry

CoRR, 2016

How robust are reconstruction thresholds for community detection?

[BibT_eX]

[DOI]

Ankur Moitra

William Perry

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

A semidefinite program for unbalanced multisection in the stochastic block model.

[BibT_eX]

[DOI]

William Perry