Afonso S. Bandeira

Publication Activity (10 Years)

Years Active: 2012-2024
Publications (10 Years): 55

Top Topics

Hypothesis Test

Intrinsic Dimension

Maximum Likelihood

Top Venues

IEEE Trans. Inf. Theory

Publications

Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
Subexponential-Time Algorithms for Sparse PCA. Found. Comput. Math. 24 (3) (2024)
Pedro Abdalla, Afonso S. Bandeira, Clara Invernizzi
Guarantees for Spontaneous Synchronization on Random Geometric Graphs. SIAM J. Appl. Dyn. Syst. 23 (1) (2024)
Anastasia Kireeva, Afonso S. Bandeira, Dmitriy Kunisky
Computational lower bounds for multi-frequency group synchronization. CoRR (2024)
Afonso S. Bandeira, Antoine Maillard, Shahar Mendelson, Elliot Paquette
Fitting an ellipsoid to a quadratic number of random points. CoRR (2023)
Antoine Maillard, Afonso S. Bandeira, David Belius, Ivan Dokmanic, Shuta Nakajima
Injectivity of ReLU networks: perspectives from statistical physics. CoRR (2023)
Antoine Maillard, Afonso S. Bandeira
Exact threshold for approximate ellipsoid fitting of random points. CoRR (2023)
Afonso S. Bandeira, Antoine Maillard, Richard Nickl, Sven Wang
On free energy barriers in Gaussian priors and failure of MCMC for high-dimensional unimodal distributions. CoRR (2022)
Afonso S. Bandeira, Antoine Maillard, Nikita Zhivotovskiy
A remark on Kashin's discrepancy argument and partial coloring in the Komlós conjecture. CoRR (2022)
Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, Ilias Zadik
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics. NeurIPS (2022)
Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, Ilias Zadik
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics. CoRR (2022)
Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein
Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs. COLT (2021)
Gabriel Arpino, Nicolò Grometto, Afonso S. Bandeira
Group Testing in the High Dilution Regime. ISIT (2021)
Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
Average-Case Integrality Gap for Non-Negative Principal Component Analysis. MSML (2021)
Gabriel Arpino, Nicolò Grometto, Afonso S. Bandeira
Group Testing in the High Dilution Regime. CoRR (2021)
Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
The Average-Case Time Complexity of Certifying the Restricted Isometry Property. IEEE Trans. Inf. Theory 67 (11) (2021)
Dmitriy Kunisky, Afonso S. Bandeira
A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian. Math. Program. 190 (1) (2021)
Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein
Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs. CoRR (2020)
Matthias Löffler, Alexander S. Wein, Afonso S. Bandeira
Computationally efficient sparse clustering. CoRR (2020)
Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
Average-Case Integrality Gap for Non-Negative Principal Component Analysis. CoRR (2020)
Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
Computational Hardness of Certifying Bounds on Constrained PCA Problems. ITCS (2020)
Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
The Average-Case Time Complexity of Certifying the Restricted Isometry Property. CoRR (2020)
Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
Subexponential-Time Algorithms for Sparse PCA. CoRR (2019)
Weichi Yao, Afonso S. Bandeira, Soledad Villar
Experimental performance of graph neural networks on random instances of max-cut. CoRR (2019)
Dmitriy Kunisky, Afonso S. Bandeira
A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian. CoRR (2019)
Luca Venturi, Afonso S. Bandeira, Joan Bruna
Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes. J. Mach. Learn. Res. 20 (2019)
Amelia Perry, Jonathan Weed, Afonso S. Bandeira, Philippe Rigollet, Amit Singer
The Sample Complexity of Multireference Alignment. SIAM J. Math. Data Sci. 1 (3) (2019)
Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
Computational Hardness of Certifying Bounds on Constrained PCA Problems. CoRR (2019)
Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio. CoRR (2019)
David M. Rosen, Luca Carlone, Afonso S. Bandeira, John J. Leonard
SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group. Int. J. Robotics Res. 38 (2-3) (2019)
Shuyang Ling, Ruitu Xu, Afonso S. Bandeira
On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization. SIAM J. Optim. 29 (3) (2019)
Alex Nowak, Soledad Villar, Afonso S. Bandeira, Joan Bruna
Revised Note on Learning Quadratic Assignment with Graph Neural Networks. DSW (2018)
Chiheon Kim, Afonso S. Bandeira, Michel X. Goemans
Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach. CoRR (2018)
Luca Venturi, Afonso S. Bandeira, Joan Bruna
Neural Networks with Finite Intrinsic Dimension have no Spurious Valleys. CoRR (2018)
Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra
Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models. CoRR (2018)
Afonso S. Bandeira, Amelia Perry, Alexander S. Wein
Notes on computational-to-statistical gaps: predictions using statistical physics. CoRR (2018)
Afonso S. Bandeira
Random Laplacian Matrices and Convex Relaxations. Found. Comput. Math. 18 (2) (2018)
Alex Nowak, Soledad Villar, Afonso S. Bandeira, Joan Bruna
A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks. CoRR (2017)
Afonso S. Bandeira, Nicolas Boumal, Amit Singer
Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Math. Program. 163 (1-2) (2017)
Afonso S. Bandeira, Ben Blum-Smith, Amelia Perry, Jonathan Weed, Alexander S. Wein
Estimation under group actions: recovering orbits from invariants. CoRR (2017)
Afonso S. Bandeira, Asaf Ferber, Matthew Kwan
Resilience for the Littlewood-Offord Problem. Electron. Notes Discret. Math. 61 (2017)
Chiheon Kim, Afonso S. Bandeira, Michel X. Goemans
Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares. CoRR (2017)
Amelia Perry, Jonathan Weed, Afonso S. Bandeira, Philippe Rigollet, Amit Singer
The sample complexity of multi-reference alignment. CoRR (2017)
David M. Rosen, Luca Carlone, Afonso S. Bandeira, John J. Leonard
A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group. CoRR (2016)
Soledad Villar, Afonso S. Bandeira, Andrew J. Blumberg, Rachel Ward
A polynomial-time relaxation of the Gromov-Hausdorff distance. CoRR (2016)
Nicolas Boumal, Vladislav Voroninski, Afonso S. Bandeira
The non-convex Burer-Monteiro approach works on smooth semidefinite programs. CoRR (2016)
Afonso S. Bandeira, Christopher Kennedy, Amit Singer
Approximating the little Grothendieck problem over the orthogonal and unitary groups. Math. Program. 160 (1-2) (2016)
Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra
Message-passing algorithms for synchronization problems over compact groups. CoRR (2016)
Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra
Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization. CoRR (2016)
Emmanuel Abbe, Afonso S. Bandeira, Georgina Hall
Exact Recovery in the Stochastic Block Model. IEEE Trans. Inf. Theory 62 (1) (2016)
Nicolas Boumal, Vladislav Voroninski, Afonso S. Bandeira
The non-convex Burer-Monteiro approach works on smooth semidefinite programs. NIPS (2016)
Afonso S. Bandeira, Nicolas Boumal, Vladislav Voroninski
On the low-rank approach for semidefinite programs arising in synchronization and community detection. COLT (2016)
David M. Rosen, Luca Carlone, Afonso S. Bandeira, John J. Leonard
A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group. WAFR (2016)
Amelia Perry, Alexander S. Wein, Afonso S. Bandeira
Statistical limits of spiked tensor models. CoRR (2016)
Emmanuel Abbe, Noga Alon, Afonso S. Bandeira, Colin Sandon
Linear Boolean Classification, Coding and the Critical Problem. IEEE Trans. Inf. Theory 62 (4) (2016)
David M. Rosen, Luca Carlone, Afonso S. Bandeira, John J. Leonard
SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group. CoRR (2016)
Afonso S. Bandeira
Random Laplacian matrices and convex relaxations. CoRR (2015)
Afonso S. Bandeira
An Efficient Algorithm for Exact Recovery of Vertex Variables from Edge Measurements. Computer 48 (9) (2015)
Afonso S. Bandeira, Megan E. Lewis, Dustin G. Mixon
Discrete uncertainty principles and sparse signal processing. CoRR (2015)
Naman Agarwal, Afonso S. Bandeira, Konstantinos Koiliaris, Alexandra Kolla
Multisection in the Stochastic Block Model using Semidefinite Programming. CoRR (2015)
Afonso S. Bandeira
A note on Probably Certifiably Correct algorithms. CoRR (2015)
Afonso S. Bandeira, Yutong Chen, Amit Singer
Non-unique games over compact groups and orientation estimation in cryo-EM. CoRR (2015)
Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, Rachel Ward
Relax, No Need to Round: Integrality of Clustering Formulations. ITCS (2015)
Emmanuel Abbe, Noga Alon, Afonso S. Bandeira
Linear Boolean classification, coding and "the critical problem". CoRR (2014)
Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, Rachel Ward
Relax, no need to round: integrality of clustering formulations. CoRR (2014)
Emmanuel Abbe, Afonso S. Bandeira, Annina Bracher, Amit Singer
Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery. CoRR (2014)
Afonso S. Bandeira, Yuehaw Khoo, Amit Singer
Open Problem: Tightness of maximum likelihood semidefinite relaxations. COLT (2014)
Afonso S. Bandeira, Matthew Fickus, Dustin G. Mixon, Joel Moreira
Derandomizing restricted isometries via the Legendre symbol. CoRR (2014)
Emmanuel Abbe, Afonso S. Bandeira, Georgina Hall
Exact Recovery in the Stochastic Block Model. CoRR (2014)
Emmanuel Abbe, Noga Alon, Afonso S. Bandeira
Linear Boolean classification, coding and "the critical problem". ISIT (2014)
Afonso S. Bandeira, Moses Charikar, Amit Singer, Andy Zhu
Multireference alignment using semidefinite programming. ITCS (2014)
Afonso S. Bandeira, Yuehaw Khoo, Amit Singer
Open problem: Tightness of maximum likelihood semidefinite relaxations. CoRR (2014)
Afonso S. Bandeira, Dustin G. Mixon, Joel Moreira
A conditional construction of restricted isometries. CoRR (2014)
Boris Alexeev, Afonso S. Bandeira, Matthew Fickus, Dustin G. Mixon
Phase Retrieval with Polarization. SIAM J. Imaging Sci. 7 (1) (2014)
Emmanuel Abbe, Afonso S. Bandeira, Annina Bracher, Amit Singer
Decoding Binary Node Labels from Censored Edge Measurements: Phase Transition and Efficient Recovery. IEEE Trans. Netw. Sci. Eng. 1 (1) (2014)
Emmanuel Abbe, Afonso S. Bandeira, Annina Bracher, Amit Singer
Linear inverse problems on Erdős-Rényi graphs: Information-theoretic limits and efficient recovery. ISIT (2014)
Afonso S. Bandeira, Katya Scheinberg, Luís Nunes Vicente
Convergence of Trust-Region Methods Based on Probabilistic Models. SIAM J. Optim. 24 (3) (2014)
Afonso S. Bandeira, Dustin G. Mixon, Benjamin Recht
Compressive classification and the rare eclipse problem. CoRR (2014)
Afonso S. Bandeira, Dustin G. Mixon
Near-optimal phase retrieval of sparse vectors. CoRR (2013)
Afonso S. Bandeira, Christopher Kennedy, Amit Singer
Approximating the Little Grothendieck Problem over the Orthogonal Group. CoRR (2013)
Afonso S. Bandeira, Edgar Dobriban, Dustin G. Mixon, William F. Sawin
Certifying the Restricted Isometry Property is Hard. IEEE Trans. Inf. Theory 59 (6) (2013)
Afonso S. Bandeira, Moses Charikar, Amit Singer, Andy Zhu
Multireference Alignment using Semidefinite Programming. CoRR (2013)
Afonso S. Bandeira, Yutong Chen, Dustin G. Mixon
Phase retrieval from power spectra of masked signals CoRR (2013)
Afonso S. Bandeira, Amit Singer, Daniel A. Spielman
A Cheeger Inequality for the Graph Connection Laplacian. SIAM J. Matrix Anal. Appl. 34 (4) (2013)
Afonso S. Bandeira, Katya Scheinberg, Luís Nunes Vicente
On partial sparse recovery CoRR (2013)
Afonso S. Bandeira, Edgar Dobriban, Dustin G. Mixon, William F. Sawin
Certifying the restricted isometry property is hard CoRR (2012)
Boris Alexeev, Afonso S. Bandeira, Matthew Fickus, Dustin G. Mixon
Phase retrieval with polarization CoRR (2012)
Afonso S. Bandeira, Katya Scheinberg, Luís Nunes Vicente
Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization. Math. Program. 134 (1) (2012)
Afonso S. Bandeira, Amit Singer, Daniel A. Spielman
A Cheeger Inequality for the Graph Connection Laplacian CoRR (2012)