- Kousha Etessami:
A Hierarchy of Polynomial-Time Computable Simulations for Automata. CONCUR 2002: 131-144 - 1999
- Jin-yi Cai:
A Classification of the Probabilistic Polynomial Time Hierarchy Under Fault Tolerant Access to Oracle Classes. Inf. Process. Lett. 69(4): 167-174 (1999) - Jin-yi Cai, Ajay Nerurkar, D. Sivakumar:
Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time. STOC 1999: 726-735 - Adam R. Klivans, Dieter van Melkebeek:
Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. STOC 1999: 659-667 - 1998
- Herbert Baier, Klaus W. Wagner:
The Analytic Polynomial Time Hierarchy. Math. Log. Q. 44: 529-544 (1998) - Herbert Baier, Klaus W. Wagner:
Bounding Queries in the Analytic Polynomial-Time Hierarchy. Theor. Comput. Sci. 207(1): 89-104 (1998) - Adam R. Klivans, Dieter van Melkebeek:
Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- Anthony J. Bonner:
Intuitionistic Deductive Databases and the Polynomial Time Hierarchy. J. Log. Program. 33(1): 1-47 (1997) - 1996
- Ran Canetti:
More on BPP and the Polynomial-Time Hierarchy. Inf. Process. Lett. 57(5): 237-241 (1996) - 1994
- Ronald V. Book:
On Collapsing the Polynomial-Time Hierarchy. Inf. Process. Lett. 52(5): 235-237 (1994) - 1993
- Jun Tarui:
Probablistic Polynomials, AC0 Functions, and the Polynomial-Time Hierarchy. Theor. Comput. Sci. 113(1): 167-183 (1993) - 1992
- Peter Clote:
A Time-Space Hierarchy Between Polynomial Time and Polynomial Space. Math. Syst. Theory 25(2): 77-92 (1992) - Seinosuke Toda, Mitsunori Ogiwara:
Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy. SIAM J. Comput. 21(2): 316-328 (1992) - Paul Young:
How reductions to sparse sets collapse the polynomial-time hierarchy: a primer; part I: polynomial-time Turing reductions. SIGACT News 23(3): 107-117 (1992) - Paul Young:
How reductions to sparse sets collapse the polynomial-time hierarchy: a primer: Part II restricted polynomial-time reductions. SIGACT News 23(4): 83-94 (1992) - 1991
- Jim Kadin:
Erratum: The Polynomial Time Hierarchy Collapses if the Boolean Hierarchy Collapses. SIAM J. Comput. 20(2): 404 (1991) - Seinosuke Toda:
PP is as Hard as the Polynomial-Time Hierarchy. SIAM J. Comput. 20(5): 865-877 (1991) - Seinosuke Toda, Mitsunori Ogiwara:
Counting Classes Are at Least as Hard as the Polynomial-Time Hierarchy. SCT 1991: 2-12 - 1990
- Ker-I Ko:
A note on separating the relativized polynomial time hierarchy by immune sets. RAIRO Theor. Informatics Appl. 24: 229-240 (1990) - Ker-I Ko:
Separating and Collapsing Results on the Relativized Probabilistic Polynomial-Time Hierarchy. J. ACM 37(2): 415-438 (1990) - 1989
- Ronald V. Book, Shouwen Tang:
A Note on Sparse Sets and the Polynomial-Time Hierarchy. Inf. Process. Lett. 33(3): 141-143 (1989) - Jin-yi Cai:
With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy. J. Comput. Syst. Sci. 38(1): 68-85 (1989) - 1988
- Jim Kadin:
Restricted Turing Reducibilities & the Structure of the Polynomial Time Hierarchy. Cornell University, USA, 1988 - Leen Torenvliet:
A Second Step Toward the Strong Polynomial-Time Hierarchy. Math. Syst. Theory 21(2): 99-123 (1988) - Jim Kadin:
The Polynomial Time Hierarchy Collapses if the Boolean Hierarchy Collapses. SIAM J. Comput. 17(6): 1263-1282 (1988) - Erich Grädel:
Subclasses of Presburger Arithmetic and the Polynomial-Time Hierarchy. Theor. Comput. Sci. 56: 289-301 (1988) - Jim Kadin:
The polynomial time hierarchy collapses if the Boolean hierarchy collapses. SCT 1988: 278-292 - 1987
- Bogdan S. Chlebus:
A note on the polynomial-time hierarchy and the quantified Boolean formulas. Bull. EATCS 31: 15-21 (1987) - László Babai:
Random Oracles Separate PSPACE from the Polynomial-Time Hierarchy. Inf. Process. Lett. 26(1): 51-53 (1987) - Claus-Peter Schnorr:
A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms. Theor. Comput. Sci. 53: 201-224 (1987)