Institut für Theoretische Informatik
- 1:
Lehre. - 2:
Forschung. - 3:
TheorieTag. - 4:
Mitarbeiter.- 4.1:
Prof. Dr. Uwe Schöning.- 4.1.1:
List of on-line available publications . - 4.1.2:
Buchveröffentlichungen.
- 4.1.1:
- 4.2:
Prof. Dr. Jacobo Torán. - 4.3:
Prof. Dr. Enno Ohlebusch. - 4.4:
Waltraud Fromm. - 4.5:
Dipl.-Phys. Stefan Arnold. - 4.6:
Dipl.-Inf. Adrian Balint. - 4.7:
Dipl.-Inf. Timo Beller. - 4.8:
Dipl.-Inf. Oliver Gableske. - 4.9:
M.Sc.-Bioinf. Dominikus Krüger. - 4.10:
Dipl.-Inf. Adrian Kügel. - 4.11:
Dr. Markus Maucher. - 4.12:
Dipl.-Inf. Thomas Schnattinger. - 4.13:
Dipl.-Inf. Simon Straub. - 4.14:
Dipl.-Inf. Gunnar Völkel. - 4.15:
Ehemalige Mitarbeiter / Doktoranden.
- 4.1:
- 5:
Adresse. - 6:
Intern. - 7:
Impressum.
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))n 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.
