20 citations · 76 across the 24 of their papers we have counts for
19 papers · 2 filters
One-Way Functions in Worst-Case Cryptography: Algebraic and Security Properties
A. Beygelzimer, L. A. Hemaspaandra, C. M. Homan +1
We survey recent developments in the study of (worst-case) one-way functions having strong algebraic and security properties. According to [RS93], this line of research was initiat…
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…
Self-Specifying Machines
Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung
We study the computational power of machines that specify their own acceptance types, and show that they accept exactly the languages that $\manyonesharp$-reduce to NP sets. A natu…
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…