Proceedings, Eleventh Annual IEEE Conference on Computational Complexity: May 24-27, 1996, Philadelphia, Pennsylvania
Jin-yi Cai, Steven Homer
IEEE Computer Society Press, 1996 - Computers - 307 pages
Twenty-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.
Nondeterministic NC Computation
Collapsing OracleTape Hierarchies
25 other sections not shown
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