首页    期刊浏览 2024年11月25日 星期一
登录注册

文章基本信息

  • 标题:On Expressing Majority as a Majority of Majorities
  • 本地全文:下载
  • 作者:Christian Engels ; Mohit Garg ; Kazuhisa Makino
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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.

  • 关键词:Discrepancy ; majority
国家哲学社会科学文献中心版权所有