Toward Better Depth Lower Bounds: Composition of Boolean Functions and the KRW Conjecture

Proving formula depth lower bounds is a fundamental challenge in complexity theory, with the strongest known bound of roughly $3\log n$ established by Håstad over 25 years ago. The Karchmer--Raz--Wigderson (KRW) conjecture offers a promising approach to advance these bounds and separate $\mathsf{P}$ from ${\mathsf{NC}}^1$. It suggests that the depth complexity of a function composition $f\diamond g$ approximates the sum of the depth complexities of $f$ and $g$.

The Karchmer--Wigderson (KW) relation framework translates formula depth into communication complexity, restating the KRW conjecture as $\mathsf{CC}({\mathsf{KW}}_f\diamond {\mathsf{KW}}_g)\approx \mathsf{CC}({\mathsf{KW}}_f)+\mathsf{CC}({\mathsf{KW}}_g)$. Prior work has confirmed the conjecture under various relaxations, often replacing one or both KW relations with the universal relation or constraining the communication game through strong composition.

The goal of this project is to resolve the KRW conjecture in the setting where the outer function is simple (for example, $\mathsf{XOR}$).

Report ​

In this work, we examine the strong composition ${\mathsf{KW}}_{\mathsf{XOR}}◯\ast {\mathsf{KW}}_f$ of the parity function and a random Boolean function $f$. During the project, we  proved that with probability $1-o(1)$, any protocol solving this composition requires at least $n^{3-o(1)}$ leaves (almost matching the upper bound). This result establishes a depth lower bound of $\approx 3\log n$, matching Håstad's bound, but is applicable to a broader class of inner functions, even when the outer function is simple. While strong composition bounds do not directly yield formula depth bounds, they are often instrumental in analyzing the standard composition (of the corresponding two functions), which directly relates to formula depth.

Our proof utilizes formal complexity measures. First, we apply Khrapchenko's method to show that numerous instances of $f$ remain unsolved after several communication steps. Subsequently, we transition to a different formal complexity measure to demonstrate that the remaining communication problem is at least as hard as ${\mathsf{KW}}_{\mathsf{OR}}◯\ast {\mathsf{KW}}_f$. This hybrid approach not only achieves the desired lower bound, but also introduces a novel technique for analyzing formula depth, potentially informing future research in complexity theory.

The results has been published in the proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025).