Balancing Sets and Majority Lower bounds

Resources

• [https://eccc.weizmann.ac.il/report/2019/026/](Hrubes, Natarajan Ramamoorthy, Rao, Yehudayoff - Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits)

Main Definitions

• We define $\left\langle \stackrel{m}{k}\right\rangle$ to be the set ${ x\in {0,1}^m \mid \text{$x$ has $k$ ones}}$.
• Balanced Set: Sets $S_1,\dots, S_k$ are a balancing set family if for every $X\in [n]$ of size $n/2$ there is an $i$ such that $\lvert S_i\cap X\rvert = \lvert S_i\rvert/2$.
• $B(n)$ is the minimal $k$ such that a balancing set family exists.

Main Lemma

• Let $p$ be a prime and let $f(x_1,\dots,x_{2p})$ be a polynomial over $F_p$ with $\forall x\in \left\langle \stackrel{2p}p \right\rangle$, $f(x)=0$ and $f(0)\neq 0$.

Theorem

• If $n=2p$ for a prime $p$ then $B(n)=p$. [Theorem 2]
• For all integer $n$ $B(n) = n/2 - o(1)$. [Theorem 3]
• For a prime $p=n/2$. Any depth 2 circuit computing the majority of $n$ bits with the bottom gates computing threshold functions the following holds. Either the top fan-in is at least $p$ or some gate at the bottom computes a threshold with $t=p$. [Theorem 7]
• Corollary from the third is that the fan-in is $p$, as a threshold $p$ function needs fan-in at least $p$ to be non-trivial.