The Library
ON PROBABILISTIC ACC CIRCUITS WITH AN EXACTTHRESHOLD OUTPUT GATE
Tools
UNSPECIFIED (1992) ON PROBABILISTIC ACC CIRCUITS WITH AN EXACTTHRESHOLD OUTPUT GATE. LECTURE NOTES IN COMPUTER SCIENCE, 650 . pp. 420429.
Full text not available from this repository, contact author.Abstract
Let SYM+ denote the class of Boolean functions computable by depthtwo sizen(logO(1)n) circuits with a symmetricfunction gate at the root and AND gates of fanin log(o(1)n) at the next level, or equivalently, the class of Boolean functions f such that f(x1,...,x(n)) can be expressed as f(x1,...,x(n)) = h(n)(p(n)(x1,..., x(n))) for some polynomial p. 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 [Yao90], Beigel and Tarui [BT91] showed that ACC subsetorequalto SYM+, where ACC is the class of Boolean functions computable by constantdepth polynomialsize 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 exactthreshold gate as the output gate (an exactthreshold 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 docs not belong to the class ACC remains an open problem in circuit complexity, and the result that ACC subsetorequalto SYM+ has raised the hope that we may be able to solve this problem by exploiting the characterization of SYM+ iii terms of polynomials, which are perhaps easier to analyze than circuits, and showing that f isnotanelementof 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 iu mind and explored.
By a wellknown connection [FSS84], we also obtain new results about some classes related to the polynomialtime hierarchy.
Item Type:  Journal Article  

Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software  
Journal or Publication Title:  LECTURE NOTES IN COMPUTER SCIENCE  
Publisher:  SPRINGER VERLAG  
ISSN:  03029743  
Official Date:  1992  
Dates: 


Volume:  650  
Number of Pages:  10  
Page Range:  pp. 420429  
Publication Status:  Published 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 