Uwe Schöning (born 28 December 1955) is a retired German
computer scientist
A computer scientist is a scientist who specializes in the academic study of computer science.
Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...
, known for his research in
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
.
Education and career
Schöning earned his Ph.D. from the
University of Stuttgart
The University of Stuttgart () is a research university located in Stuttgart, Germany. It was founded in 1829 and is organized into 10 faculties. It is one of the oldest technical universities in Germany with programs in civil, mechanical, ind ...
in 1981, under the supervision of Wolfram Schwabhäuser.
He was a professor in the Institute for Theoretical Informatics at the
University of Ulm
Ulm University () is a public university in Ulm, Baden-Württemberg, Germany. The University was founded in 1967 and focuses on natural sciences, medicine, engineering sciences, mathematics, economics and computer science. With 9,891 studen ...
until his retirement in 2021.
Contributions
Schöning introduced the
low and high hierarchies In the computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these c ...
to
structural complexity theory in 1983. As Schöning later showed in a 1988 paper, these hierarchies play an important role in the complexity of the
graph isomorphism problem
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.
The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational c ...
, which Schöning further developed in a 1993 monograph with Köbler and Toran.
In a 1999
FOCS paper, Schöning showed that
WalkSAT
In computer science, GSAT and WalkSAT are Local_search (optimization), local search algorithms to solve Boolean_satisfiability_problem, Boolean satisfiability problems.
Both algorithms work on Well-formed formula, formulae in Boolean logic that ar ...
, a
randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
previously analyzed for
2-satisfiability
In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case ...
by
Papadimitriou, had good
expected time complexity (although still exponential) when applied to worst-case instances of
3-satisfiability
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) asks whether there exists an interpretation that satisfies a given Boolean f ...
and other
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
constraint satisfaction In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through
a set of constraints that impose conditions that the variables must satisfy. A solution is therefore an assignment of value ...
problems. At the time this was the fastest guaranteed time bound for 3SAT; subsequent research has built on this idea to develop even faster algorithms.
Schöning is also the inventor of the pedagogical
programming language
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
s
LOOP, GOTO, and WHILE, which he described in his textbook ''Theoretische Informatik - kurz gefasst''.
Selected publications
Schöning is the author or editor of many books in computer science, including
*''Complexity and Structure'' (Springer, Lecture Notes in Computer Science 211, 1985).
*''Logik für Informatiker'' (in German, Reihe Informatik, 1987; 5th ed., Springer, 2000). Translated into English as ''Logic for Computer Scientists'' (Birkhäuser, 1989).
*''Theoretische Informatik - kurz gefasst'' (in German, BI-Wiss.-Verlag, 1992; 5th ed., Spektrum, 2008)
*''The Graph Isomorphism Problem: Its Structural Complexity'' (with J. Köbler and J. Toran, Birkhäuser, 1993).
*''Perlen der Theoretischen Informatik'' (in German, Bibl. Institut Wissenschaftsverlag, 1995). Revised and Translated into English as ''Gems of Theoretical Computer Science'' (with R. J. Pruim, Springer, 1998).
[Review of ''Gems of Theoretical Computer Science'' by Marius Zimand (2000), ]
*''Algorithmen - kurz gefasst'' (in German, Spektrum, 1997).
*''Algorithmik'' (in German, Spektrum, 2001).
*''Ideen der Informatik'' (in German, Oldenbourg, 2002, 2nd ed. 2005).
*''Mathe-Toolbox - Mathematische Notationen, Grundbegriffe und Beweismethoden'' (with H. A. Kestler, Lehmanns, 2010).
*''Kryptologie-Kompendium'' (Lehmanns, 2012).
*''Das Erfüllbarkeitsproblem SAT - Algorithmen und Analysen'' (with J. Toran, in German, Lehmanns, 2012). Translated into English as ''The Satisfiability Problem - Algorithms and Analyses'' (Lehmanns, 2013).
His research articles include:
*.
*.
*.
References
External links
Google scholar profile
{{DEFAULTSORT:Schoning, Uwe
1955 births
Living people
University of Stuttgart alumni
Academic staff of the University of Ulm
German theoretical computer scientists
Programming language designers