11 citations · 18 across the 6 of their papers we have counts for
9 papers · 2 filters
Translating Equality Downwards
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
Downward translation of equality refers to cases where a collapse of some pair of complexity classes would induce a collapse of some other pair of complexity classes that (a priori…
Query Order and the Polynomial Hierarchy
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] initiated the field of query order, which studies the ways in which computational power is affected by the order in which informa…
A Downward Collapse within the Polynomial Hierarchy
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
Downward collapse (a.k.a. upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downwar…
An Introduction to Query Order
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] raised the following questions: If one is allowed one question to each of two different information sources, does the order in wh…
R_{1-tt}^{SN}(NP) Distinguishes Robust Many-One and Turing Completeness
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
Do complexity classes have many-one complete sets if and only if they have Turing-complete sets? We prove that there is a relativized world in which a relatively natural complexity…
What's Up with Downward Collapse: Using the Easy-Hard Technique to Link Boolean and Polynomial Hierarchy Collapses
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
During the past decade, nine papers have obtained increasingly strong consequences from the assumption that boolean or bounded-query hierarchies collapse. The final four papers of…