## Proceedings, Eleventh Annual IEEE Conference on Computational Complexity: May 24-27, 1996, Philadelphia, PennsylvaniaTwenty-six presentations made in 15 sessions at the May 1996 conference providing original research and theories in a variety of areas in computational complexity. The papers cover topics in circuit complexity, collapsing oracle-tape hierarchies, randomness extraction, error reduction by parallel re" |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Nondeterministic NC Computation | 12 |

Session 2 | 23 |

Collapsing OracleTape Hierarchies | 33 |

Copyright | |

25 other sections not shown

### Common terms and phrases

accepts algorithm approximating automorphism binary Boolean boolean circuit collapses complexity classes complexity theory Computer Science conPMV constant construction Corollary define definition denote deterministic Dlogtime-uniform edge encoding exists extractors fan-in finite func function f gate graph graph products hence hierarchy IEEE implies independent set input bits integer program isomorphism L-printable Lemma logspace lower bound many-one reductions min-entropy multivalued functions node nonadaptive nondeterministic NP-complete NPMV NPSV O(log oracle tape oracle Turing machine output bit p-measure partial multivalued functions pebble polynomial polynomial hierarchy polynomial-time computable PP-comp probabilistic problem Proc proof system properties Proposition prove PSPACE queries random bits recursive Selman sequence simulation solution space space-bounded strings of length subgraph subset Symposium test tube Theorem tion truth-table reducible Turing machine Turing reductions variables VC dimension vertex vertices