Afonso S. Bandeira

96 papers A* 6A 3B 3C 1Journal 79Unranked 3

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