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 [ n ] is balancing if for every subset X 1 2 n of size n 2 , there is an i [ k ] so that S i X = S i 2 . We extend and simplify the framework developed by Hegedüs for proving lower bounds on the size of balancing set families. We prove that if n = 2 p 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.
展开▼
机译：组合集和计算机科学中出现了平衡集族的各种概念。例如，如果对于大小为n 2的每个子集X 1 2 n都存在一个i [k]，那么一族适当的非空子集S 1 S k [n]是平衡的，因此S i X = S i 2。我们扩展和简化了Hegedüs开发的框架，以证明平衡套件系列的大小的下限。我们证明如果素数p的n = 2 p，则k p。对于n的任意值，我们表明k n 2？ o（n）。然后，我们利用平衡族和深度2阈值电路之间的连接。这种连接有助于解决Kulikov和Podolskii提出的关于深度2多数电路扇入计算n位多数功能的问题。我们表明，任何在n位上计算多数的深度2阈值电路都具有至少一个扇入至少为n 2？上 ） 。我们还证明了深度2阈值电路的扇入的急剧下界，该阈值电路计算特定的加权阈值函数。
展开▼
