20 citations · 74 across the 17 of their papers we have counts for
20 papers · 1 filter
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…
Almost-Everywhere Superiority for Quantum Computing
Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand
Simon as extended by Brassard and Høyer shows that there are tasks on which polynomial-time quantum machines are exponentially faster than each classical machine infinitely often.…
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…