202 citations · 1.3k across the 61 of their papers we have counts for
5 papers · 1 filter
A note on Probably Certifiably Correct algorithms
Afonso S. Bandeira
Many optimization problems of interest are known to be intractable, and while there are often heuristics that are known to work on typical instances, it is usually not easy to dete…
Multisection in the Stochastic Block Model using Semidefinite Programming
Naman Agarwal, Afonso S. Bandeira, Konstantinos Koiliaris +1
We consider the problem of identifying underlying community-like structures in graphs. Towards this end we study the Stochastic Block Model (SBM) on -clusters: a random model on…
Non-unique games over compact groups and orientation estimation in cryo-EM
Afonso S. Bandeira, Yutong Chen, Amit Singer
Let be a compact group and let . We define the Non-Unique Games (NUG) problem as finding to minimize $\su…
Random Laplacian matrices and convex relaxations
Afonso S. Bandeira
The largest eigenvalue of a matrix is always larger or equal than its largest diagonal entry. We show that for a large class of random Laplacian matrices, this bound is essentially…
Discrete uncertainty principles and sparse signal processing
Afonso S. Bandeira, Megan E. Lewis, Dustin G. Mixon
We develop new discrete uncertainty principles in terms of numerical sparsity, which is a continuous proxy for the 0-norm. Unlike traditional sparsity, the continuity of numerical…