All reports by Author Anup Rao:

__
TR19-026
| 28th February 2019
__

Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff#### Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits

Revisions: 1

Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff

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,\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| = ... more >>>