Uwe Schöning

Uwe Schöning, Jacobo Torán: Das Erfüllbarkeitsproblem SAT - Algorithmen und Analysen. Mathematik für Anwendungen 1, Lehmann 2012, isbn 978-3-86541-473-1, pp. 1-187

Uwe Schöning, Wolfgang Thomas: Turings Arbeiten über Berechenbarkeit - eine Einführung und Lesehilfe. Informatik Spektrum 35(4): 253-260 (2012)

Adrian Balint, Uwe Schöning: Choosing Probability Distributions for Stochastic Local Search and the Role of Make versus Break. SAT 2012: 16-29

Uwe Schöning, Hans A. Kestler: Mathe-Toolbox - Mathematische Notationen, Grundbegriffe und Beweismethoden. Lehmanns Media 2010, isbn 978-3-86541-369-7, pp. 1-143

Uwe Schöning, Monika von Knop: Using Stochastic Indexed Grammars for RNA Structure PredictionWith Pseudoknots. Bulletin of the EATCS 101: 185-188 (2010)

Uwe Schöning: Das SAT-Problem. Informatik Spektrum 33(5): 479-483 (2010)

Uwe Schöning: Comparing Two Stochastic Local Search Algorithms for Constraint Satisfaction Problems. CSR 2010: 344-349

Thomas Hofmeister, Uwe Schöning, Rainer Schuler, Osamu Watanabe: Randomized Algorithms for 3-SAT. Theory Comput. Syst. 40(3): 249-262 (2007)

Uwe Schöning: Principles of Stochastic Local Search. UC 2007: 178-187

Uwe Schöning: Smaller superconcentrators of density 28. Inf. Process. Lett. 98(4): 127-129 (2006)

Uwe Schöning, Jacobo Torán: A note on the size of Craig Interpolants. Circuits, Logic, and Games 2006

Uwe Schöning: Ideen der Informatik - grundlegende Modelle und Konzepte (2. Aufl.). Oldenbourg 2005, isbn 978-3-486-57833-1, pp. I-X, 1-260

Uwe Schöning: New Algorithmic Paradigms in Exponential Time Algorithms. CiE 2005: 429-429

Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler: Randomized Quicksort and the Entropy of the Random Source. COCOON 2005: 450-460

Uwe Schöning: Algorithmics in Exponential Time. STACS 2005: 36-43

Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler: Randomized QuickSort and the Entropy of the Random Source. Algebraic Methods in Computational Complexity 2004

Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler: Randomized Quicksort and the Entropy of the Random Number Generator. Electronic Colloquium on Computational Complexity (ECCC)(059) (2004)

Uwe Schöning: Ideen der Informatik: Grundlegende Modelle und Konzepte. Oldenbourg 2002, isbn 3-486-25899-0

Uwe Schöning: A Probabilistic Algorithm for k -SAT Based on Limited Local Search and Restart. Algorithmica 32(4): 615-623 (2002)

Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning: A deterministic (2-2/(k+1))ⁿ algorithm for k-SAT based on local search. Theor. Comput. Sci. 289(1): 69-83 (2002)

Thomas Hofmeister, Uwe Schöning, Rainer Schuler, Osamu Watanabe: A Probabilistic 3-SAT Algorithm Further Improved. STACS 2002: 192-202

Uwe Schöning: Algorithmik. Spektrum Akadem. Verl. 2001, isbn 978-3-8274-1092-4, pp. 1-384

Uwe Schöning: New Algorithms for k -SAT Based on the Local Search Principle. MFCS 2001: 87-95

Uwe Schöning: Mastering the Master Theorem. Bulletin of the EATCS 71: 165-166 (2000)

Uwe Schöning: Construction of expanders and superconcentrators using Kolmogorov complexity. Random Struct. Algorithms 17(1): 64-77 (2000)

Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning: Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search. ICALP 2000: 236-247

Uwe Schöning: A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems. FOCS 1999: 410-414

Uwe Schöning, Randall Pruim: Gems of theoretical computer science. Springer 1998, isbn 978-3-540-64425-5, pp. I-X, 1-320

Uwe Schöning: Algorithmen - kurz gefasst. Hochschultaschenbuch, Spektrum Akademischer Verlag 1997, isbn 978-3-8274-0232-5, pp. 1-221

Uwe Schöning: Theoretische Informatik - kurzgefaßt (3. Aufl.). Hochschultaschenbuch, Spektrum Akademischer Verlag 1997, isbn 978-3-8274-0250-9, pp. 1-196

Uwe Schöning: Complexity of Presburger Arithmetic with Fixed Quantifier Dimension. Theory Comput. Syst. 30(4): 423-428 (1997)

Johannes Köbler, Uwe Schöning: High Sets for NP. Advances in Algorithms, Languages, and Complexity 1997: 139-156

Uwe Schöning: Resolution Proofs, Exponential Bounds, and Kolmogorov Complexity. MFCS 1997: 110-116

Uwe Schöning: Better Expanders and Superconcentrators by Kolmogorov Complexity. SIROCCO 1997: 138-150

Uwe Schöning: Perlen der theoretischen Informatik. BI-Wissenschaftsverlag 1995, isbn 978-3-411-17331-0, pp. 1-332

Uwe Schöning: Perlen der theoretischen Informatik - 9 weitere Themen. Universität 1995, pp. 1-58

Uwe Schöning: Logik für Informatiker (4. Aufl.). Reihe Informatik, Spektrum Akademischer Verlag 1995, isbn 978-3-86025-684-8, pp. 1-207

Uwe Schöning: Theoretische Informatik kurzgefaßt (2. Aufl.). Spektrum Akademischer Verlag 1995, isbn 978-3-86025-711-1, pp. 1-188

Vikraman Arvind, Johannes Köbler, Uwe Schöning, Rainer Schuler: If NP has Polynomial-Size Circuits, then MA=AM. Theor. Comput. Sci. 137(2): 279-282 (1995)

Pekka Orponen, Ker-I Ko, Uwe Schöning, Osamu Watanabe: Instance Complexity. J. ACM 41(1): 96-121 (1994)

Uwe Schöning: On Random Reductions from Sparse Sets to Tally Sets. Inf. Process. Lett. 46(5): 239-241 (1993)

Klaus Ambos-Spies, Steven Homer, Uwe Schöning (Eds.): Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8, 1992. Cambridge University Press 1993, isbn 0-521-44220-6

Uwe Schöning: Logik für Informatiker, 3. Auflage. Reihe Informatik 56, Bibliographisches Institut 1992, isbn 3-411-14013-5

Uwe Schöning: Theoretische Informatik kurz gefasst. BI-Wissenschaftsverlag 1992, isbn 978-3-411-15641-2, pp. 1-188

Johannes Köbler, Uwe Schöning, Jacobo Torán: Graph Isomorphism is Low for PP. Computational Complexity 2: 301-330 (1992)

Johannes Köbler, Uwe Schöning, Seinosuke Toda, Jacobo Torán: Turing Machines with Few Accepting Computations and Low Sets for PP. J. Comput. Syst. Sci. 44(2): 272-286 (1992)

José L. Balcázar, Uwe Schöning: Logarithmic Advice Classes. Theor. Comput. Sci. 99(2): 279-290 (1992)

Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf: Reductions to Sets of Low Information Content. Complexity Theory: Current Research 1992: 1-46

Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf: Reductions to Sets of Low Information Content. ICALP 1992: 162-173

Johannes Köbler, Uwe Schöning, Jacobo Torán: Graph Isomorphism is Low for PP. STACS 1992: 401-411

Uwe Schöning: Complexity Cores and Hard Problem Instances. SIGAL International Symposium on Algorithms 1990: 232-240

Uwe Schöning: Logik für Informatiker, 2. Auflage. Reihe Informatik 56, Bibliographisches Institut 1989, isbn 3-411-14012-7

Johannes Köbler, Uwe Schöning, Jacobo Torán: On Counting and Approximation. Acta Inf. 26(4): 363-379 (1989)

Uwe Schöning: Probabilistic Complexity Classes and Lowness. J. Comput. Syst. Sci. 39(1): 84-100 (1989)

Johannes Köbler, Uwe Schöning, Seinosuke Toda, Jacobo Torán: Turing Machines with few Accepting Computations and low Sets for PP. Structure in Complexity Theory Conference 1989: 208-215

Uwe Schöning: Graph Isomorphism is in the Low Hierarchy. J. Comput. Syst. Sci. 37(3): 312-323 (1988)

Johannes Köbler, Uwe Schöning, Jacobo Torán: On Counting and Approximation. CAAP 1988: 40-51

Uwe Schöning: The power of counting. Structure in Complexity Theory Conference 1988: 2-9

Uwe Schöning: Robust Orale Machines. MFCS 1988: 93-106

Uwe Schöning, Klaus W. Wagner: Collapsing Oracle Hierarchies, Census Functions and Logarithmically Many Queries. STACS 1988: 91-97

Uwe Schöning: Logik für Informatiker. Reihe Informatik 56, Bibliographisches Institut 1987, isbn 3-411-03164-6

Johannes Köbler, Uwe Schöning, Klaus W. Wagner: The Difference and Truth-Table Hierarchies for NP. ITA 21(4): 419-435 (1987)

Uwe Schöning: Lowness and probabilistic complexity classes. Structure in Complexity Theory Conference 1987

Uwe Schöning: Complexity Cores and Hard-To-Prove Formulas. CSL 1987: 273-280

Uwe Schöning: Graph Isomorphism is in the Low Hierarchy. STACS 1987: 114-124

Uwe Schöning: Complexity and Structure. Lecture Notes in Computer Science 211, Springer 1986, isbn 3-540-16079-5

Pekka Orponen, Uwe Schöning: The Density and Complexity of Polynomial Cores for Intractable Sets. Information and Control 70(1): 54-68 (1986)

José L. Balcázar, Ronald V. Book, Uwe Schöning: The polynomial-time hierarchy and sparse oracles. J. ACM 33(3): 603-617 (1986)

Uwe Schöning: Complete Sets and Closeness to Complexity Classes. Mathematical Systems Theory 19(1): 29-41 (1986)

Pekka Orponen, David A. Russo, Uwe Schöning: Optimal Approximations and Polynomially Levelable Sets. SIAM J. Comput. 15(2): 399-408 (1986)

José L. Balcázar, Ronald V. Book, Uwe Schöning: Sparse Sets, Lowness and Highness. SIAM J. Comput. 15(3): 739-747 (1986)

Ker-I Ko, Pekka Orponen, Uwe Schöning, Osamu Watanabe: What Is a Hard Instance of a Computational Problem?. Structure in Complexity Theory Conference 1986: 197-217

Uwe Schöning: Lower Bounds by Recursion Theoretic Arguments (Extended Abstract). ICALP 1986: 370-375

José L. Balcázar, Uwe Schöning: Bi-Immune Sets for Complexity Classes. Mathematical Systems Theory 18(1): 1-10 (1985)

Ker-I Ko, Uwe Schöning: On Circuit-Size Complexity and the Low Hierarchy in NP. SIAM J. Comput. 14(1): 41-51 (1985)

Uwe Schöning: Robust Algorithms: A Different Approach to Oracles. Theor. Comput. Sci. 40: 57-66 (1985)

José L. Balcázar, Ronald V. Book, Uwe Schöning: On Bounded Query Machines. Theor. Comput. Sci. 40: 237-243 (1985)

Pekka Orponen, David A. Russo, Uwe Schöning: Polynomial Levelability and Maximal Complexity Cores. ICALP 1985: 435-444

Uwe Schöning, Ronald V. Book: Immunity, Relativizations, and Nondeterminism. SIAM J. Comput. 13(2): 329-337 (1984)

Uwe Schöning: Minimal pairs for P. Theor. Comput. Sci. 31: 41-48 (1984)

Uwe Schöning: On Small Generators. Theor. Comput. Sci. 34(3): 337-341 (1984)

José L. Balcázar, Ronald V. Book, Timothy J. Long, Uwe Schöning, Alan L. Selman: Sparse Oracles and Uniform Complexity Classes. FOCS 1984: 308-311

Uwe Schöning: Robust Algorithms: A Different Approach to Oracles. ICALP 1984: 448-453

José L. Balcázar, Ronald V. Book, Uwe Schöning: Sparse Oracles, Lowness, and Highness. MFCS 1984: 185-193

Pekka Orponen, Uwe Schöning: The Structure of Polynomial Complexity Cores (Extended Abstract). MFCS 1984: 452-458

Uwe Schöning: On the Dtructure of Delta^p₂. Inf. Process. Lett. 16(4): 209-211 (1983)

Uwe Schöning: A Low and a High Hierarchy within NP. J. Comput. Syst. Sci. 27(1): 14-28 (1983)

Uwe Schöning, Ronald V. Book: Immunity (Extended Abstract). ICALP 1983: 653-661

Uwe Schöning: A Uniform Approach to Obtain Diagonal Sets in Complexity Classes. Theor. Comput. Sci. 18: 95-103 (1982)

Uwe Schöning: Untersuchungen zur Struktur von NP und verwandten Komplexitätsklassen mit Hilfe verschiedener polynomieller Reduktionen. Universität Stuttgart 1981, pp. 1-78