UNSPECIFIED (1993) PROBABILISTIC POLYNOMIALS, AC(0) FUNCTIONS AND THE POLYNOMIAL-TIME HIERARCHY. In: 8TH ANNUAL SYMP ON THEORETICAL ASPECTS OF COMPUTER SCIENCE ( STACS 91 ), FEB 14-16, 1991, HAMBURG, GERMANY.

Full text not available from this repository.

Abstract

We show that, for every Boolean function f (x1, ..., x(n)) in the class AC0 and an arbitrary constant k greater-than-or-equal-to 0, there is a size-0 (n(k + 1)) collection OMEGA of degree-log(O(1)) n polynomials over Z in x 1, ..., x(n) such that, for each x is-an-element-of {0, 1}n, when p is-an-element-of 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. Ap-plying this result, we prove the following: (a) Every Boolean function in the class AC0 can be computed with one-sided error at most 1/(3n(k)) by some depth-two probabilistic circuits with a threshold gate at the root, n(log(O(1)n) AND gates of fan-in 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 greater-than-or-equal-to 0, by some depth-three 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 fan-in log(O(1))n at the third level. (b) For C = PP, C = P, and MOD(m)P, every language L in the polynomial-time hierarchy is C-easy under a randomized many-one polynomial-time reduction; in fact, for C = PP and C = P, L is C-easy under such a reduction with one-sided 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:	0304-3975
Date:	24 May 1993
Volume:	113
Number:	1
Number of Pages:	17
Page Range:	pp. 167-183
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 14-16, 1991
URI:	http://wrap.warwick.ac.uk/id/eprint/21346

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item