All reports by Author Mohit Garg:

__
TR17-174
| 13th November 2017
__

Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao#### On Expressing Majority as a Majority of Majorities

Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao

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