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
Steven Homer: Structural Properties of Nondeterministic Complete Sets. 3-10
Lane A. Hemachandra, Albrecht Hoene: On Sets with Efficient Implicit Membership Tests. 11-19
Pekka Orponen: On the Instance Complexity of NP-Hard Problems. 20-27

Session 2

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

Session 3

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

Session 4

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

Session 5

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

Session 6

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

Session 7

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

Session 8

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

Errata

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

Last update Tue Feb 14 03:51:38 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page