9 papers
Convergence of Kikuchi matrices to -independent and -Gaussian limits
Afonso S. Bandeira, Dmitriy Kunisky, Petar Nizić-Nikolac +2
Kikuchi matrices are a family of structured matrices that were introduced to study problems involving tensors and hypergraphs. We show that, as the ambient dimension grows, dense r…
Matrix Concentration and Equivalent Operators on Fock Spaces
Afonso S. Bandeira, Dmitriy Kunisky, Petar Nizić-Nikolac +2
We develop a method for proving matrix concentration inequalities by identifying random matrices with associated deterministic operators acting on suitable Fock spaces and controll…
The Hypergraph Moore Bound
Afonso S. Bandeira, Dmitriy Kunisky, Petar Nizić-Nikolac +2
The hypergraph Moore bound conjectured by Feige (2008) controls the size of the smallest even cover in a -uniform hypergraph in terms of the average density of hyperedges. An ev…
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 independence…
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 \…
Computational lower bounds for multi-frequency group synchronization
Anastasia Kireeva, Afonso S. Bandeira, Dmitriy Kunisky
We consider a group synchronization problem with multiple frequencies which involves observing pairwise relative measurements of group elements on multiple frequency channels, corr…
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…