ComputingComputer EngineeringComputer ScienceAlgorithmsCircuit TheoryTheory Of ComputationCircuit ComplexityComplexity TheoryComputational ComplexityBoolean Circuit ComplexityCircuit Complexity Of Boolean FunctionsCircuit Depth ComplexityCircuit Lower BoundsCircuit Size ComplexityCircuit Upper BoundsDeterministic Circuit ComplexityProbabilistic Circuits
It has been shown by A. Yao (1990) that every language in ACC is recognized by a sequence of depth-2 probabilistic circuits with a symmetric gate at the root and n/sup polylog/(n) AND gates of fan-in polylog (n) at the leaves. The authors simplify Yao's proof and strengthen his results: every language in ACC is recognized by a sequence of depth-2 deterministic circuits with a symmetric gate at the root and n/sup polylog/(n) AND gates of fan-in polylog(n) at the leaves. They also analyze and improve modulus-amplifying polynomials constructed by S. Toda (1989) and Yao: this yields smaller circuits in Yao's and the present results on ACC.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
17
Introduction to Commutative Algebra.
D. J. Lewis, B. R. McDonald, M. F. Atiyah et al. · American Mathematical Monthly · 1970 · 1.8K citations