default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID10th SCT 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 - 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 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 - 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-23 19:41 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
