A New Rank Technique for Formula Size Lower Bounds
A New Rank Technique for Formula Size Lower Bounds
复制标题
公式大小下限的新排序技术
DOI：
10.1007/978-3-540-70918-3_13
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Troy Lee
中科院分区：
文献类型：
--
作者：
Troy Lee
我们介绍了一种新的技术证明公式大小下界的基础上矩阵秩。这种技术的一个简单形式给出的界限至少与Khrapchenko方法给出的界限一样大，Khrapchenko方法最初用于证明奇偶函数的ann 2下界。将我们的方法应用于奇偶校验函数，我们能够给出奇偶校验公式大小的精确表达式：如果n = 2 <$+k，其中0 ≤k< 2 <$，则奇偶校验的公式大小为2 <$（2 <$+3 k）=n2+k2 <$−k2。这样的一个界限不能被Khrapchenko，Nečiporuk，Koutsoupias的任何下界技术或量子对抗方法证明，这些方法受到n2的限制。
We introduce a new technique for proving formula size lower bounds based on matrix rank. A simple form of this technique gives bounds at least as large as those given by the method of Khrapchenko, originally used to prove ann2lower bound on the parity function. Applying our method to the parity function, we are able to give an exact expression for the formula size of parity: ifn= 2ℓ+k, where 0 ≤k< 2ℓ, then the formula size of parity onnbits is exactly 2ℓ(2ℓ+ 3k) =n2+k2ℓ−k2. Such a bound cannot be proven by any of the lower bound techniques of Khrapchenko, Nečiporuk, Koutsoupias, or the quantum adversary method, which are limited byn2.