default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID6th SCT 1991: Chicago, Illinois, USA
- Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30 - July 3, 1991. IEEE Computer Society 1991, ISBN 0-8186-2255-5
Session 1
- Seinosuke Toda, Mitsunori Ogiwara:
Counting Classes Are at Least as Hard as the Polynomial-Time Hierarchy. 2-12 - Lance Fortnow, Nick Reingold:
PP is Closed Under Truth-Table Reductions. 13-15 - Mitsunori Ogiwara, Lane A. Hemachandra
:
A Complexity Theory for Feasible Closure Properties. 16-29 - Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz:
Gap-Definable Counting Classes. 30-42 - Sanjay Gupta:
The Power of Witness Reduction. 43-59
Session 2
- William I. Gasarch:
Bounded Queries in Recursion Theory: A Survey. 62-78 - Steven Homer, Luc Longpré:
On Reductions of NP Sets to Sparse Sets. 79-88 - Ricard Gavaldà, Osamu Watanabe:
On the Computational Complexity of Small Descriptions. 89-101 - Daniel P. Bovet, Pierluigi Crescenzi, Riccardo Silvestri:
Complexity Classes and Sparse Oracles. 102-108
Session 3
- Jin-yi Cai, Anne Condon, Richard J. Lipton:
PSPACE Is Provable By Two Provers In One Round. 110-115 - Uriel Feige:
On the Success Probability of the Two Provers in One-Round Proof Systems. 116-123 - Joan Feigenbaum, Lance Fortnow:
On the Random-Self-Reducibility of Complete Sets. 124-132 - Rafail Ostrovsky:
One-Way Functions, Hard on Average Problems, and Statistical Zero-Knowledge Proofs. 133-138 - Mitsunori Ogiwara, Antoni Lozano:
On One Query Self-Reducible Sets. 139-151
Session 4
- Ming Li, Paul M. B. Vitányi:
Combinatorics and Kolmogorov Complexity. 154-163 - Peter Bro Miltersen:
The Complexity of Malign Ensembles. 164-171 - Rafi Heiman, Avi Wigderson:
Randomized vs.Deterministic Decision Tree Complexity for Read-Once Boolean Functions. 172-179 - Miklos Santha:
On the Monte Carlo Boolean Decision Tree Complexity of Read-Once Formulae. 180-187
Session 5
- Jack H. Lutz:
A Pseudorandom Oracle Characterization of BPP. 190-195 - Stephen A. Fenner:
Notions of Resource-Bounded Category and Genericity. 196-212 - László Babai, Noam Nisan:
BPP has Subexponential Time Simulation unless EXPTIME has Pubishable Proofs. 213-219 - Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe:
Relating Equivalence and Reducibility to Sparse Sets. 220-229 - Shouwen Tang, Bin Fu, Tian Liu:
Exponential Time and Subexponential Time Sets. 230-237
Session 6
- José L. Balcázar:
Adaptive Logspace and Depth-Bounded Reducibilities. 240-254 - Richard Chang, Jim Kadin, Pankaj Rohatgi:
Connections between the Complexity of Unique Satisfiability and the Threshold Behavior of Randomized Reductions. 255-269 - V. Vinay:
Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. 270-284 - Jun Tarui:
Degree Compexity of Boolean Functions and Its Applications to Realivized Separations. 382-390 - Richard Beigel, Nick Reingold, Daniel A. Spielman:
The Perceptron Strikes Back. 286-291
Session 7
- Michelangelo Grigni, Michael Sipser:
Monotone Separation of Logspace from NC. 294-298 - Mauricio Karchmer, Ran Raz, Avi Wigderson:
Super-logarithmic Depth Lower Bounds via Direct Sum in Communication Coplexity. 299-304 - David A. Mix Barrington, Howard Straubing:
Superlinear Lower Bounds for Bounded-Width Branching Programs. 305-313 - Matthias Krause:
Geometric Arguments Yield Better Bounds for Threshold Circuits and Distributed Computing. 314-321 - Jeff Edmonds:
Lower Bounds with Smaller Domain Size On Concurrent Write Parallel Machines. 322-331
Session 8
- Neil Immerman:
DSPACE[nk] = VAR[k+1]. 334-340 - Erich Grädel:
Capturing Complexity Classes by Fragments of Second Order Logic. 341-352 - Phokion G. Kolaitis, Madhukar N. Thakur:
Approximation Properties of NP Minimization Classes. 353-366 - Stephen J. Bellantoni, Toniann Pitassi, Alasdair Urquhart:
Approximation and Small Depth Frege Proofs. 367-390
Errata
- Jack H. Lutz, William J. Schmidt:
Errata for Circuit Size to Pseudorandom Oracles. 392
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-06-17 21:06 CEST 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:
