TR17-174 Authors: Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao

Publication: 13th November 2017 20:34

Downloads: 1240

Keywords:

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 = \Omega(n^{4/5})$. This improves on a bound proved by Kulikov and Podolskii, who showed that $k= \Omega(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.