From the 1 of 7 linked papers with an AI index.
7 papers
The Hypergraph Moore Bound
Afonso S. Bandeira, Dmitriy Kunisky, Petar NiziÄ-Nikolac +2
The paper proves Feige’s hypergraph Moore bound for all even uniformities (k ≥ 4) without extra polylogarithmic factors, using colored walks in a Kikuchi graph and a polynomial int…
Exact threshold for approximate ellipsoid fitting of random points
Afonso S. Bandeira, Antoine Maillard
We consider the problem of exactly fitting an ellipsoid (centered at ) to standard Gaussian random vectors in , as with $n / d^2 \t…
Average-case complexity in statistical inference: A puzzle-driven research seminar
Anastasia Kireeva, Afonso S. Bandeira
These notes describe our experience with running a student seminar on average-case complexity in statistical inference using the jigsaw learning format at ETH Zurich in Fall of 202…
Randomstrasse101: Open Problems of 2024
Afonso S. Bandeira, Anastasia Kireeva, Antoine Maillard +1
is a blog dedicated to Open Problems in Mathematics, with a focus on Probability Theory, Computation, Combinatorics, Statistics, and related topics. Thi…
The Lovász number of random circulant graphs
Afonso S. Bandeira, JarosÅaw BÅasiok, Daniil Dmitriev +3
This paper addresses the behavior of the Lovász number for dense random circulant graphs. The Lovász number is a well-known semidefinite programming upper bound on the independen…
Nonconvex landscapes for synchronization and graph clustering are benign near exact recovery thresholds
Andrew D. McRae, Pedro Abdalla, Afonso S. Bandeira +1
We study the optimization landscape of a smooth nonconvex program arising from synchronization over the two-element group , that is, recovering $z_1, \dots, z_n \in \…