Improved Formula Size Lower Bounds for Monotone Self-Dual Boolean Functions

摘要

本研究は、Karchmer，Kushilevitz and Nisan［11］によって導入された線形計画限界と安定集合多面体の理論に基づき、論理式サイズの下限を証明する新しい技法を導入する。この新しい技法を多数決関数に適用することで、Khrapchenko［13］による古典的結果から論理式サイズの下限を改良する。さらに、単調自己双対論理関数の分解理論からの動機付けにより非平衡再帰3分多数決関数の概念を導入し、それらの論理式サイズの整数的に最適な上限と下限を示す。また、平衡再帰3分多数決関数の単調論理式サイズに対してLaplante，Lee and Szegedy［15】の量子敵対者限界により得られた値より改良された下限を示す。%We introduce a new technique proving formula size lower bounds based on the linear programming bound originally introduced by Karchmer, Kushilevitz and Nisan[ll] and the theory of stable set polytope. We apply it to majority functions and prove their formula size lower bounds improved from the classical result by Khrapchenko [13]. Moreover, we introduce a notion of unbalanced recursive ternary majority functions motivated by a decomposition theory of monotone self-dual functions and give integrally 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 [15].