Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits
Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits
复制标题
平衡集和深度 2 阈值电路的下限
DOI：
10.4230/lipics.icalp.2019.72
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
A. Yehudayoff
中科院分区：
文献类型：
--
作者：
P. Hrubes;Sivaramakrishnan Natarajan Ramamoorthy;Anup Rao;A. Yehudayoff
在组合学和计算机科学中有各种各样的平衡集族概念。例如，一类固有非空子集S_1，…，S_k子集[n]是平衡的，如果对于每个子集X子集{1,2，…，n}的大小为n/2，在[k]中有一个i，使得|S_i cap X| = |S_i|/2。我们扩展并简化了Hegedus开发的证明平衡集族大小下界的框架。证明了对于素数p，如果n=2p，则k >= p，对于任意n，证明了k >= n/2 - 0 (n)。
There are various notions of balancing set families that appear in combinatorics and computer science. For example, a family of proper non-empty subsets S_1,...,S_k subset [n] is balancing if for every subset X subset {1,2,...,n} of size n/2, there is an i in [k] so that |S_i cap X| = |S_i|/2. We extend and simplify the framework developed by Hegedus for proving lower bounds on the size of balancing set families. We prove that if n=2p for a prime p, then k >= p. For arbitrary values of n, we show that k >= n/2 - o(n).
We then exploit the connection between balancing families and depth-2 threshold circuits. This connection helps resolve a question raised by Kulikov and Podolskii on the fan-in of depth-2 majority circuits computing the majority function on n bits. We show that any depth-2 threshold circuit that computes the majority on n bits has at least one gate with fan-in at least n/2 - o(n). We also prove a sharp lower bound on the fan-in of depth-2 threshold circuits computing a specific weighted threshold function.