publications

2026

1. Convergence of Kikuchi matrices to Γ-independent and q-Gaussian limits

   Afonso S. Bandeira, Dmitriy Kunisky, Petar Nizic-Nikolac, Lucas Pesenti, and Robert Wang

   Available online, 2026

   Abs arXiv

   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 random Kikuchi matrices have a limit described by a system of Γ-independent semicircular elements. This characterizes their limiting spectral distribution and yields improved bounds on their spectral norm, a key quantity in the analysis of algorithms for Tensor PCA. Finally, we show that, in an appropriate double limit, independent Kikuchi matrices converge to the q-Gaussian system, another central object in noncommutative probability.

2. Matrix Concentration and Equivalent Operators on Fock Spaces

   Afonso S. Bandeira, Dmitriy Kunisky, Petar Nizic-Nikolac, Lucas Pesenti, and Robert Wang

   Available online, 2026

   Abs arXiv

   We develop a method for proving matrix concentration inequalities by identifying random matrices with associated deterministic operators acting on suitable Fock spaces and controlling norms of these operators and their restrictions to low-order subspaces. Applying this method, we obtain new strengthenings of the non-commutative Khintchine inequality that improve on the state of the art, in particular sharpening recent inequalities due to Bandeira, Boedihardjo, and van Handel (2023) quantifying intrinsic freeness of random matrices. Our proofs of these results are based on relatively simple operator algebra arguments and involve neither Gaussian interpolation nor explicit combinatorics of tracial moments. Further, our techniques apply equally well to several models of non-commutative random variables of interest in the literature, such as operator series constructed from q-Gaussian and Γ-independent systems of operators, treating all of these objects with the same method. We obtain new norm bounds for such operators both in the style of the non-commutative Khintchine inequality and in the style of Lehner’s operator norm formula.

3. The Hypergraph Moore Bound

   Afonso S. Bandeira, Dmitriy Kunisky, Petar Nizic-Nikolac, Lucas Pesenti, and Robert Wang

   Available online, 2026

   Abs arXiv

   We prove Feige’s conjectured hypergraph Moore bound, which controls the size of the smallest even cover in a k-uniform hypergraph in terms of the average density of hyperedges. We give a simple proof of Feige’s original conjecture for all k ≥3, with no superfluous polylogarithmic factors. Our method uses colored walks in Kikuchi graphs together with polynomial methods in the even-uniform case, and extends to odd-uniform hypergraphs via an adapted procedure.

2025

1. Matrix Chaos Inequalities and Chaos of Combinatorial Type

   Afonso S. Bandeira, Kevin Lucca, Petar Nizic-Nikolac, and Ramon van Handel

   In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Prague, Czechia, 2025

   Abs DOI arXiv

   Matrix concentration inequalities and their recently discovered sharp counterparts provide powerful tools to bound the spectrum of random matrices whose entries are linear functions of independent random variables. However, in many applications in theoretical computer science and in other areas one encounters more general random matrix models, called matrix chaoses, whose entries are polynomials of independent random variables. Such models have often been studied on a case-by-case basis using ad-hoc methods that can yield suboptimal dimensional factors. In this paper we provide general matrix concentration inequalities for matrix chaoses, which enable the treatment of such models in a systematic manner. These inequalities are expressed in terms of flattenings of the coefficients of the matrix chaos. We further identify a special family of matrix chaoses of combinatorial type for which the flattening parameters can be computed mechanically by a simple rule. This allows us to provide a unified treatment of and improved bounds for matrix chaoses that arise in a variety of applications, including graph matrices, Khatri-Rao matrices, and matrices that arise in average case analysis of the sum-of-squares hierarchy.

2023

1. The bunkbed conjecture holds in the p↑1 limit

   Tom Hutchcroft, Alexander Kent, and Petar Nizic-Nikolac

   Combinatorics, Probability and Computing, 2023

   Abs DOI arXiv

   Let G=(V,E) be a countable graph. The Bunkbed graph of G is the product graph G \times K_2, which has vertex set V\times {0,1} with “horizontal” edges inherited from G and additional “vertical” edges connecting (w,0) and (w,1) for each w ∈V. Kasteleyn’s Bunkbed conjecture states that for each u,v ∈V and p∈[0,1], the vertex (u,0) is at least as likely to be connected to (v,0) as to (v,1) under Bernoulli-p bond percolation on the bunkbed graph. We prove that the conjecture holds in the p ↑1 limit in the sense that for each finite graph G there exists \varepsilon (G)\gt 0 such that the bunkbed conjecture holds for p \geqslant 1-\varepsilon (G).