A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints
A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints
复制标题
通过团约束对公式大小下界进行更强的 LP 约束
DOI：
10.1016/j.tcs.2012.02.005
复制
发表时间：
2012
影响因子：
1.1
通讯作者：
Kenya Ueno
中科院分区：
文献类型：
--
作者：
Y. Aoshima;D. Avis;T. Deering;Y. Matsumoto and S. Moriyama;David Avis;Kenya Ueno
我们基于 Karchmer、Kushilevitz 和 Nisan 最初提出的线性规划界以及稳定集合多胞形理论，引入了一种证明公式大小下界的新技术。我们将其应用于多数函数，并证明其公式大小下界比 Khrapchenko 的经典结果有所改进。此外，我们引入了由单调自对偶函数分解理论激发的不平衡递归三元多数函数的概念，并给出了其公式大小的匹配上限和下界。我们还展示了平衡递归三元多数函数的单调公式大小下界，该函数是从 Laplante、Lee 和 Szegedy 的量子对手界限改进而来的。
We introduce a new technique proving formula size lower bounds based on the linear programming bound originally introduced by Karchmer, Kushilevitz and Nisan and the theory of stable set polytopes. We apply it to majority functions and prove their formula size lower bounds improved from the classical result of Khrapchenko. Moreover, we introduce a notion of unbalanced recursive ternary majority functions motivated by a decomposition theory of monotone self-dual functions and give matching upper and lower bounds of their formula size. We also show monotone formula size lower bounds of balanced recursive ternary majority functions improved from the quantum adversary bound of Laplante, Lee and Szegedy.