Education and careerEdit
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 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).
- 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:
- 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.
- Uwe Schöning at the Mathematics Genealogy Project
- Faculty profile, Univ. of Ulm, retrieved 2013-09-07.
- Review of Complexity and Structure by Juris Hartmanis (1987), MR0827009
- Review of Logik für Informatiker by Neculai Curteanu (1989), MR0944086; also listed as MR1244106 (3rd ed.) and MR2683474 (English ed.)
- Review of Logic for Computer Scientists by Riccardo Pucella (2005), SIGACT News 36 (3): 17–19, doi:10.1145/1086649.1086657
- Review of The Graph Isomorphism Problem by Pavol Hell (1995), MR1232421
- 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
- Review of Gems of Theoretical Computer Science by Danny Krizanc (2000), SIGACT News 31 (2): 2–5, doi:10.1145/348210.1042072
- Review of Gems of Theoretical Computer Science by Marius Zimand (2000), MR1667079