![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
6th 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
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
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.