On ACC期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

On ACC

Authors:	Richard Beigel Jun Tarui

Affiliation:	(1) Dept. of Computer Science, University of Yale, P.O. Box 208285, 06520-8285 New Haven, CT, U.S.A.;(2) Department of Communications & Systems Engineering, University of Electro-Communications, Chofu, 182 Tokyo, Japan

Abstract:	We show that every languageL in the class ACC can be recognized by depth-two deterministic circuits with a symmetric-function gate at the root and $2^{log ^{O(1)} n}$ AND gates of fan-in log^O(1)n at the leaves, or equivalently, there exist polynomialsp_n(x₁,..., x_n) overZ of degree log^O(1)n and with coefficients of magnitude $2^{log ^{O(1)} n}$ and functionsh_n:Z{0,1} such that for eachn and eachx{0,1}ⁿ,XL^(x)=h_n(p_n(x₁,...,x_n)). This improves an earlier result of Yao (1985). We also analyze and improve modulus-amplifying polynomials constructed by Toda (1991) and Yao (1985).

Keywords:	68Q05 68Q15 68Q25
本文献已被 SpringerLink 等数据库收录！