All reports by Author Jörg Rothe:

__
TR06-078
| 12th June 2006
__

Tobias Riege, Jörg Rothe#### Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem

Revisions: 1

__
TR06-036
| 7th February 2006
__

Tobias Riege, Jörg Rothe#### Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems

Revisions: 1

__
TR05-146
| 25th November 2005
__

Gábor Erdèlyi, Tobias Riege, Jörg Rothe#### Quantum Cryptography: A Survey

Revisions: 2

__
TR02-068
| 10th December 2002
__

Tobias Riege, Jörg Rothe#### Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem

Revisions: 2

__
TR01-096
| 21st November 2001
__

Jörg Rothe#### Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial

Revisions: 1

__
TR96-045
| 28th August 1996
__

Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe#### Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems

Comments: 2

Tobias Riege, Jörg Rothe

NP-complete problems cannot have efficient algorithms unless P = NP. Due to their importance in practice, however, it is useful to improve the known exponential-time algorithms for NP-complete problems. We survey some of the recent results on such improved exponential-time algorithms for the NP-complete problems satisfiability, graph colorability, and the ... more >>>

Tobias Riege, Jörg Rothe

This paper surveys some of the work that was inspired by Wagner's general technique to prove completeness in the levels of the boolean hierarchy over NP and some related results. In particular, we show that it is DP-complete to decide whether or not a given graph can be colored with ... more >>>

Gábor Erdèlyi, Tobias Riege, Jörg Rothe

We survey some results in quantum cryptography. After a brief

introduction to classical cryptography, we provide the physical and

mathematical background needed and present some fundamental protocols

from quantum cryptography, including quantum key distribution and

quantum bit commitment protocols.

Tobias Riege, Jörg Rothe

We prove that the exact versions of the domatic number problem are complete

for the levels of the boolean hierarchy over NP. The domatic number

problem, which arises in the area of computer networks, is the problem of

partitioning a given graph into a maximum number ...
more >>>

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 cryptography, and then

move on to modern public-key cryptography. Particular attention is

paid to cryptographic protocols and the problem of constructing ...
more >>>

Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe

We study EP, the subclass of NP consisting of those

languages accepted by NP machines that when they accept always have a

number of accepting paths that is a power of two. We show that the

negation equivalence problem for OBDDs (ordered binary decision

diagrams) ...
more >>>