文章基本信息

标题：Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits
本地全文：下载
作者：Pavel Hrubes ; Sivaramakrishnan Natarajan Ramamoorthy ; Anup Rao 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：132
页码：1-14
DOI：10.4230/LIPIcs.ICALP.2019.72
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 Hegedüs 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.
关键词：Balancing sets; depth-2 threshold circuits; polynomials; majority; weighted thresholds