List of on-line available publications of Uwe Schöning

A. Balint, U. Schöning. Choosing Probability Distributions for Stochastic Local Search and the Role of Make versus Break. 15th International Conference on Theory and Applications of Satisfiability Testing, SAT 2012.
T. Schnattinger, U. Schöning, H. A. Kestler. Pareto-optimal RNA sequence-structure alignments. 9th International Workshop on Computational Systems Biology WSCB 2012.
U. Schöning, W. Thomas. Turings Arbeiten über Berechenbarkeit - eine Einführung und Lesehilfe. Springer Informatik-Spektrum, 2012.
U. Schöning. Das SAT-Problem. Springer Informatik-Spektrum, 2010.
U. Schöning. Comparing two stochastic local search algorithms for constraint satisfaction problems. Proc. CSR 2010. Springer Lecture Notes in Computer Science.
U. Schöning, M. v. Knop. Using stochastic indexed grammars for RNA structure prediction with pseudoknots. Bulletin of the EATCS 2010.
B. List, M. Maucher, U. Schöning, R. Schuler. Quicksort under an information-theoretic view. in: W. Arendt, W. Schleich (ed.), Mathematical analysis of evolution, information, and complexity. Wiley-VCH, 2009, 455-464.
M. Maucher, U. Schöning, H.A. Kestler. An empirical assessment of local and population based search methods with different degrees of pseudorandomness. Tech. Report, Univ. Ulm, 2008
M. Maucher, U. Schöning, H.A. Kestler. On the different notions of pseudorandomness. Tech. Report, Univ. Ulm, 2008.
T. Hofmeister, U. Schöning, R. Schuler, O. Watanabe. Randomized algorithms for 3-SAT. Theor. Comput. Sci. 40 (3) (2007) 249-262.
U. Schöning. Principles of stochastic local search. Unconventional computation. 6th international conference, UC 2007. Lecture Notes in Computer Science 4618, Springer 2007, 178-187.
U. Schöning. Smaller superconcentrators of density 28. Information Proc. Letters 98 (4) 2006, 127-129.
U. Schöning, J. Torán. A note on the size of Craig interpolants. Circuits, Logic, and Games (2006).
U. Schöning. Moderately exponential algorithms. ALGO 2006.
U. Schöning. Ein Spiel mit Steinchen auf Graphen zum Studium von Rechenzeit und Speicherplatz. Der Mathematik-Unterricht: Algorithmen, Jahrgang 52, Heft 1, 2006, 40-48.
U. Schöning. New algorithmic paradigms in exponential time algorithms. Proc. Computability in Europe, CiE 2005, Lecture Notes in Computer Science 3526, Springer 2005, 429-429.
U. Schöning. Algorithmics in exponential time. Proceedings of the Symposium on Theoretical Aspects of Computer Science, STACS 2005, Lecture Notes in Computer Science 3404, Springer 2005, 36-43.
B. List, M. Maucher, U. Schöning, R. Schuler. Randomized Quicksort and the entropy of the random source. Proceedings COCOON 2005, Lecture Notes in Computer Science 3595, Springer 2005, 450-460.
U. Schöning. Komplexität von Erfüllbarkeitsproblemen. Nordrhein-Westfälische Akademie der Wissenschaften, Vorträge I11, Verlag Ferdinand Schöningh, 2004, 23-35.
U. Schöning. The role of randomization in 3-SAT algorithms. Proceedings Guangzhou Sympos. on Satisfiability in Logic-Based Modeling, 2004, pages 114-121.
T. Hofmeister, U. Schöning, R. Schuler, O. Watanabe. A probabilistic 3-SAT algorithm further improved. Symposium on Theoretical Aspects of Computer Science, STACS 2002. Lecture Notes in Computer Science 2285, Springer 2002, 192-202.
U. Schöning. A probabilistic algorithm for k-SAT based on limited local search and restart. Algorithmica 32,4 (2002) 615-623.
E. Dantsin, A. Goerdt, E.A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schöning. A deterministic (2-2/(k+1))ⁿ algorithm for k-SAT based on local search. Theoretical Computer Science 289/1 (2002) 69-83.
U. Schöning. New algorithms for k-SAT based on the local search principle. Proceedings Math. Foundat. Comput. Theory, MFCS 2001, Lecture Notes in Computer Science 2136, Springer 2001, 87-95.
U. Schöning. Construction of expanders and superconcentrators using Kolmogorov complexity. Journal of Random Structures and Algorithms 17 (2000) 64-77.
E. Dantsin, A. Goerdt, E.A. Hirsch, U. Schöning. A deterministic algorithm for k-SAT based on covering codes and local search. Intern. Colloq. on Automata, Languages and Computation, ICALP 2000, Lecture Notes in Computer Science 1853. Springer 2000, 236-247.
U Schöning. Mastering the master theorem. Bulletin of the EATCS 71, 165-166 (2000).
U. Schöning. Muss die Wahrheitstafel sein - Lösung für das 3-SAT-Problem. Uni Ulm intern, Mai 2000.
U. Schöning. A probabilistic algorithm for k-SAT and constraint satisfaction problems. Proc. 40th Sympos. on Foundations of Computer Science. FOCS 1999, IEEE, 410-414.
U. Schöning. On the complexity of constraint satisfaction problems. Tech. Report, Univ. Ulm, 1998.
U. Schöning. Better expanders and superconcentrators by Kolmogorov complexity. Proceedings Structure in Communication Complexity. SIROCCO 1997. Carleton Scientific, 138-150.
U. Schöning. Complexity of Presburger arithmetic with fixed quantifier dimension. Mathematical Systems Theory 30 (1997) 423-428
U. Schöning. Resolution proofs, exponential lower bounds, and Kolmogorov complexity. Proceedings Symposium on Mathematical Foundations of Computer Science. MFCS 1997, Lecture Notes in Computer Science 1295, Springer 1997, 110-116.
U. Schöning. Wie man Beweise führen kann: interaktiv und ohne den Beweris zu verraten. In: I. Wegener (Hg.): Highlights aus der Informatik, Springer, 1996, 287-304.
U. Schöning. Perlen der Theoretischen Informatik. Bibl. Institut, 1995.
V. Arvind, J. Köbler, U. Schöning, R. Schuler. If NP has polynomial-size circuits, then MA=AM. Theoretical Computer Science 137 (1995) 279-282.
U. Schöning. Gelungene Wortschöpfung - Die Informatik als Wissenschaft, was ist, was kann, was will sie? Uni Ulm intern, Juni 1995.
K. Ko, P. Orponen, U. Schöning, O. Watanabe. Instance complexity. Journal of the ACM 41, No 1 (1994) 96-121.
U. Schöning. On random reductions from sparse sets to tally sets. Information Proc. Letters 46 (1993) 239-241.
J. Köbler, U. Schöning, J. Toran. Graph isomorphism is low for PP. Sympos. on Theoretical Aspects of Computer Science, STACS 1992, Lecture Notes in Computer Science 577, Springer, 1992, 401-411. appeared in: Journal of Computational Complexity 2 (1992) 301-330.
J.L. Balcazar, U. Schöning. Logarithmic advice classes, Theor. Comput. Sci. 99 (1992), 279-290.
V. Arvind, Y. Han, L. Hemachandra, J. Köbler, A. Lozano, M. Mundhenk, M. Ogiwara, U. Schöning, R. Silvestri, T. Thierauf. Reductions to sets of low information content. Intern. Colloq. Automata, Languages and Programming, ICALP 1992, Lecture Notes in Computer Science 623, Springer 1992, 162-173.
U. Schöning. Recent Highlights in Structural Complexity Theory. SOFSEM 1991. Conference Proceedings, pages 205-216.
U. Schöning. Complexity cores and hard problem instances. Symposium on Algorithms, SIGAL 90. Lecture Notes in Computer Science 450, Springer 1990, 232-240.
U. Schöning. The power of counting. in: A.L. Selman (ed.): Complexity Theory Retrospective. Springer, 1990, pages 204-223.
J. Köbler, U. Schöning, S. Toda und J. Toran. Turing machines with few accepting computations and low sets for PP, Conf. on Structure in Comput. Complexity, CCC 1989, IEEE, 208-215, 1989.
U. Schöning, R. Schuler. Renamable Horn clauses and unit resolution. Tech. Report, Univ. Koblenz, 1989.
J. Köbler, U. Schöning, J. Torán. On counting and approximation. Acta Informatica 26, 363-379 (1989).
U. Schöning. Probabilistic complexity classes and lowness. Journal of Computer and System Sciences 39 (1989) 84-100.
U. Schöning, K. Wagner. Collapsing oracle hierarchies, census functions and logarithmically many queries. Sympos. on Theoretical Aspects of Computer Science, STACS 1988, Lecture Notes in Computer Science 294, Springer 1988, 91-97.
U. Schöning. Robust oracle machines. Sympos. on Mathem. Found. of Computer Science, MFCS 1988, Lecture Notes in Computer Science 324, Springer 1988, 93-106.
U. Schöning. Graph Isomorphism is in the Low Hierarchy. Computer and System Sciences, Vol. 37, No. 3 (1988) 312-323.
Uwe Schöning. Complexity cores and hard-to-prove formulas. Workshop on Computer Science Logic, CSL 1987, Lecture Notes in Computer Science 329, Springer 1988, 273-280.
U. Schöning. Graph isomorphism is in the low hierarchy. Sympos. Theor. Aspects of Computer Science, STACS 1987, Lecture Notes in Computer Science 247, Springer 1987, 114-124.
U. Schöning. Lower bounds by recursion-theoretic arguments. Intern. Colloq. Automata, Languages and Programming, ICALP 1986 , Lecture Notes in Computer Science 226, Springer 1986, 123–135.
K. Ko, P. Orponen, U. Schöning, O. Watanabe. What is a hard instance of a computational problem? Structure in Complexity Theory. Conf. 1986, Lecture Notes in Computer Science, Springer 1986, 197-217.
P. Orponen, U. Schöning. The Density and Complexity of Polynomial Cores for Intractable Sets.
Information and Control, Vol 70, No. 1 (1986) 54-68.
J. L. Balcázar, U. Schöning. Bi-immune sets for complexity classes. Math. Systems Theory 18, 1-10 (1985).
P. Orponen, D. A. Russo, U. Schöning. Polynomial levelability and maximal complexity cores. Intern. Collq. Automata, Languages and Programming, ICALP 1985, Lecture Notes in Computer Science 194, Springer 1985, 435-444.
U. Schöning. Robust algorithms: a different approach to oracles. Theor. Comput. Sci. 40, (1985) 57-66.
K. Ko, U. Schöning. On circuit-size complexity and the low hierarchy for NP. SIAM Journal on Computing 14,1 (1985) 41-51.
J. L. Balcázar, R. V. Book, U. Schöning. Sparse oracles, lowness, and highness. Sympos. Math. Foundat. of. Computer Science, MFCS 1984, Lecture Notes in Computer Science 176, Springer 1984, 185-193.
P. Orponen, U. Schöning. The structure of polynomial complexity cores. Sympos. Math. Foundations Computer Science, MFCS 1984, Lecture Notes in Computer Science 176, Springer 1984, 452-458.
U. Schöning. Robust algorithms: a different approach to oracles. Intern. Colloq. Automata, Languages and Programming, ICALP 1984, Lecture Notes in Computer Science 172, Springer 1984, 448-453.
U. Schöning. Minimal pairs for P. Theor. Comput Sci. 31 (1984) 41-48.
U. Schöning. On small generators. Theor. Comput. Sci. 34 (1984) 337-341.
U. Schöning. Generalized Polynomial-time reducibilities, degrees and NP-completeness. Fundamenta Informaticae VII, 1 (1984) 77-82.
U. Schöning, R.V. Book. Immunity, relativizations, and nondeterminism. SIAM Journal on Computing 13, 2 (1984) 329-337.
J. Balcázar, R. Book, T. Long, U. Schöning, A. Selman. Sparse oracles and uniform complexity classes. 25th Ann. Sympos. on Foundations of Computer Science, FOCS 1984, IEEE, pages 308-311.
U. Schöning. A low and a high hierarchy within NP. Journal of Computer and System Sciences 27,1 (1983) 14-28.
U. Schöning. On the structure of delta-2-p. Information Proc. Letters 16 (1983) 209-211.
U. Schöning, R. V. Book. Immunity. Intern. Colloq. Automata, Languages and Programming, ICALP 1983, Lecture Notes in Computer Science 172, Springer 1983, 448-453.
U. Schöning. A uniform approach to obtain diagonal sets in compexity classes. Theor. Comput. Sci. 18 (1982) 95-103.
U. Schöning. On NP-Decomposable Sets. SIGACT News 14 (1982), 18–20.
U. Schöning. A Note on Complete Sets for the Polynomial-Time Hierarchy. SIGACT News 13 (1981), 30-34.