KRW Composition Theorems via Lifting
KRW Composition Theorems via Lifting
复制标题
DOI：
10.1109/focs46700.2020.00013
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Susanna F. de Rezende;Or Meir;Jakob Nordström;T. Pitassi;Robert Robere
中科院分区：
文献类型：
--
作者：
Susanna F. de Rezende;Or Meir;Jakob Nordström;T. Pitassi;Robert Robere
复杂性理论中主要的开放问题之一是证明电路深度的超对数下界（即 $\mathrm{P}\nsubseteq \text{NC}^{1}$）。 Karchmer、Raz 和 Wigderson [13] 建议通过证明深度复杂度对于函数 $f\diamond g$ 的组合表现“符合预期”来解决这个问题。他们证明这个猜想的有效性意味着$\mathrm{P}\nsubseteq \text{NC}^{1}$。有几项工作通过证明特殊情况在解决这一猜想方面取得了进展。特别是，这些工作证明了每个外部函数的 KRW 猜想，但仅针对少数内部函数。因此，证明 KRW 猜想适用于更广泛的内函数是一个重要的挑战。在这项工作中，我们显着扩展了可以处理的内部函数的范围。首先，我们考虑 KRW 猜想的单调版本。我们为每个单调内部函数证明了这一点，其深度复杂性可以通过查询到通信提升定理进行下限。这使我们能够处理几个经过充分研究的新函数，例如 $s-t$-连接、派系和生成函数。为了将这一进展带回非单调环境，我们引入了半单调复合的新概念，它将外部函数的非单调复杂性与内部函数的单调复杂性结合起来。在此设置中，我们证明了针对类似的内部函数选择的 KRW 猜想，但仅针对外部函数 $f$ 的特定选择。
One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathrm{P}\nsubseteq \text{NC}^{1}$). Karchmer, Raz, and Wigderson [13] 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 $\mathrm{P}\nsubseteq \text{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, but only for few inner functions. 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 monotone version of the KRW conjecture. We prove it for every monotone inner function 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-t$-connectivity, clique, and generation functions. In order to carry this progress back to the non-monotone setting, we introduce a new notion of semi-monotone composition, which combines the non-monotone complexity of the outer function with the monotone complexity of the inner function. In this setting, we prove the KRW conjecture for a similar selection of inner functions, but only for a specific choice of the outer function $f$.