On probabilistic ACC circuits with an exact-threshold output gate
説明
Let SYM+ denote the class of Boolean functions computable by depth-two size-\(n^{log^{O(1)} n}\) circuits with a symmetric-function gate at the root and AND gates of fan-in logO(1)n at the next level, or equivalently, the class of Boolean functions h such that h(x1,⋯ ,x n ) can be expressed as h(x1,⋯, xn) =h n(pn(x1,⋯, x n )) for some polynomial p n over Z of degree logO(1)n and norm (the sum of the absolute values of its coefficients) \(n^{log^{O(1)} n}\) and some function h n : Z → {0,1}. Building on work of Yao [Yao90], Beigel and Tarui [BT91] showed that ACC \(\subseteq\) SYM+, where ACC is the class of Boolean functions computable by constant-depth polynomial-size circuits with NOT, AND, OR, and MODm gates for some fixed m.