Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
复制标题
Lov[a-acute]sz 的下限 - Schrijver Systems 及其他系统遵循多方通信复杂性
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Nathan Segerlind
中科院分区：
文献类型：
--
作者：
P. Beame;T. Pitassi;Nathan Segerlind
我们证明了集不相交函数的3方额上数（NOF）通信复杂度的$omega(log^ 4n)$下界暗示了一个$n^{omega(1)}$大小的树状Lovasz-Schrijver系统的下界，该系统驳斥了合取范式（CNFs）中的不可满足公式。更一般地，我们证明了集合不相交的$(k+1)$-party NOF通信复杂度的$n^{Omega(1)}$下界意味着对于所有公式为$k$多项式不等式的树状证明系统的$2^{n^{Omega(1)}}$大小的下界。
We prove that an $omega(log^4 n)$ lower bound for the three-party number-on-the-forehead (NOF) communication complexity of the set-disjointness function implies an $n^{omega(1)}$ size lower bound for treelike Lovasz-Schrijver systems that refute unsatisfiable formulas in conjunctive normal form (CNFs). More generally, we prove that an $n^{Omega(1)}$ lower bound for the $(k+1)$-party NOF communication complexity of set disjointness implies a $2^{n^{Omega(1)}}$ size lower bound for all treelike proof systems whose formulas are degree $k$ polynomial inequalities.