Publication
Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
STACS 2025, 2025. PDF · Official record
Abstract
Proving formula depth lower bounds is a fundamental challenge in complexity theory, with the strongest known bound of \((3-o(1))\log n\) established by Håstad over 25 years ago. The Karchmer–Raz–Wigderson conjecture offers a promising approach to advance these bounds and separate P from NC¹. It suggests that the depth complexity of a function composition approximates the sum of the depth complexities of its components.
In this paper, we examine the strong composition of the Karchmer–Wigderson relations for the parity function and a random Boolean function. We prove that with probability \(1-o(1)\), any protocol solving this composition requires at least \(n^{3-o(1)}\) leaves. This establishes a depth lower bound of \((3-o(1))\log n\), matching Håstad’s bound, while applying to a broader class of inner functions.
Our proof combines formal complexity measures: Khrapchenko’s method first shows that many instances remain unsolved after several communication steps, and a second measure shows that the remaining problem is at least as hard as the corresponding OR composition.