The Library
PROBABILISTIC POLYNOMIALS, AC(0) FUNCTIONS AND THE POLYNOMIALTIME HIERARCHY
Tools
UNSPECIFIED (1993) PROBABILISTIC POLYNOMIALS, AC(0) FUNCTIONS AND THE POLYNOMIALTIME HIERARCHY. In: 8TH ANNUAL SYMP ON THEORETICAL ASPECTS OF COMPUTER SCIENCE ( STACS 91 ), HAMBURG, GERMANY, FEB 1416, 1991. Published in: THEORETICAL COMPUTER SCIENCE, 113 (1). pp. 167183. ISSN 03043975.
Research output not available from this repository, contact author.Abstract
We show that, for every Boolean function f (x1, ..., x(n)) in the class AC0 and an arbitrary constant k greaterthanorequalto 0, there is a size0 (n(k + 1)) collection OMEGA of degreelog(O(1)) n polynomials over Z in x 1, ..., x(n) such that, for each x isanelementof {0, 1}n, when p isanelementof OMEGA is randomly chosen, f(x) = p(x) with probability at least 1  1/(3n(k)), and, furthermore, if f (x) = 0 (f(x) = 1), then p(x) = 1 (p(x) = 0) with probability 0. Applying this result, we prove the following: (a) Every Boolean function in the class AC0 can be computed with onesided error at most 1/(3n(k)) by some depthtwo probabilistic circuits with a threshold gate at the root, n(log(O(1)n) AND gates of fanin log(O(1))n at the next level, and (k + 1)log2 n + O(1) random bits; it can also be computed, for an arbitrary constant l greaterthanorequalto 0, by some depththree deterministic circuits with an OR gate at the root, at most n/(log2 n)1 Threshold gates at the second level, and n(log(O(1)n) AND gates of fanin log(O(1))n at the third level. (b) For C = PP, C = P, and MOD(m)P, every language L in the polynomialtime hierarchy is Ceasy under a randomized manyone polynomialtime reduction; in fact, for C = PP and C = P, L is Ceasy under such a reduction with onesided error.
Item Type:  Conference Item (UNSPECIFIED)  

Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software  
Journal or Publication Title:  THEORETICAL COMPUTER SCIENCE  
Publisher:  ELSEVIER SCIENCE BV  
ISSN:  03043975  
Official Date:  24 May 1993  
Dates: 


Volume:  113  
Number:  1  
Number of Pages:  17  
Page Range:  pp. 167183  
Publication Status:  Published  
Title of Event:  8TH ANNUAL SYMP ON THEORETICAL ASPECTS OF COMPUTER SCIENCE ( STACS 91 )  
Location of Event:  HAMBURG, GERMANY  
Date(s) of Event:  FEB 1416, 1991 
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 