Showing 2001Show all
2 papers · 1 filter
cs.CC2001
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…
cs.CC2001
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…