论文标题
通过举起的KRW组成定理
KRW Composition Theorems via Lifting
论文作者
论文摘要
复杂性理论中的主要开放问题之一是证明了电路深度的超级含量下限（即，$ \ mathbf {p} \ not \ subseteq \ subseteq \ mathbf {nc}^1 $）。 Karchmer，Raz和Wigderson（计算复杂性5（3/4），1995年）建议通过证明深度复杂性在功能组成$ f \ diamond g $方面的“预期”来解决此问题。他们表明，这种猜想的有效性意味着$ \ mathbf {p} \ not \ subseteq \ subseteq \ mathbf {nc}^1 $。 通过证明特殊情况，几项工作取得了进步，以解决这一猜想。特别是，这些作品证明了每个外部功能$ f $的KRW猜想，但仅适用于少数内部功能$ g $。因此，证明对更广泛的内部功能的KRW猜想是一个重要的挑战。 在这项工作中，我们可以显着扩展可以处理的内部功能的范围。首先，我们考虑KRW猜想的$ \ textit {monotone} $版本。我们证明了每个单调内部函数$ g $可以通过查询到通信的抬高定理的深度复杂性的$ g $。这使我们能够处理几个新的良好的功能，例如$ s \ textbf { - } t $ - 连接性，集团和生成功能。 为了将这一进度带回$ \ textit {non-monotone} $设置，我们引入了$ \ textit {semi-monotone} $组成的新概念，该概念将外部功能$ f $的非单调复杂性与内部功能的单调复杂性结合在一起。在这种情况下，我们证明了KRW的猜想，用于类似的内部功能$ g $，但仅用于特定选择外部功能$ f $。
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$.
