Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-174 | 13th November 2017 20:34

On Expressing Majority as a Majority of Majorities

RSS-Feed




TR17-174
Authors: Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao
Publication: 13th November 2017 20:34
Downloads: 247
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint