Boolean Matrix Multiplication Lower Bounds
summary
Proves explicit lower bounds for restricted “combinatorial” Boolean matrix multiplication: the classic Angluin model (binary union circuits) needs Ω(n^2 / log n) unions, and a more realistic model that allows continuous block splitting and concatenation still forces super‑quadratic cost — roughly Ω(n^{2+1/3}/2^{O(√log n)}). The proof builds a tripartite instance from Ruzsa–Szemerédi graphs with many vertex pairs joined by a unique middle vertex; the construction yields the claimed unconditional separations.
AI-written summary · about