KRW Composition Theorems via Lifting
Authors:
- Susanna F. de RezendeSRSusanna F. de Rezende
- Or MeirOMOr Meir
- Jakob NordströmJNJakob Nordström
- Toniann PitassiTPToniann Pitassi
- Robert RobereRRRobert Robere
Preprint
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$.
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity2020
- Simulation Theorems via Pseudo-random Propertiescomputational complexity, 2019
- Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexitycomputational complexity, 2017
- Super-logarithmic depth lower bounds via direct sum in communication complexity2002
- Communication complexity towards lower bounds on circuit depthcomputational complexity, 2001
- Separation of the Monotone NC HierarchyCombinatorica, 1999
- Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offsJournal of Computer and System Sciences, 1992
- A simple lower bound for monotone clique using a communication gameInformation Processing Letters, 1992
- Applications of matrix methods to the theory of lower bounds in computational complexityCombinatorica, 1990
- An observation on time-storage trade offJournal of Computer and System Sciences, 1974