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

文章基本信息

  • 标题:A better-than- 3 n lower bound for the circuit complexity of an explicit function
  • 本地全文:下载
  • 作者:Magnus Gausdal Find ; Alexander Golovnev ; Edward Hirsch
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2015
  • 卷号:2015
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We consider Boolean circuits over the full binary basis. We prove a (3 + 1 86 ) n − o ( n ) lower bound on the size of such a circuit for an explicitly defined predicate, namely an affine disperser for sublinear dimension. This improves the 3 n − o ( n ) bound of Norbert Blum (1984). The proof is based on the gate elimination technique extended with the following three ideas. We generalize the computational model by allowing circuits to contain cycles, this in turn allows us to perform affine substitutions. We use a carefully chosen circuit complexity measure to track the progress of the gate elimination process. Finally, we use quadratic substitutions that may be viewed as delayed affine substitutions.

国家哲学社会科学文献中心版权所有