6. CoCo 1991: Chicago, Illinois, USA

Session 1

• Seinosuke Toda, Mitsunori Ogiwara: Counting Classes Are at Least as Hard as the Polynomial-Time Hierarchy. 2-12 BibTeX
• Lance Fortnow, Nick Reingold: PP is Closed Under Truth-Table Reductions. 13-15 BibTeX
• Mitsunori Ogiwara, Lane A. Hemachandra: A Complexity Theory for Feasible Closure Properties. 16-29 BibTeX
• Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz: Gap-Definable Counting Classes. 30-42 BibTeX
• Sanjay Gupta: The Power of Witness Reduction. 43-59 BibTeX

Session 2

• William I. Gasarch: Bounded Queries in Recursion Theory: A Survey. 62-78 BibTeX
• Steven Homer, Luc Longpré: On Reductions of NP Sets to Sparse Sets. 79-88 BibTeX
• Ricard Gavaldà, Osamu Watanabe: On the Computational Complexity of Small Descriptions. 89-101 BibTeX
• Daniel P. Bovet, Pierluigi Crescenzi, Riccardo Silvestri: Complexity Classes and Sparse Oracles. 102-108 BibTeX

Session 3

• Jin-yi Cai, Anne Condon, Richard J. Lipton: PSPACE Is Provable By Two Provers In One Round. 110-115 BibTeX
• Uriel Feige: On the Success Probability of the Two Provers in One-Round Proof Systems. 116-123 BibTeX
• Joan Feigenbaum, Lance Fortnow: On the Random-Self-Reducibility of Complete Sets. 124-132 BibTeX
• Rafail Ostrovsky: One-Way Functions, Hard on Average Problems, and Statistical Zero-Knowledge Proofs. 133-138 BibTeX
• Mitsunori Ogiwara, Antoni Lozano: On One Query Self-Reducible Sets. 139-151 BibTeX

Session 4

• Ming Li, Paul M. B. Vitányi: Combinatorics and Kolmogorov Complexity. 154-163 BibTeX
• Peter Bro Miltersen: The Complexity of Malign Ensembles. 164-171 BibTeX
• Rafi Heiman, Avi Wigderson: Randomized vs.Deterministic Decision Tree Complexity for Read-Once Boolean Functions. 172-179 BibTeX
• Miklos Santha: On the Monte Carlo Boolean Decision Tree Complexity of Read-Once Formulae. 180-187 BibTeX

Session 5

• Jack H. Lutz: A Pseudorandom Oracle Characterization of BPP. 190-195 BibTeX
• Stephen A. Fenner: Notions of Resource-Bounded Category and Genericity. 196-212 BibTeX
• László Babai, Noam Nisan: BPP has Subexponential Time Simulation unless EXPTIME has Pubishable Proofs. 213-219 BibTeX
• Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe: Relating Equivalence and Reducibility to Sparse Sets. 220-229 BibTeX
• Shouwen Tang, Bin Fu, Tian Liu: Exponential Time and Subexponential Time Sets. 230-237 BibTeX

Session 6

• José L. Balcázar: Adaptive Logspace and Depth-Bounded Reducibilities. 240-254 BibTeX
• Richard Chang, Jim Kadin, Pankaj Rohatgi: Connections between the Complexity of Unique Satisfiability and the Threshold Behavior of Randomized Reductions. 255-269 BibTeX
• V. Vinay: Counting Auxiliary Pushdown Automata. 270-284 BibTeX
• Jun Tarui: Degree Compexity of Boolean Functions and Its Applications to Realivized Separations. 382-390 BibTeX
• Richard Beigel, Nick Reingold, Daniel A. Spielman: The Perceptron Strikes Back. 286-291 BibTeX

Session 7

• Michelangelo Grigni, Michael Sipser: Monotone Separation of Logspace from NC. 294-298 BibTeX
• Mauricio Karchmer, Ran Raz, Avi Wigderson: Super-logarithmic Depth Lower Bounds via Direct Sum in Communication Coplexity. 299-304 BibTeX
• David A. Mix Barrington, Howard Straubing: Superlinear Lower Bounds for Bounded-Width Branching Programs. 305-313 BibTeX
• Matthias Krause: Geometric Arguments Yield Better Bounds for Threshold Circuits and Distributed Computing. 314-321 BibTeX
• Jeff Edmonds: Lower Bounds with Smaller Domain Size On Concurrent Write Parallel Machines. 322-331 BibTeX

Session 8

• Neil Immerman: DSPACE[n^k] = VAR[k+1]. 334-340 BibTeX
• Erich Grädel: Capturing Complexity Classes by Fragments of Second Order Logic. 341-352 BibTeX
• Phokion G. Kolaitis, Madhukar N. Thakur: Approximation Properties of NP Minimization Classes. 353-366 BibTeX
• Stephen Bellantoni, Toniann Pitassi, Alasdair Urquhart: Approximation and Small Depth Frege Proofs. 367-390 BibTeX

Errata

• Jack H. Lutz, William J. Schmidt: Errata for Circuit Size to Pseudorandom Oracles. 392 BibTeX