KRW Composition Theorems via Lifting

by Susanna de Rezende, Or Meir, Jakob Nordstrom, Toniann Pitassi, and Robert Robere

Oded's comments

settings in which the KRW Composition Conjecture is known to hold. One such natural setting in which this aim is largely achieved is the case of monotone complexity. Here composition holds for any outer function f and any inner function g of a certain general form (obtained by `lifting'; i.e., certain general reduction from the context of query complexity). The treatment of the semi-monotone case may seem less satisfactory by itself, but one may view it as an important step beyond the case of monotone complexity (while recalling that breakthroughts are sought in the non-monotone setting).

The original abstract

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions $f \diamond g$. They showed that the validity of this conjecture would imply that $\mathbf{P}\not\subseteq\mathbf{NC}^1$.

Several works have made progress toward resolving this conjecture by proving special cases. In particular, these works proved the KRW conjecture for every outer function $f$, but only for few inner functions $g$. Thus, it is an important challenge to prove the KRW conjecture for a wider range of inner functions.

In this work, we extend significantly the range of inner functions that can be handled. First, we consider the $\textit{monotone}$ version of the KRW conjecture. We prove it for every monotone inner function $g$ whose depth complexity can be lower bounded via a query-to-communication lifting theorem. This allows us to handle several new and well-studied functions such as the $s\textbf{-}t$-connectivity, clique, and generation functions.

In order to carry this progress back to the $\textit{non-monotone}$ setting, we introduce a new notion of $\textit{semi-monotone}$ composition, which combines the non-monotone complexity of the outer function $f$ with the monotone complexity of the inner function $g$. In this setting, we prove the KRW conjecture for a similar selection of inner functions $g$, but only for a specific choice of the outer function $f$.

Available from ECCC TR20-099.

Back to list of Oded's choices.