# The Library

### PROBABILISTIC POLYNOMIALS, AC(0) FUNCTIONS AND THE POLYNOMIAL-TIME HIERARCHY

Tools

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

**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

### Actions (login required)

View Item |