Uwe Schöning (born 28 December 1955) is a retired German

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

, 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 relating these classes to each other. A computational problem is a task solved by ...

Education and career

Schöning earned his Ph.D. from the

University of Stuttgart The University of Stuttgart (german: Universität Stuttgart) is a leading 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 wit ...

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 (german: Universität Ulm) 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 sci ...

until his retirement in 2021.

Contributions

Schöning introduced the low and high hierarchies 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 compl ...

, 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 algorithms to solve Boolean satisfiability problems. Both algorithms work on formulae in Boolean logic that are in, or have been converted into conjunctive normal form. They start by assigni ...

, 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 by Papadimitriou, had good expected time complexity (although still exponential) when applied to worst-case instances of 3-satisfiability and other

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

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 a set of values for th ...

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. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...

LOOP Loop or LOOP may refer to: Brands and enterprises * Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live * Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets * Loop Mobile, an ...

, 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'' (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 German computer scientists University of Stuttgart alumni Academic staff of the University of Ulm Theoretical computer scientists Programming language designers