publications

2026

1. 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).