10. CoCo 1995: Minneapolis, Minnesota, USA

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, June 19-22, 1995, Minneapolis, Minnesota, USA. IEEE Computer Society Press, 1995, ISBN 0-8186-7052-5

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

Last update Thu May 24 04:15:01 2012 CET by the DBLP Team —

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