Dmitriy Kunisky

IEEE Trans. Inf. Theory, October, 2024

Subexponential-Time Algorithms for Sparse PCA.

[BibT_eX]

[DOI]

Found. Comput. Math., June, 2024

The Spectrum of the Grigoriev-Laurent Pseudomoments.

[BibT_eX]

[DOI]

Cristopher Moore

SIAM J. Discret. Math., March, 2024

Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models.

[BibT_eX]

[DOI]

CoRR, 2024

Statistical inference of a ranked community in a directed graph.

[BibT_eX]

[DOI]

CoRR, 2024

On the Structure of Bad Science Matrices.

[BibT_eX]

[DOI]

CoRR, 2024

Inference of rankings planted in random tournaments.

[BibT_eX]

[DOI]

Daniel A. Spielman

Xifan Yu

CoRR, 2024

Computational lower bounds for multi-frequency group synchronization.

[BibT_eX]

[DOI]

Anastasia Kireeva

CoRR, 2024

Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing.

[BibT_eX]

[DOI]

CoRR, 2024

Optimality of Glauber dynamics for general-purpose Ising model sampling and free energy approximation.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Computational Hardness of Detecting Graph Lifts and Certifying Lift-Monotone Properties of Random Regular Graphs.

[BibT_eX]

[DOI]

Xifan Yu

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Tensor Cumulants for Statistical Inference on Invariant Distributions.

[BibT_eX]

[DOI]

Cristopher Moore

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., June, 2023

Linear Programming and Community Detection.

[BibT_eX]

[DOI]

Alberto Del Pia

Aida Khajavirad

Math. Oper. Res., May, 2023

Online Algorithms and Lower Bounds for Average-Case Matrix Discrepancy.

[BibT_eX]

[DOI]

Peiyuan Zhang

CoRR, 2023

Generic MANOVA limit theorems for products of projections.

[BibT_eX]

[DOI]

CoRR, 2023

A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph.

[BibT_eX]

[DOI]

Xifan Yu

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Strong recovery of geometric planted matchings.

[BibT_eX]

[DOI]

Jonathan Niles-Weed

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021

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

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2021

A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian.

[BibT_eX]

[DOI]

Math. Program., 2021

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

[BibT_eX]

[DOI]

Proceedings of the Mathematical and Scientific Machine Learning, 2021

Hypothesis testing with low-degree polynomials in the Morris class of exponential families.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 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

Positivity-preserving extensions of sum-of-squares pseudomoments over the hypercube.

[BibT_eX]

[DOI]

CoRR, 2020

Computational Hardness of Certifying Bounds on Constrained PCA Problems.

[BibT_eX]

[DOI]

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

2019

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

[BibT_eX]

[DOI]