2026-08-06T10:24:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10648 2024-03-06T10:46:22Z ddc:004 open_access

Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits Hrubeš, Pavel Natarajan Ramamoorthy, Sivaramakrishnan Rao, Anup Yehudayoff, Amir Balancing sets depth-2 threshold circuits polynomials majority weighted thresholds 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pavel Hrubeš and Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao and Amir Yehudayoff 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.72 urn:nbn:de:0030-drops-106487 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.72 eng https://creativecommons.org/licenses/by/3.0/legalcode