ECCC-Report TR19-026https://eccc.weizmann.ac.il/report/2019/026Comments and Revisions published for TR19-026en-usSun, 05 May 2019 00:36:44 +0300
Revision 1
| Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits |
Pavel Hrubes,
Sivaramakrishnan Natarajan Ramamoorthy,
Anup Rao,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2019/026#revision1There 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,\ldots,S_k \subset [n]$ is balancing if for every subset $X \subset \{1,2,\ldots,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 \geq p$. For arbitrary values of $n$, we show that $k \geq 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.Sun, 05 May 2019 00:36:44 +0300https://eccc.weizmann.ac.il/report/2019/026#revision1
Paper TR19-026
| Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits |
Pavel Hrubes,
Sivaramakrishnan Natarajan Ramamoorthy,
Anup Rao,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2019/026There 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,\ldots,S_k \subset [n]$ is balancing if for every subset $X \subset \{1,2,\ldots,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 \geq p$. For arbitrary values of $n$, we show that $k \geq 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.Fri, 01 Mar 2019 09:12:49 +0200https://eccc.weizmann.ac.il/report/2019/026