5. CoCo 1990: Barcelona, Spain

Proceedings: Fifth Annual Structure in Complexity Theory Conference, July 8-11, 1990, Universitat Politècnica de Catalunya, Barcelona, Spain. IEEE Computer Society Press, 1990, ISBN 0-8186-2072-2

Session 1

Mitsunori Ogiwara, Osamu Watanabe: On Polynominal Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets (Abstract). 2 BibTeX
Steven Homer: Structural Properties of Nondeterministic Complete Sets. 3-10 BibTeX
Lane A. Hemachandra, Albrecht Hoene: On Sets with Efficient Implicit Membership Tests. 11-19 BibTeX
Pekka Orponen: On the Instance Complexity of NP-Hard Problems. 20-27 BibTeX

Session 2

László Babai: E-mail and the Unexpected Power of Interaction. 30-44 BibTeX
Jin-yi Cai, Anne Condon, Richard J. Lipton: On Bounded Round Multi-Prover Interactive Proof Systems. 45-54 BibTeX
Reuven Bar-Yehuda, Benny Chor, Eyal Kushilevitz: Privacy, Additional Information, and Communication. 55-65 BibTeX
Péter Hajnal: On the Power of Randomness in the Decision Tree Model. 66-77 BibTeX
Rafi Heiman, Ilan Newman, Avi Wigderson: On Read-Once Threshold Formulae and Their Randomized Decision Tree Complexity. 78-87 BibTeX

Session 3

Yishay Mansour, Noam Nisan, Prasoon Tiwari: The Computational Complexity of Universal Hashing. 90 BibTeX
Ilan Newman, Prabhakar Ragde, Avi Wigderson: Perfect Hashing, Graph Entropy, and Circuit Complexity. 91-99 BibTeX
Joan Feigenbaum, Sampath Kannan, Noam Nisan: Lower Bounds on Random-Self-Reducibility. 100-109 BibTeX
Martin Mundhenk, Rainer Schuler: Non-Uniform Complexity Classes and Random Languages. 110-119 BibTeX

Session 4

Eric Allender, Christopher B. Wilson: Width-Bounded Reducibility and Binary Search over Complexity Classes. 122-129 BibTeX
Klaus-Jörn Lange: Unambiguity of Circuits. 130-137 BibTeX

Session 5

Thomas Gundermann, Nasser Ali Nasser, Gerd Wechsung: A Survey on Counting Classes. 140-153 BibTeX
Carme Àlvarez, Birgit Jenner: A Very Hard Log Space Counting Class. 154-168 BibTeX
Richard Chang, Jim Kadin: The Boolean Hierarchy and the Polynomial Hierarchy: a Closer Connection. 169-178 BibTeX
Noam Nisan: On Read-Once vs. Multiple Access to Randomness in Logspace. 179-184 BibTeX

Session 6

Peter Clote: Bounded Arithmetic and Computational Complexity. 186-199 BibTeX
François Bédard, François Lemieux, Pierre McKenzie: Extensions to Barrington's M-Program Model. 200-209 BibTeX
James F. Lynch: The Quantifier Structure of Sentences that Characterize Nondeterministic Time Complexity. 210-222 BibTeX
V. Vinay, H. Venkateswaran, C. E. Veni Madhavan: Circuits, Pebbling and Expressibility. 223-230 BibTeX

Session 7

Amihood Amir, Richard Beigel, William I. Gasarch: Some Connections Between Bounded Query Classes and Non-Uniform Complexity. 232-243 BibTeX
Alessandro Panconesi, Desh Ranjan: Quantifiers and Approximation (Abstract). 244 BibTeX
Gerhard Lischke: Impossibilities and Possibilities of Weak Separation Between NP and Exponential Time. 245-253 BibTeX
Jie Wang: P-Productivity and Polynominal Time Approximations. 254-265 BibTeX

Session 8

Jack H. Lutz, William J. Schmidt: Circuit Size Relative to Pseudorandom Oracles. 268-286 BibTeX
Lane A. Hemachandra, Roy S. Rubinstein: A Note on Relativizing Complexity Classes with Tally Oracles. 287-294 BibTeX
Frederic Green: An Oracle Separating +P From PP^ph. 295-298 BibTeX
Ronald V. Book: On Separating Complexity Classes. 299-304 BibTeX
Johannes Köbler, Thomas Thierauf: Complexity Classes with Advice. 305-315 BibTeX

Errata

Lance Fortnow, John Rompel, Michael Sipser: Errata for On the Power of Multi-Prover Interactive Protocols. 318-319 BibTeX