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

文章基本信息

  • 标题:Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
  • 本地全文:下载
  • 作者:Alexander Golovnev ; Alexander Kulikov
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2015
  • 卷号:2015
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    In this paper we motivate the study of Boolean dispersers for quadratic varieties by showing that an explicit construction of such objects gives improved circuit lower bounds. An ( n k s ) -quadratic disperser is a function on n variables that is not constant on any subset of F 2 n of size at least s that can be defined as the set of common roots of at most k quadratic polynomials. We show that if a Boolean function f is a n 1 83 n 2 g ( n ) -quadratic disperser for any function g ( n ) = o ( n ) then the circuit size of f is at least 3 11 n . In order to prove this, we generalize the gate elimination method so that the induction works on the size of the variety rather than on the number of variables as in previously known proofs.

  • 关键词:Boolean circuits ; Dispersers ; lower bounds
国家哲学社会科学文献中心版权所有