11. CoCo 1996: Philadelphia, Pennsylvania, USA

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, May 24-27, 1996, Philadelphia, Pennsylvania, USA. IEEE Computer Society Press, 1996, ISBN 0-8186-7386-9

Session 1

Manindra Agrawal, Eric Allender:
An Isomorphism Theorem for Circuit Complexity. 2-11
Electronic Edition (IEEE Computer Society DL) BibTeX
Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer:
Nondeterministic NC¹ Computation. 12-21
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 2

Kazuo Iwama, Chuzo Iwamoto:
Parallel Complexity Hierarchies Based on PRAMs and DLOGTIME-Uniform Circuits. 24-32
Electronic Edition (IEEE Computer Society DL) BibTeX
Georg Gottlob:
Collapsing Oracle-Tape Hierarchies. 33-42
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 3

Noam Nisan:
Extracting Randomness: How and Why A survey. 44-58
Electronic Edition (IEEE Computer Society DL) BibTeX
Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik:
On Coherence, Random-self-reducibility, and Self-correction. 59-67
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 4

Uriel Feige, Oleg Verbitsky:
Error Reduction by Parallel Repetition - a Negative Result. 70-76
Electronic Edition (IEEE Computer Society DL) BibTeX
Marcus Schäfer:
Deciding the Vapnik-Cervonenkis dimension is Sigma^P₃-complete. 77-80
Electronic Edition (IEEE Computer Society DL) BibTeX
Pascal Koiran:
VC Dimension in Circuit Complexity. 81-85
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 5

Dieter van Melkebeek:
Reducing P to a Sparse Set using a Constant Number of Queries Collapses P to L. 88-96
Electronic Edition (IEEE Computer Society DL) BibTeX
Lance Fortnow, Judy Goldsmith, Stephen R. Mahaney:
L-Printable Sets. 97-106
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 6

V. Vinay:
Hierarchies of Circuit Classes that are Closed under Complement. 108-117
Electronic Edition (IEEE Computer Society DL) BibTeX
Helmut Veith:
Succinct Representation, Leaf Languages, and Projection Reductions. 118-126
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 7

Michael E. Saks:
Randomization and Derandomization in Space_Bounded Computation. 128-149
Electronic Edition (IEEE Computer Society DL) BibTeX
Ker-I Ko, Klaus Weihrauch:
On the Measure of Two-Dimensional Regions with Polynomial-Time computables Boundaries. 150-159
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 9

Clemens Lautemann, Thomas Schwentick, Iain A. Stewart:
On Positive P. 162-170
Electronic Edition (IEEE Computer Society DL) BibTeX
Klaus Ambos-Spies, Elvira Mayordomo, Xizhong Zheng:
A Comparison of Weak Completeness Notions. 171-178
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 10

Yongge Wang:
The Law of the Iterated Logarithm for p-Random Sequences. 180-189
Electronic Edition (IEEE Computer Society DL) BibTeX
Rainer Schuler:
Truth-table Closure and Turing Closure of Average Polynomial Time have Different Measures in EXP. 190-195
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 11

Alan L. Selman:
Much Ado about Functions. 198-212
Electronic Edition (IEEE Computer Society DL) BibTeX
Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers:
Inverting Onto Functions. 213-222
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 12

Ashish V. Naik, Alan L. Selman:
A Note on P-selective sets and on Adaptive versus Nonadaptive Queries to NP. 224-232
Electronic Edition (IEEE Computer Society DL) BibTeX
Samuel R. Buss, Toniann Pitassi:
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. 233-242
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 13

Christos H. Papadimitriou:
The Complexity of Knowledge Representation. 244-248
Electronic Edition (IEEE Computer Society DL) BibTeX
Ian Barland, Phokion G. Kolaitis, Madhukar N. Thakur:
Integer Programming as a Framework for Optimization and Approximability. 249-259
Electronic Edition (IEEE Computer Society DL) BibTeX
Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer:
Complements of Multivalued Functions. 260-269
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 14

Manindra Agrawal, Vikraman Arvind:
A Note on Decision versus Search for Graph Automorphism. 272-277
Electronic Edition (IEEE Computer Society DL) BibTeX
Uriel Feige, Joe Kilian:
Zero Knowledge and the Chromatic Number. 278-287
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 15

Eric Bach, Anne Condon, Elton Glaser, Celena Tanguay:
DNA Models and Algorithms for NP-complete Problems. 290-300
Electronic Edition (IEEE Computer Society DL) BibTeX
Ming Li, Paul M. B. Vitányi:
Reversible Simulation of Irreversible Computation. 301-306
Electronic Edition (IEEE Computer Society DL) BibTeX