10. CoCo 1995: Minneapolis, Minnesota, USA

Session 1

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

Session 2

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

Session 3

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

Session 4

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

Session 5

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

Session 6

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

Session 7

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

Session 8

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