10. CoCo 1995: Minneapolis, Minnesota, USA
Proceedings of the Tenth Annual Structure in Complexity Theory Conference, Minneapolis, Minnesota, USA, June 19-22, 1995. IEEE Computer Society 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
- 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: 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
Session 6
- 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 PiP2-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
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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-19T203413 by the dblp team