ECCC-Report TR17-174https://eccc.weizmann.ac.il/report/2017/174Comments and Revisions published for TR17-174en-usMon, 13 Nov 2017 20:34:51 +0200
Paper TR17-174
| On Expressing Majority as a Majority of Majorities |
Christian Engels,
Mohit Garg,
Kazuhisa Makino,
Anup Rao
https://eccc.weizmann.ac.il/report/2017/174If $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. Mon, 13 Nov 2017 20:34:51 +0200https://eccc.weizmann.ac.il/report/2017/174