Die bibliographische Datenbank LEABib

Suchen • Liste der Journale • Liste der Serien • Liste der Konferenzen • Ausgewählte Publikationen [1]	Hilfe

Suche: Booktitle=Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991)

Als [bib] [pdf] [ps] [dvi] [xml] herunterladen.

Counting classes are at least as hard as the polynomial-time hierarchy
Seinosuke Toda, Mitsunori Ogiwara
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 2-12
PP is closed under truth-table reductions
Lance Fortnow, Nick Reingold
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 13-15
A complexity theory for feasible closure properties
Mitsunori Ogiwara, Lane A. Hemachandra
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 16-29
Gap-definable counting classes
Stephen A. Fenner, Lance J. Fortnow, Stuart A. Kurtz
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 30-42
The power of witness reduction
Sanjay Gupta
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 43-59
Bounded queries in recursion theory: A survey
William Gasarch
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 62-78
On reductions of NP sets to sparse sets
Steven Homer, Luc Longpré
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 79-88
On the computational complexity of small descriptions
Ricard Gavaldà, Osamu Watanabe
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 89-101
Complexity classes and sparse oracles
D.P. Bovet, P. Crescenzi, R. Silvestri
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 102-108
PSPACE is provable by two provers in one round
Jin-Yi Cai, Anne Condon
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 110-115
On the success probability of the two provers in one-round proof systems
Uriel Feige
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 116-123
On the random-self-reducibility of complete sets
Joan Feigenbaum, Lance Fortnow
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 124-132
One-way functions, hard-on-average problems, and statistical zero-knowledge proofs
Rafail Ostrovsky
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 133-138
On one-query self-reducible sets
Mitsunori Ogiwara, Antoni Lozano
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 139-151
Combinatorics and Kolmogorov complexity
Ming Li, Paul M.B. Vitányi
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 154-163
The complexity of malign ensembles
Peter Bro Miltersen
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 164-171
Randomized vs.\ deterministic decision tree complexity for read-once Boolean functions
Rafi Heiman, Avi Wigderson
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 172-179
On the Monte Carlo Boolean decision tree complexity of read-once formulae
Miklos Santha
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 180-187
A pseudorandom oracle characterization of BPP
Jack H. Lutz
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 190-195
Notions of resource-bounded category and genericity
Stephen A. Fenner
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 196-212
BPP has subexponential time simulations unless EXPTIME has publishable proofs
László Babai, Noam Nisan, Lance Fortnow, Avi Wigderson
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 213-219
Relating equivalence and reducibility to sparse sets
Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 220-229
Exponential time and subexponential time sets
Shouwen Tang, Bin Fu, Tian Liu
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 230-237
Adaptive logspace and depth-bounded reducibilities
José L. Balcázar
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 240-254
Connections between the complexity of unique satisfiability and the threshold behavior of randomized reductions
Richard Chang, Jim Kadin, Pankaj Rohatgi
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991), 1991, pp. 255-269

Seiten 1 2 >