14 citations · 36 across the 13 of their papers we have counts for
13 papers
Algebraic Properties for Selector Functions
Lane A. Hemaspaandra, Harald Hempel, Arfst Nickelsen
The nondeterministic advice complexity of the P-selective sets is known to be exactly linear. Regarding the deterministic advice complexity of the P-selective sets--i.e., the amoun…
All Superlinear Inverse Schemes are coNP-Hard
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
How hard is it to invert NP-problems? We show that all superlinearly certified inverses of NP problems are coNP-hard. To do so, we develop a novel proof technique that builds diago…
Using the No-Search Easy-Hard Technique for Downward Collapse
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
The top part of the preceding figure [figure appears in actual paper] shows some classes from the (truth-table) bounded-query and boolean hierarchies. It is well-known that if eith…
P-Immune Sets with Holes Lack Self-Reducibility Properties
Lane A. Hemaspaandra, Harald Hempel
No P-immune set having exponential gaps is positive-Turing self-reducible.
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…