If k n , can one express the majority of n bits as the majority of at most k majorities, each of at most k bits? We prove that such an expression is possible only if k = ( n 4 5 ) . This improves on a bound proved by Kulikov and Podolskii, who showed that k = ( n 0 7+ o (1) ) . Our proof is based on ideas originating in discrepancy theory, as well as a strong concentration bound for sums of independent Bernoulli random variables and a strong anticoncentration bound for the hypergeometric distribution.
展开▼
