35 citations · 200 across the 47 of their papers we have counts for
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…
Boolean Operations, Joins, and the Extended Low Hierarchy
Lane A. Hemaspaandra, Zhigen Jiang, Joerg Rothe +1
We prove that the join of two sets may actually fall into a lower level of the extended low hierarchy than either of the sets. In particular, there exist sets that are not in the s…
Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP
Edith Hemaspaandra, Lane A. Hemaspaandra, Joerg Rothe
In 1876, Lewis Carroll proposed a voting system in which the winner is the candidate who with the fewest changes in voters' preferences becomes a Condorcet winner---a candidate who…
Easy Sets and Hard Certificate Schemes
Lane A. Hemaspaandra, Joerg Rothe, Gerd Wechsung
Can easy sets only have easy certificate schemes? In this paper, we study the class of sets that, for all NP certificate schemes (i.e., NP machines), always have easy acceptance ce…
Polynomial-Time Multi-Selectivity
Lane A. Hemaspaandra, Zhigen Jiang, Joerg Rothe +1
We introduce a generalization of Selman's P-selectivity that yields a more flexible notion of selectivity, called (polynomial-time) multi-selectivity, in which the selector is allo…