10. CoCo 1995: Minneapolis, Minnesota, USA

Session 1

• Kousha Etessami: Counting Quantifiers, Successor Relations, and Logarithmic Space. 2-11 BibTeX
• Marius Zimand: Weighted NP Optimization Problems: Logical Definability and Approximation Properties. 12-28 BibTeX
• Kazuo Iwama, Eiji Miyano: Intractability of Read-Once Resolution. 29-36 BibTeX
• James S. Royer: Semantics versus Syntax versus Computations. 37-48 BibTeX

Session 2

• Kenneth W. Regan: On Superlinear Lower Bounds in Complexity Theory. 50-64 BibTeX
• Anna Gál, Mario Szegedy: Fault Tolerant Circuits and Probabilistically Checkable Proofs. 65-73 BibTeX
• Yosi Ben-Asher, Ilan Newman: Decision Trees with AND, OR Queries. 74-81 BibTeX
• Anna Gál: Semi-Unbounded Fan-In Circuits: Boolean vs. Arithmetic. 82-87 BibTeX

Session 3

• John D. Rogers: The Isomorphism Conjecture Holds and One-Way Functions Exist Relative to an Oracle. 90-101 BibTeX
• Stephen A. Fenner: Inverting the Turing Jump in Complexity Theory. 102-110 BibTeX
• Martin Kummer: The Instance Complexity Conjecture. 111-124 BibTeX
• Richard Beigel, William I. Gasarch, Efim B. Kinber: Frequency Computation and Bounded Queries. 125-132 BibTeX

Session 4

• Russell Impagliazzo: A Personal View of Average-Case Complexity. 134-147 BibTeX
• Rainer Schuler, Osamu Watanabe: Towards Average-Case Complexity Analysis of NP Optimization Problems. 148-159 BibTeX

Session 5

• Klaus Ambos-Spies: Resource-Bounded Genericity. 162-181 BibTeX
• Stephen A. Fenner: Resource-Bounded Baire Category: A Stronger Approach. 182-192 BibTeX
• José L. Balcázar, Elvira Mayordomo: A Note on Genericity and Bi-Immunity. 193-196 BibTeX
• Harry Buhrman, Elvira Mayordomo: An Excursion to the Kolmogorov Random Strings. 197-203 BibTeX

Session 6

• Yenjo Han, Thomas Thierauf: Restricted Information from Nonadaptive Queries to NP. 206-213 BibTeX
• Sameet Agarwal, Anne Condon: On Approximation Algorithms for Hierarchical MAX-SAT. 214-226 BibTeX
• Joan Feigenbaum, Daphne Koller, Peter W. Shor: A Game-Theoretic Classification of Interactive Complexity Classes. 227-237 BibTeX
• Chih-Long Lin: Optimizing TRIEs for Ordered Pattern Matching is Pi^P₂-Complete. 238-244 BibTeX

Session 7

• Johannes Köbler: On the Structure of Low Sets. 246-261 BibTeX
• Nicholas Q. Trân: On P-Immunity of Nondeterministic Complete Sets. 262-263 BibTeX
• Manindra Agrawal, Vikraman Arvind: Reductions of Self-Reducible Sets to Depth-1 Weighted Threshold Circuit Classes, and Sparse Sets. 264-276 BibTeX
• Richard Beigel, Howard Straubing: The Power of Local Self-Reductions. 277-285 BibTeX

Session 8

• Richard Chang, William I. Gasarch, Jacobo Torán: On Finding the Number of Graph Automorphisms. 288-298 BibTeX
• Ulrich Hertrampf, Heribert Vollmer, Klaus W. Wagner: On the Power of Number-Theoretic Operations with Respect to Counting. 299-314 BibTeX
• Manindra Agrawal: DSPACE(n)=^?NSPACE(n): A Degree Theoretic Characterization. 315-323 BibTeX
• Jack H. Lutz: A Small Span Theorem for P/Poly-Turing Reductions. 324-330 BibTeX