26th Annual Symposium on Foundations of Computer Science: October 21-23, 1985 |
Contents
Deterministic Simulation of Probabilistic Constant Depth Circuits | 11 |
Amplification of Probabilistic Boolean Formulas | 20 |
On Networks of Noisy Gates | 30 |
35 other sections not shown
Common terms and phrases
algorithm Algorithm FGK apply approximation algorithm assignment assume b₁ binary bits Boolean Boolean function chain circuit coin flipping complexity Computer Science constant construction cycle defined denote deterministic DIEGO edges elements embedding encoding endpoint factor finite formula function given IEEE independent induction input integer intersection iteration label layer least Lemma length linear logn lower bound matching matrix matroid merging minimum node O(log O(n² obtain optimal output pair parallel parallel algorithms partition path permutation permutation graph planar graph polynomial probabilistic probability problem Proc processors proof protocol prove pushdown random variable recursive recursive set requires result rithm root scheme segment sequence simulate solution solved sorting step string subgraph subset Theorem Theory tion tree undirected graph upper bound v₁ vector vertex vertices VLSI weight wires