首页    期刊浏览 2025年06月11日 星期三
登录注册

文章基本信息

  • 标题:Separation of AC 0 [ ] Formulas and Circuits
  • 本地全文:下载
  • 作者:Benjamin Rossman ; Srikanth Srinivasan
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the AC 0 [ ] basis (unbounded fan-in AND, OR, NOT and MOD 2 gates). We show, for all d ( n ) O ( log n log log n ) , that there exist {\em polynomial-size depth- d circuits} that are not equivalent to {\em depth- d formulas of size n o ( d ) } (moreover, this is optimal in that n o ( d ) cannot be improved to n O ( d ) ). This result is obtained by a combination of new lower and upper bounds for {\em Approximate Majorities}, the class of Boolean functions 0 1 n 0 1 that agree with the Majority function on 3 4 fraction of inputs.

    AC 0 [ ] formula lower bound: We show that every depth- d AC 0 [ ] formula of size s has a {\em 1 8 -error polynomial approximation} over \F 2 of degree O ( 1 d log s ) d − 1 . This strengthens a classic O ( log s ) d − 1 degree approximation for \underline{circuits} due to Razborov. Since the Majority function has approximate degree ( n ) , this result implies an exp ( ( d n 1 2( d − 1) )) lower bound on the depth- d AC 0 [ ] formula size of all Approximate Majority functions for all d ( n ) O ( log n ) .

    Monotone AC 0 circuit upper bound: For all d ( n ) O ( log n log log n ) , we give a randomized construction of depth- d monotone AC 0 circuits (without NOT or MOD 2 gates) of size exp ( O ( n 1 2( d − 1) )) that compute an Approximate Majority function. This strengthens a construction of \underline{formulas} of size exp ( O ( d n 1 2( d − 1) )) due to Amano.

  • 关键词:approximate majority ; circuit complexity ; lower bounds ; polynomial method
国家哲学社会科学文献中心版权所有