Afonso S. Bandeira

Clara Invernizzi

SIAM J. Appl. Dyn. Syst., March, 2024

Computational lower bounds for multi-frequency group synchronization.

[BibT_eX]

[DOI]

Anastasia Kireeva

CoRR, 2024

2023

Exact threshold for approximate ellipsoid fitting of random points.

[BibT_eX]

[DOI]

Antoine Maillard

CoRR, 2023

Fitting an ellipsoid to a quadratic number of random points.

[BibT_eX]

[DOI]

CoRR, 2023

Injectivity of ReLU networks: perspectives from statistical physics.

[BibT_eX]

[DOI]

CoRR, 2023

2022

On free energy barriers in Gaussian priors and failure of MCMC for high-dimensional unimodal distributions.

[BibT_eX]

[DOI]

CoRR, 2022

A remark on Kashin's discrepancy argument and partial coloring in the Komlós conjecture.

[BibT_eX]

[DOI]

Antoine Maillard

Nikita Zhivotovskiy

CoRR, 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

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

Group Testing in the High Dilution Regime.

[BibT_eX]

[DOI]

Gabriel Arpino

Nicolò Grometto

Proceedings of the IEEE International Symposium on Information 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

Computationally efficient sparse clustering.

[BibT_eX]

[DOI]

Matthias Löffler

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

The Sample Complexity of Multireference Alignment.

[BibT_eX]

[DOI]

SIAM J. Math. Data Sci., 2019

On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization.

[BibT_eX]

[DOI]

Shuyang Ling

Ruitu Xu

SIAM J. Optim., 2019

Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes.

[BibT_eX]

[DOI]

Luca Venturi

Joan Bruna

J. Mach. Learn. Res., 2019

SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group.

[BibT_eX]

[DOI]

Int. J. Robotics Res., 2019

Experimental performance of graph neural networks on random instances of max-cut.

[BibT_eX]

[DOI]

Weichi Yao

Soledad Villar

CoRR, 2019

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

[BibT_eX]

[DOI]

CoRR, 2019

2018

Random Laplacian Matrices and Convex Relaxations.

[BibT_eX]

[DOI]

Found. Comput. Math., 2018

Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach.

[BibT_eX]

[DOI]

Chiheon Kim

Michel X. Goemans

CoRR, 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

Neural Networks with Finite Intrinsic Dimension have no Spurious Valleys.

[BibT_eX]

[DOI]

Luca Venturi

Joan Bruna

CoRR, 2018

Revised Note on Learning Quadratic Assignment with Graph Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the 2018 IEEE Data Science Workshop, 2018

2017

Tightness of the maximum likelihood semidefinite relaxation for angular synchronization.

[BibT_eX]

[DOI]

Nicolas Boumal

Math. Program., 2017

Resilience for the Littlewood-Offord Problem.

[BibT_eX]

[DOI]

Asaf Ferber

Matthew Kwan

Electron. Notes Discret. Math., 2017

Estimation under group actions: recovering orbits from invariants.

[BibT_eX]

[DOI]

CoRR, 2017

The sample complexity of multi-reference alignment.

[BibT_eX]

[DOI]

CoRR, 2017

A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks.

[BibT_eX]

[DOI]

CoRR, 2017

Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares.

[BibT_eX]

[DOI]

Chiheon Kim

Michel X. Goemans

CoRR, 2017

2016

Exact Recovery in the Stochastic Block Model.

[BibT_eX]

[DOI]

Emmanuel Abbe

Georgina Hall

IEEE Trans. Inf. Theory, 2016

Linear Boolean Classification, Coding and the Critical Problem.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2016

Approximating the little Grothendieck problem over the orthogonal and unitary groups.

[BibT_eX]

[DOI]

Christopher Kennedy

Math. Program., 2016

A polynomial-time relaxation of the Gromov-Hausdorff distance.

[BibT_eX]

[DOI]

CoRR, 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

A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Foundations of Robotics XII, 2016

The non-convex Burer-Monteiro approach works on smooth semidefinite programs.

[BibT_eX]

[DOI]

Nicolas Boumal

Vladislav Voroninski

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

On the low-rank approach for semidefinite programs arising in synchronization and community detection.

[BibT_eX]

[DOI]

Nicolas Boumal

Vladislav Voroninski

Proceedings of the 29th Conference on Learning Theory, 2016

2015

Convex Relaxations for Certain Inverse Problems on Graphs

[BibT_eX]

[DOI]

PhD thesis, 2015

Discrete uncertainty principles and sparse signal processing.

[BibT_eX]

[DOI]

Megan E. Lewis

CoRR, 2015

Non-unique games over compact groups and orientation estimation in cryo-EM.

[BibT_eX]

[DOI]

Yutong Chen

CoRR, 2015

A note on Probably Certifiably Correct algorithms.

[BibT_eX]

[DOI]

CoRR, 2015

Multisection in the Stochastic Block Model using Semidefinite Programming.

[BibT_eX]

[DOI]

Naman Agarwal

Konstantinos Koiliaris

Alexandra Kolla

CoRR, 2015

An Efficient Algorithm for Exact Recovery of Vertex Variables from Edge Measurements.

[BibT_eX]

[DOI]

Computer, 2015

Relax, No Need to Round: Integrality of Clustering Formulations.

[BibT_eX]

[DOI]

Pranjal Awasthi

Moses Charikar

Ravishankar Krishnaswamy

Soledad Villar

Rachel A. Ward

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

2014

Decoding Binary Node Labels from Censored Edge Measurements: Phase Transition and Efficient Recovery.

[BibT_eX]

[DOI]

IEEE Trans. Netw. Sci. Eng., 2014

Convergence of Trust-Region Methods Based on Probabilistic Models.

[BibT_eX]

[DOI]

Katya Scheinberg

Luís Nunes Vicente

SIAM J. Optim., 2014

Phase Retrieval with Polarization.

[BibT_eX]

[DOI]

SIAM J. Imaging Sci., 2014

Compressive classification and the rare eclipse problem.

[BibT_eX]

[DOI]

Benjamin Recht

CoRR, 2014

A conditional construction of restricted isometries.

[BibT_eX]

[DOI]

Joel Moreira

CoRR, 2014

Derandomizing restricted isometries via the Legendre symbol.

[BibT_eX]

[DOI]

CoRR, 2014

Linear inverse problems on Erdős-Rényi graphs: Information-theoretic limits and efficient recovery.

[BibT_eX]

[DOI]

Proceedings of the 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, June 29, 2014

Linear Boolean classification, coding and "the critical problem".

[BibT_eX]

[DOI]

Emmanuel Abbe

Noga Alon

Proceedings of the 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, June 29, 2014

Multireference alignment using semidefinite programming.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2014

Open Problem: Tightness of maximum likelihood semidefinite relaxations.

[BibT_eX]

[DOI]

Yuehaw Khoo

Proceedings of The 27th Conference on Learning Theory, 2014

2013

Certifying the Restricted Isometry Property is Hard.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2013

A Cheeger Inequality for the Graph Connection Laplacian.

[BibT_eX]

[DOI]

Daniel A. Spielman

SIAM J. Matrix Anal. Appl., 2013

On partial sparse recovery

[BibT_eX]

[DOI]

Katya Scheinberg

Luís Nunes Vicente

CoRR, 2013

Phase retrieval from power spectra of masked signals

[BibT_eX]

[DOI]

Yutong Chen

CoRR, 2013

Near-optimal phase retrieval of sparse vectors.

[BibT_eX]

[DOI]

CoRR, 2013

Approximating the Little Grothendieck Problem over the Orthogonal Group.

[BibT_eX]

[DOI]

Christopher Kennedy

CoRR, 2013

2012

Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization.

[BibT_eX]

[DOI]