

Afonso S. Bandeira
contact info Prof. Dr. Afonso Bandeira HG G 23.1, ETH Zurich, Ramistrasse 101 8092 Zurich, Switzerland Professor of Mathematics, ETH Zurich Administration: Annette Ryter annette [dot] ryter [at] ifor [dot] math [dot] ethz [dot] ch






Group Members: Antoine Maillard, March Boedihardjo, Pedro Abdalla, Daniil Dmitriev, Konstantin Donhauser, Anastasia Kireeva, Petar NizicNikolac. Published manuscripts by the group available at the ETH Research Collection. Publications Submitted, In Press, and selected Preprints On the concentration of Gaussian Cayley matrices A. S. Bandeira, D. Kunisky, D. G. Mixon, X. Zeng arXiv:2212.00066 [math.FA], 2022 [arXiv] Expander graphs are globally synchronising P. Abdalla, A. S. Bandeira, M. Kassabov, V. Souza, S. H. Strogatz, A. Townsend arXiv:2210.12788 [math.CO], 2022 [arXiv] Guarantees for Spontaneous Synchronization on Random Geometric Graphs P. Abdalla, A. S. Bandeira, C. Invernizzi arXiv:2208.12246 [math.PR], 2022 [arXiv] On free energy barriers in Gaussian priors and failure of cold start MCMC for highdimensional unimodal distributions A. S. Bandeira, A. Maillard, R. Nickl, S. Wang Philosophical Transactions of the Royal Society A, to appear. [arXiv] Matrix Concentration Inequalities and Free Probability A. S. Bandeira, M. T. Boedihardjo, R. van Handel arXiv:2108.06312 [math.PR], 2021 [arXiv] SubexponentialTime Algorithms for Sparse PCA Y. Ding, D. Kunisky, A. S. Wein, A. S. Bandeira Journal of the FoCM, to appear. [arXiv] [related video] A Gramian Description of the Degree 4 Generalized Elliptope A. S. Bandeira, D. Kunisky arXiv:1812.11583 [math.OC], 2018. [arXiv] Estimation under group actions: recovering orbits from invariants A. S. Bandeira, B. BlumSmith, Joe Kileel, A. Perry, J. Weed, A. S. Wein arXiv:1712.10163 [math.ST], 2017. [arXiv] [related video] Books, Lecture Notes and Monographs Mathematics of Data Science (draft) A. S. Bandeira, A. Singer, T. Strohmer Book in preparation See here for videos of lectures on this material (*Disclaimer: they were prepared due to the Covid19 pandemic, and are not polished or highquality, I include them here in case they are still useful) Ten Lectures and FortyTwo Open Problems in the Mathematics of Data Science A. S. Bandeira Lecture Notes, December 2015. See also MIT OCW page for a course based on this notes Mathematics of Machine Learning A. S. Bandeira and N. Zhivotovskiy Lecture Notes (undergraduate course), Spring 2021, ETH Zurich See here for videos of lectures on this material More available at my teaching page PeerReviewed Publications A remark on Kashin's discrepancy argument and partial coloring in the Komlós conjecture A. S. Bandeira, A. Maillard, N. Zhivotovskiy Port. Math. 79 (2022), no. 3/4, pp. 311–316, 2022 [arXiv] [article] The FranzParisi Criterion and Computational Tradeoffs in High Dimensional Statistics A. S. Bandeira, A. El Alaoui, S. B. Hopkins, T. Schramm, A. S. Wein, I. Zadik NeurIPS 2022, Oral Presentation. [arXiv] [article] Dual bounds for the positive definite functions approach to mutually unbiased bases A. S. Bandeira, N. Doppelbauer, D. Kunisky Sampling Theory, Signal Processing, and Data Analysis (SaSiDa) 20, 2022 [arXiv] [article] Community Detection with a Subsampled Semidefinite Program P. Abdalla, A. S. Bandeira Sampling Theory, Signal Processing, and Data Analysis (SaSiDa) 20, 2022 [arXiv] [article] Computationally efficient sparse clustering M. Loffler, A. S. Wein, A. S. Bandeira Information and Inference: A Journal of the IMA, Volume 11, Issue 4, Pages 1255–1286, 2022. [arXiv] [article] Notes on Computational Hardness of Hypothesis Testing: Predictions using the LowDegree Likelihood Ratio D. Kunisky, A. S. Wein, A. S. Bandeira In: Cerejeiras, P., Reissig, M. (eds) Mathematical Analysis, its Applications and Computation. ISAAC 2019. Springer Proceedings in Mathematics & Statistics, vol 385, 2022. [arXiv] [related video] [article] AverageCase Integrality Gap for NonNegative Principal Component Analysis D. Kunisky, A. S. Wein, A. S. Bandeira MSML 2021 [arXiv] [article] Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs A. S. Bandeira, J. Banks, D. Kunisky, C. Moore, A. S. Wein COLT 2021 [arXiv] [video] The Spectral Norm of Random Lifts of Matrices A. S. Bandeira, Y. Ding Electron. Commun. Probab. 26: 110 (2021) [arXiv] [paper] The AverageCase Time Complexity of Certifying the Restricted Isometry Property Y. Ding, D. Kunisky, A. S. Wein, A. S. Bandeira IEEE Transactions on Information Theory (Volume: 67, Issue: 11, November 2021) [arXiv] [article] Group Testing in the High Dilution G. Arpino, N. Grometo, A. S. Bandeira ISIT 2021 [arXiv] [article] Likelihood Maximization and Moment Matching in Low SNR Gaussian Mixture Models A. Katsevich, A. S. Bandeira Communications on Pure and Applied Mathematics, 2022. [arXiv] [article] A Tight Degree 4 SumofSquares Lower Bound for the SherringtonKirkpatrick Hamiltonian D. Kunisky, A. S. Bandeira, Mathematical Programming, 190, pages 721–759 (2021) [arXiv] [article] Nonunique games over compact groups and orientation estimation in cryoEM A. S. Bandeira, Y. Chen, R. Lederman, and A. Singer Inverse Problems, Volume 36, Number 6 Special Issue on CryoElectron Microscopy and Inverse Problems, 2020. [arXiv] [paper] Statistical limits of spiked tensor models A. Perry, A. S. Wein, and A. S. Bandeira Annales de l'Institut Henri Poincare  Probabilites et Statistiques, Vol. 56, No. 1, 230264, 2020. [arXiv] [paper] Deterministic guarantees for BurerMonteiro factorizations of smooth semidefinite programs N. Boumal, V. Voroninski, and A. S. Bandeira Communications on Pure and Applied Mathematics, Volume 73, Issue 3, 2020. [arXiv] [article] Computational Hardness of Certifying Bounds on Constrained PCA Problems A. S. Bandeira, D. Kunisky, A. S. Wein Innovations in Theoretical Computer Science (ITCS’20), 2020. [arXiv] [paper] [related video] Optimal rates of estimation for multireference alignment A. S. Bandeira, P. Rigollet, J. Weed Mathematical Statistics and Learning, Volume 2, Issue 1, 2019, pp. 2575. [arXiv] [related video] Spurious Valleys in Onehiddenlayer Neural Network Optimization Landscapes L. Venturi, A. S. Bandeira, J. Bruna Journal of Machine Learning Research (JMLR), 20(133):134, 2019. [arXiv] [paper] Previous title: Spurious Valleys in Twolayer Neural Network Optimization Landscapes Earlier version preprint: Neural Networks with Finite Intrinsic Dimension have no Spurious Valleys Experimental performance of graph neural networks on random instances of maxcut W. Yao, A. S. Bandeira, S. Villar SPIE Wavelets and Sparsity 2019. [arXiv] Connections between sumofsquares optimization and structured tight frames A. S. Bandeira, D. Kunisky SPIE Wavelets and Sparsity 2019. [pdf] On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization S. Ling, R. Xu, A. S. Bandeira SIAM Journal on Optimization (SIOPT), 29(3), 1879–1907, 2019 [arXiv] The sample complexity of multireference alignment A. Perry, J. Weed, A. S. Bandeira, P. Rigollet, A. Singer SIAM Journal on Mathematics of Data Science (SIMODS), Vol. 1, No. 3, pp. 497517, 2019. [arXiv] [related video] SumofSquares Optimization and the Sparsity Structure of Equiangular Tight Frames A. S. Bandeira, D. Kunisky SampTA Sampling Theory and Applications, 13th International Conference, 2019. [arXiv] SESync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group D. M. Rosen, L. Carlone, A. S. Bandeira, and J. J. Leonard International Journal of Robotics Research, International Journal of Robotics Research, Vol 38, Issue 23, 2019. [code] [technical report] [corrigendum] Notes on computationaltostatistical gaps: predictions using statistical physics A. S. Bandeira, A. Perry, A. S. Wein Portugaliae Mathematica, Portugaliae Mathematica, Vol 75, issue 2, pages 159186, 2018. [arXiv] A Revised note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks A. Nowak, S. Villar, A. S. Bandeira, J. Bruna IEEE Data Science Workshop, 2018. [arXiv] Optimality and Suboptimality of PCA I: Spiked Random Matrix Models A. Perry, A. S. Wein, A. S. Bandeira, and A. Moitra Annals of Statistics, Annals of Statistics, Volume 46, Number 5, pp. 24162451, 2018. [arXiv] [related video] Longer technical report: Optimality and Suboptimality of PCA for Spiked Random Matrices and Synchronization. [arXiv] [related video]  A. Perry and A. Wein awarded 2018 Jonhson prize (MIT) for this paper. Messagepassing algorithms for synchronization problems over compact groups A. Perry, A. S. Wein, A. S. Bandeira, A. Moitra Communications on Pure and Applied Mathematics, Communications on Pure and Applied Mathematics, Volume 71, Issue 11, Pages 22752322, 2018. [arXiv] [related video] Random Laplacian matrices and convex relaxations A. S. Bandeira Foundations of Computational Mathematics, Foundations of Computational Mathematics, 18, pages 345–379(2018). [arXiv] [bibtex] Multisection in the stochastic block model using semidefinite programming N. Agarwal, A. S. Bandeira, K. Koiliaris, A. Kolla Compressed Sensing and its Applications: MATHEON Workshop 2015 (Applied and Numerical Harmonic Analysis), 125162, 2018. [arXiv] [bibtex] Compressive classification and the rare eclipse problem A. S. Bandeira, D. G. Mixon, and B. Recht Compressed Sensing and its Applications: MATHEON Workshop 2015 (Applied and Numerical Harmonic Analysis), 197220, 2018. [arXiv] [bibtex] [blog entry] Discrete uncertainty principles and sparse signal processing A. S. Bandeira, M. E. Lewis, and D. G. Mixon Journal of Fourier Analysis and Applications, Journal of Fourier Analysis and Applications, volume 24, pages 935–956(2018) [arXiv] [bibtex] [paper] Resilience for the LittlewoodOfford Problem A. S. Bandeira, A. Ferber, and M. Kwan Advances in Mathematics vol. 319, pp. 292312, 2017. [paper] [arXiv] A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks A. Nowak, S. Villar, A. S. Bandeira, J. Bruna ICML 2017 Workshop on Principled Approaches to Deep Learning (PADL), 2017. [arXiv] MarcenkoPastur Law for Kendall's Tau A. S. Bandeira, A. Lodhia, P. Rigollet Electronic Communications in Probability, Vol. 22, paper no. 32, 17, 2017. [paper][arXiv] Community Detection in Hypergraphs, Spiked Tensor Models, and SumofSquares C. Kim, A. S. Bandeira, M. X. Goemans SampTA Sampling Theory and Applications, 12th International Conference, 2017. [arXiv] Tightness of the maximum likelihood semidefinite relaxation for angular synchronization A. S. Bandeira, N. Boumal, and A. Singer Mathematical Programming SERIES A (2017) 163: 145167. [arXiv] [bibtex] [article] [SharedIt] A conditional construction of restricted isometries A. S. Bandeira, D. G. Mixon, and J. Moreira International Mathematics Research Notices (2017) 2017:372381. [arXiv] [bibtex] [blog entry] A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group D. M. Rosen, L. Carlone, A. S. Bandeira, and J. J. Leonard Workshop on the Algorithmic Foundations of Robotics (WAFR) , 2016. [arXiv] [code]  Best paper award at WAFR 2016. The nonconvex BurerMonteiro approach works on smooth semidefinite programs N. Boumal, V. Voroninski, and A. S. Bandeira Neural Information Processing Systems, NIPS 2016. [arXiv] [bibtex] On the lowrank approach for semidefinite programs arising in synchronization and community detection A. S. Bandeira, N. Boumal, and V. Voroninski Conference on Learning Theory (COLT), 2016. [arXiv] [bibtex] Approximating the little Grothendieck problem over the orthogonal and unitary Groups A. S. Bandeira, C. Kennedy, and A. Singer Mathematical Programming SERIES A (2016) 160: 433475. [arXiv] [bibtex] [blog entry] [related blog entry] Linear Boolean classification, coding and ''the critical problem'' E. Abbe, N. Alon, A. S. Bandeira, and C. Sandon IEEE Transactions on Information Theory (2016) 62: 16671673. [arXiv] [bibtex] [blog entry] Conference Proceedings version: Linear Boolean classification, coding and ''the critical problem'' at IEEE International Symposium on Information Theory (ISIT 2014), 2014. A note on Probably Certifiably Correct algorithms A. S. Bandeira Comptes Rendus Mathematique (2016) 354: 329333, to appear, 2016. [arXiv] [bibtex] Derandomizing restricted isometries via the Legendre symbol A. S. Bandeira, M. Fickus, D. G. Mixon, and J. Moreira Constructive Approximation (2016) 43: 409424. [arXiv] [bibtex] [paper] Sharp nonasymptotic bounds on the norm of random matrices with independent entries A. S. Bandeira and R. v. Handel Annals of Probability (2016) 44: 24792506. [arXiv] [bibtex] [blog entry] [related video part 1 and part 2] Exact Recovery in the Stochastic Block Model E. Abbe, A. S. Bandeira, G. Hall IEEE Transactions on Information Theory, vol.62, no.1, pp.471487, 2016. [paper] [arXiv] [bibtex] [related lecture notes] [related video]  2020 Information Theory Society Paper Award Relax, no need to round: integrality of clustering formulations P. Awasthi, A. S. Bandeira, M. Charikar, R. Krishnaswamy, S. Villar, and R. Ward 6th Innovations in Theoretical Computer Science (ITCS 2015). [arXiv] [bibtex] [errata] Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery E. Abbe, A. S. Bandeira, A. Bracher, and A. Singer Transactions on Network Science and Engineering, 1(1), pp.1020, 2014. [arXiv] [bibtex] [blog entry] [related blog entry] Open problem: Tightness of maximum likelihood semidefinite relaxations A. S. Bandeira, Y. Khoo, and A. Singer COLT Open Problem, JMLR W&CP 35: 12651267, 2014. [arXiv] [bibtex] [blog entry] Convergence of trustregion methods based on probabilistic models A. S. Bandeira, K. Scheinberg, and L. N. Vicente SIAM Journal on Optimization (SIOPT), 24(3), pp. 12381264, 2014 [paper] [arXiv] [bibtex] Linear Inverse problems on ErdosRenyi graphs: Informationtheoretic limits and efficient recovery E. Abbe, A. S. Bandeira, A. Bracher, and A. Singer IEEE International Symposium on Information Theory (ISIT 2014), 2014. [paper] [bibtex] [blog entry] [related blog entry] Phase retrieval from power spectra of masked signals A. S. Bandeira, Y. Chen, and D. G. Mixon Information and Inference: a Journal of the IMA, vol. 3, pp. 83102, 2014. [arXiv] [bibtex] [blog entry] [code] Multireference alignment using semidefinite programming A. S. Bandeira, M. Charikar, A. Singer, and A. Zhu 5th Innovations in Theoretical Computer Science (ITCS 2014), 2014. [final paper] [arXiv] [bibtex] Saving phase: Injectivity and stability for phase retrieval A. S. Bandeira, J. Cahill, D. G. Mixon, and A. A. Nelson Applied and Computational Harmonic Analysis (ACHA), vol. 37, pp. 106125, 2014. [final paper] [arXiv] [bibtex] [blog entry] Conference Proceedings version: Fundamental limits of phase retrieval at 10th International Conference on Sampling Theory and Applications, 2013. A Cheeger inequality for the graph connection Laplacian A. S. Bandeira, A. Singer, and D. A. Spielman SIAM Journal on Matrix Analysis and Applications (SIMAX), vol. 34, pp. 16111630, 2013. [final paper] [arXiv] [bibtex] [blog entry] Phase retrieval with polarization B. Alexeev, A. S. Bandeira, M. Fickus, and D. G. Mixon SIAM Journal on Imaging Sciences (SIIMS), vol. 7, pp. 3566, 2013 [final paper] [arXiv] [bibtex] [blog entry] The road to deterministic matrices with the restricted isometry property A. S. Bandeira, M. Fickus, D. G. Mixon, and P. Wong Journal of Fourier Analysis and Applications, vol. 19, pp. 11231149, 2013. [final paper] [arxiv] [bibtex] [blog entry]  Best student paper award at the 36th Annual SIAM Southeastern Atlantic Section Conference, 2012. Certifying the restricted isometry property is hard A. S. Bandeira, E. Dobriban, D. G. Mixon, and W. Sawin IEEE Transactions on Information Theory, vol. 59, pp. 34483450,2013 [final paper] [arxiv] [bibtex] [blog entry] Nearoptimal
phase retrieval of sparse vectors A. S. Bandeira, K. Scheinberg, and L. N. Vicente Mathematical Programming, vol. 134, pp. 223257, 2012 [final paper] [arxiv] [bibtex] [blog entry]  INFORMS Optimization Society student paper prize, 2013. Landau's necessary density conditions for the Hankel transform L. D. Abreu and A. S. Bandeira Journal of Functional Analysis, vol. 262, pp. 18451866, 2012 [final paper] [arxiv] [bibtex] [blog entry] Technical Reports, Theses, Preprints, Unpublished Manuscripts, and other Articles The spectral norm of Gaussian matrices with correlated entries A. S. Bandeira, M. T. Boedihardjo arXiv:2104.02662 [math.PR], 2021 [arXiv] Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach C. Kim, A. S. Bandeira, M. X. Goemans arXiv:1807.02884 [math.PR], 2018. [arXiv] Inference on Graphs via Semidefinite Programming A. S. Bandeira Proceedings of the National Academy of Sciences Commentary, 2016. [article] [preprint] A polynomialtime relaxation of the GromovHausdorff distance S. Villar, A. S. Bandeira, A. J. Blumberg, and R. Ward arXiv:1610.05214 [math.GT], 2016. [arXiv] Optimality and Suboptimality of PCA for Spiked Random Matrices and Synchronization A. Perry, A. S. Wein, A. S. Bandeira, and A. Moitra arXiv:1609.05573 [math.ST], 2016. [arXiv] Efficient Algorithm for Exact Recovery of Vertex Variables from Edge Measurements A. S. Bandeira Spotlight on Transactions, IEEE Computer, to appear, 2015 [preprint] Nonunique games over compact groups (Extended Abstract) A. S. Bandeira Oberwolfach Report (38/2015), 2015. Convex relaxations for certain inverse problems on graphs A. S. Bandeira PhD Thesis, Program in Applied and Computational Mathematics, Princeton University, 2015 [thesis] [bibtex] Sparse recovery in
derivativefree optimization Estimating
group transformations via convex relaxation On partially
sparse recovery A. S. Bandeira Master Thesis, Dep. Matematica, Univ. Coimbra, 2010 [thesis] [bibtex] [blog entry] 
