Uwe Schöning

Uwe Schöning (born 28 December 1955) is a German computer scientist, known for his research in computational complexity theory.

Schöning earned his Ph.D. from the University of Stuttgart in 1981, under the supervision of Wolfram Schwabhäuser. He is a professor in the Institute for Theoretical Informatics at the University of Ulm.

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, which Schöning further developed in a 1993 monograph with Köbler and Toran.

In a 1999 FOCS paper, Schöning showed that WalkSAT, a randomized algorithm 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 constraint satisfaction 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 languages LOOP, GOTO, and WHILE, which he described in his textbook Theoretische Informatik - kurz gefasst.

Schöning is the author or editor of many books in computer science, including

His research articles include:

...
Wikipedia