On the Size of Depth-Two Threshold Circuits for the Inner Product Mod 2 Function
On the Size of Depth-Two Threshold Circuits for the Inner Product Mod 2 Function
复制标题
DOI：
10.1007/978-3-030-40608-0_16
复制
发表时间：
2020-01-07
期刊：
影响因子：
--
通讯作者：
Amano K
中科院分区：
文献类型：
--
作者：
Amano K
在本文中，我们研究了计算内积模 2 函数 (mod 2) 的深度二阈值电路的大小。首先，我们揭示 可以通过尺寸明显小于尺寸 的民间传说结构的深度二阈值电路来计算。也就是说，我们给出了这样一个大小为 的电路（用电路表示）的结构。对于顶部阈值门的权重是多项式有界的情况（由电路表示），我们还给出了 的上限。其次，我们对某些特殊形式的深度二电路的大小给出了新的下界；顶门是无界权重阈值门，底门是对称门（用电路表示）。我们证明任何这样的电路计算都有每个常数的大小。这改进了 Forster 等人基于符号排序方法的先前界限。 [JCSS '02、FSTTCS '01]。我们的技术有一个独特的特点，即下界是通过对某个线性规划问题（的对偶）给出显式可行解来获得的。事实上，这个问题本身是作者在十多年前提出的[MFCS '05]，找到一个好的解决方案是这项工作的实际贡献。
In this paper, we study the size of depth-two threshold circuits computing the inner product mod 2 function (mod 2). First, we reveal that can be computed by a depth-two threshold circuit of size significantly smaller than a folklore construction of size . Namely, we give a construction of such a circuit (denoted by circuit) of size . We also give an upper bound of for the case that the weights of the top threshold gate are polynomially bounded (denoted by circuit). Second, we give new lower bounds on the size of depth-two circuits of some special form; the top gate is an unbounded weight threshold gate and the bottom gates are symmetric gates (denoted by circuit). We show that any such circuit computing has size for every constant . This improves the previous bound of based on the sign-rank method due to Forster et al. [JCSS ’02, FSTTCS ’01]. Our technique has a unique feature that the lower bound is obtained by giving an explicit feasible solution to (the dual of) a certain linear programming problem. In fact, the problem itself was presented by the author over a decade ago [MFCS ’05], and finding a good solution is an actual contribution of this work.