Authors: Richard Beigel, Jun Tarui, and Seinosuke Toda

Abstract: Let SYM⁺ denote the class of Boolean functions computable by depth-two size-n^logO(1)n circuits with a symmetric-function gate at the root and AND gates of fan-in log^O(1)n at the next level, or equivalently, the class of Boolean functions f such that f(x₁, ... , x_n) can be expressed as f(x₁, ... , x_n) = h_n(p_n(x₁, ... , x_n)) for some polynomial p_n over Z of degree log^O(1)n and norm (the sum of the absolute values of its coefficients) n^logO(1)n and some function h_n : 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 MOD_m 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