Uwe Schöning

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

Education and career

Schöning earned his Ph.D. from the University of Stuttgart in 1981, under the supervision of Wolfram Schwabhäuser.[1] He was a professor in the Institute for Theoretical Informatics at the University of Ulm until his retirement in 2021.[2]

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, 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.

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).[3]
• Logik für Informatiker (in German, Reihe Informatik, 1987; 5th ed., Springer, 2000). Translated into English as Logic for Computer Scientists (Birkhäuser, 1989).[4][5]
• 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).[6]
• 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).[7][8][9]
• 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:

• Schöning, Uwe (1983), "A low and a high hierarchy within NP", Journal of Computer and System Sciences, 27 (1): 14–28, doi:10.1016/0022-0000(83)90027-2, MR 0730913.
• Schöning, Uwe (1988), "Graph isomorphism is in the low hierarchy", Journal of Computer and System Sciences, 37 (3): 312–323, doi:10.1016/0022-0000(88)90010-4, MR 0975447.
• Schoning, U. (1999), "A probabilistic algorithm for k-SAT and constraint satisfaction problems", Proceedings of 40th Annual Symposium on Foundations of Computer Science, pp. 410–414, doi:10.1109/SFFCS.1999.814612, S2CID 123177576.

References

1. Uwe Schöning at the Mathematics Genealogy Project
2. Faculty profile, Univ. of Ulm, retrieved 2022-03-28.
3. Review of Complexity and Structure by Juris Hartmanis (1987), MR0827009
4. Review of Logik für Informatiker by Neculai Curteanu (1989), MR0944086; also listed as MR1244106 (3rd ed.) and MR2683474 (English ed.)
5. Review of Logic for Computer Scientists by Riccardo Pucella (2005), SIGACT News 36 (3): 17–19, doi:10.1145/1086649.1086657
6. Review of The Graph Isomorphism Problem by Pavol Hell (1995), MR1232421
7. Review of Gems of Theoretical Computer Science by Rohit Jivanlal Parikh (2000), Journal of Logic, Language and Information 9 (1): 131–132, doi:10.1023/A:1008379701961
8. Review of Gems of Theoretical Computer Science by Danny Krizanc (2000), SIGACT News 31 (2): 2–5, doi:10.1145/348210.1042072
9. Review of Gems of Theoretical Computer Science by Marius Zimand (2000), MR1667079

External links

• Google scholar profile