16 papers · 1 filter
An Exact 2.9416^n Algorithm for the Three Domatic Number Problem
Tobias Riege, Jörg Rothe
The three domatic number problem asks whether a given undirected graph can be partitioned into at least three dominating sets, i.e., sets whose closed neighborhood equals the verte…
Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial
Jörg Rothe
In this tutorial, selected topics of cryptology and of computational complexity theory are presented. We give a brief overview of the history and the foundations of classical crypt…
A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs
Andre Grosse, Joerg Rothe, Gerd Wechsung
We show that computing the lexicographically first four-coloring for planar graphs is P^{NP}-hard. This result optimally improves upon a result of Khuller and Vazirani who prove th…
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…