Title: On Probabilistic ACC Circuits with an Exact-Threshold Output Gate

Authors: Richard Beigel, Jun Tarui, and Seinosuke Toda

Abstract: Let SYM+ denote the class of Boolean functions computable by depth-two size-nlogO(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 f such that f(x1, ... , xn) can be expressed as f(x1, ... , xn) = hn(pn(x1, ... , xn)) for some polynomial pn over Z of degree logO(1)n and norm (the sum of the absolute values of its coefficients) nlogO(1)n and some function hn : Z -> {0,1}. Building on work of Yao (FOCS '90), Beigel and Tarui (FOCS '91) showed that ACC ⊆ 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.

In this paper, we consider augmenting the power of ACC circuits by allowing randomness and allowing an exact-threshold gate as the output gate (an exact-threshold gate outputs 1 if exactly k of its inputs are 1, where k is a parameter; it outputs 0 otherwise), and show that every Boolean function computed by this kind of augmented ACC circuits is still in SYM+.

Showing that some ``natural'' function f does not belong to the class ACC remains an open problem in circuit complexity, and the result that ACC ⊆ SYM+ has raised the hope that we may be able to solve this problem by exploiting the characterization of SYM+ in terms of polynomials, which are perhaps easier to analyze than circuits, and showing that f is not in SYM+. Our new result and proof techniques suggest that the possibility that SYM+ contains even more Boolean functions than we currently know should also be kept in mind and explored.

By a well-known connection (Furst & Saxe & Sipser, MST '84), we also obtain new results about some classes related to the polynomial-time hierarchy.

Download Full Paper