Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > WEIGHTED MAJORITY:
Reports tagged with weighted majority:
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

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 >>>

ISSN 1433-8092 | Imprint