10 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…
Restrictive Acceptance Suffices for Equivalence Problems
Bernd Borchert, Lane A. Hemaspaandra, Joerg Rothe
One way of suggesting that an NP problem may not be NP-complete is to show that it is in the class UP. We suggest an analogous new approach---weaker in strength of evidence but mor…
Characterizations of the Existence of Partial and Total One-Way Permutations
Joerg Rothe, Lane A. Hemaspaandra
In this note, we study the easy certificate classes introduced by Hemaspaandra, Rothe, and Wechsung, with regard to the question of whether or not surjective one-way functions exis…
Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
Lane A. Hemaspaandra, Joerg Rothe
It is known that for any class C closed under union and intersection, the Boolean closure of C, the Boolean hierarchy over C, and the symmetric difference hierarchy over C all are…
Raising NP Lower Bounds to Parallel NP Lower Bounds
Edith Hemaspaandra, Lane A. Hemaspaandra, Joerg Rothe
A decade ago, a beautiful paper by Wagner developed a ``toolkit'' that in certain cases allows one to prove problems hard for parallel access to NP. However, the problems his toolk…
A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem
Lane A. Hemaspaandra, Joerg Rothe
Rice's Theorem states that every nontrivial language property of the recursively enumerable sets is undecidable. Borchert and Stephan initiated the search for complexity-theoretic…