default search action
3rd SCT 1988: Georgetown University, Washington, D. C., USA
- Proceedings: Third Annual Structure in Complexity Theory Conference, Georgetown University, Washington, D. C., USA, June 14-17, 1988. IEEE Computer Society 1988, ISBN 0-8186-0794-7
- Ker-I Ko:
Relativized polynomial time hierarchies having exactly K levels. - Uwe Schöning:
The power of counting. 2-9 - Shouwen Tang, Osamu Watanabe
:
On tally relativizations of BP-complexity classes. 10-18 - Bernd Halstenberg, Rüdiger Reischuk:
Relations between communication complexity classes. 19-28 - Russell Impagliazzo
Decision trees and downward closures. 29-38 - José L. Balcázar:
Logspace self-reducibility. 40-46 - David A. Mix Barrington, Neil Immerman, Howard Straubing:
On uniformity within NC1. 47-59 - Leonard Pitt, Manfred K. Warmuth:
Reductions among prediction problems: on the difficulty of predicting automata. 60-69 - Oscar H. Ibarra, Tao Jiang:
Trading reversals for alternation. 70-77 - Ming Li, Paul M. B. Vitányi:
Two decades of applied Kolmogorov complexity: in memoriam Andrei Nikolaevich Kolmogorov 1903-87. 80-101 - Eric Allender, Osamu Watanabe
Kolmogorov complexity and degrees of tally sets. 102-111 - Neil Immerman:
Nondeterministic space is closed under complementation. 112-115 - Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo
Two applications of complementation via inductive counting. 116-125 - Richard Edwin Stearns:
Juris Hartmanis: the beginnings of computational complexity. 128-134 - Allan Borodin:
Juris Hartmanis: building a department-building a discipline. 135-137 - Paul Young:
Juris Hartmanis: fundamental contributions to isomorphism problems. 138-154 - Lance Fortnow, John Rompel, Michael Sipser:
On the power of multi-power interactive protocols. 156-161 - Anne Condon:
Space bounded probabilistic game automata. 162-174 - Jack H. Lutz:
Pseudorandom sources for BPP. 175-180 - Ker-I Ko:
Distinguishing bounded reducibilities by sparse sets. 181-191 - Jin-Yi Cai, Lane A. Hemachandra
Enumerative counting is hard. 194-203 - Dung T. Huynh:
The complexity of ranking. 204-212 - Jacobo Torán:
An oracle characterization of the counting hierarchy. 213-223 - Samuel R. Buss, Louise Hay:
On truth-table reducibility to SAT and the difference hierarchy over NP. 224-233 - Ronald V. Book, Ding-Zhu Du, David A. Russo:
On polynomial and generalized complexity cores. 236-250 - Juichi Shinoda, Theodore A. Slaman:
On the theory of the PTIME degrees of the recursive sets. 252-257 - Klaus W. Wagner:
Bounded query computations. 260-277 - Jim Kadin:
The polynomial time hierarchy collapses if the Boolean hierarchy collapses. 278-292 - Luc Longpré, Paul Young:
Cook is faster than Karp: a study of reducibilities in NP. 293-302
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 2024-12-23 19:18 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: