| 2007 |
|---|
| 70 | EE | Uwe Schöning:
Principles of Stochastic Local Search.
UC 2007: 178-187 |
| 69 | EE | Thomas Hofmeister,
Uwe Schöning,
Rainer Schuler,
Osamu Watanabe:
Randomized Algorithms for 3-SAT.
Theory Comput. Syst. 40(3): 249-262 (2007) |
| 2006 |
|---|
| 68 | EE | Uwe Schöning,
Jacobo Torán:
A note on the size of Craig Interpolants.
Circuits, Logic, and Games 2006 |
| 67 | EE | Uwe Schöning:
Smaller superconcentrators of density 28.
Inf. Process. Lett. 98(4): 127-129 (2006) |
| 2005 |
|---|
| 66 | EE | Beatrice List,
Markus Maucher,
Uwe Schöning,
Rainer Schuler:
Randomized Quicksort and the Entropy of the Random Source.
COCOON 2005: 450-460 |
| 65 | EE | Uwe Schöning:
New Algorithmic Paradigms in Exponential Time Algorithms.
CiE 2005: 429-429 |
| 64 | EE | Uwe Schöning:
Algorithmics in Exponential Time.
STACS 2005: 36-43 |
| 2004 |
|---|
| 63 | EE | Beatrice List,
Markus Maucher,
Uwe Schöning,
Rainer Schuler:
Randomized QuickSort and the Entropy of the Random Source.
Algebraic Methods in Computational Complexity 2004 |
| 62 | EE | 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) |
| 2002 |
|---|
| 61 | | Uwe Schöning:
Ideen der Informatik: Grundlegende Modelle und Konzepte
Oldenbourg 2002 |
| 60 | EE | Thomas Hofmeister,
Uwe Schöning,
Rainer Schuler,
Osamu Watanabe:
A Probabilistic 3-SAT Algorithm Further Improved.
STACS 2002: 192-202 |
| 59 | EE | Uwe Schöning:
A Probabilistic Algorithm for k -SAT Based on Limited Local Search and Restart.
Algorithmica 32(4): 615-623 (2002) |
| 58 | | 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))n algorithm for k-SAT based on local search.
Theor. Comput. Sci. 289(1): 69-83 (2002) |
| 2001 |
|---|
| 57 | EE | Uwe Schöning:
New Algorithms for k -SAT Based on the Local Search Principle.
MFCS 2001: 87-95 |
| 2000 |
|---|
| 56 | EE | 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 |
| 55 | | Uwe Schöning:
Mastering the Master Theorem.
Bulletin of the EATCS 71: 165-166 (2000) |
| 54 | | Uwe Schöning:
Construction of expanders and superconcentrators using Kolmogorov complexity.
Random Struct. Algorithms 17(1): 64-77 (2000) |
| 1999 |
|---|
| 53 | EE | Uwe Schöning:
A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems.
FOCS 1999: 410-414 |
| 1997 |
|---|
| 52 | | Johannes Köbler,
Uwe Schöning:
High Sets for NP.
Advances in Algorithms, Languages, and Complexity 1997: 139-156 |
| 51 | | Uwe Schöning:
Resolution Proofs, Exponential Bounds, and Kolmogorov Complexity.
MFCS 1997: 110-116 |
| 50 | | Uwe Schöning:
Better Expanders and Superconcentrators by Kolmogorov Complexity.
SIROCCO 1997: 138-150 |
| 49 | | Uwe Schöning:
Complexity of Presburger Arithmetic with Fixed Quantifier Dimension.
Theory Comput. Syst. 30(4): 423-428 (1997) |
| 1995 |
|---|
| 48 | EE | 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) |
| 1994 |
|---|
| 47 | EE | Pekka Orponen,
Ker-I Ko,
Uwe Schöning,
Osamu Watanabe:
Instance Complexity.
J. ACM 41(1): 96-121 (1994) |
| 1993 |
|---|
| 46 | | Klaus Ambos-Spies,
Steven Homer,
Uwe Schöning:
Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8, 1992
Cambridge University Press 1993 |
| 45 | | Uwe Schöning:
On Random Reductions from Sparse Sets to Tally Sets.
Inf. Process. Lett. 46(5): 239-241 (1993) |
| 1992 |
|---|
| 44 | | Uwe Schöning:
Logik für Informatiker, 3. Auflage
Bibliographisches Institut 1992 |
| 43 | | 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 |
| 42 | | 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 |
| 41 | | Johannes Köbler,
Uwe Schöning,
Jacobo Torán:
Graph Isomorphism is Low for PP.
STACS 1992: 401-411 |
| 40 | | Johannes Köbler,
Uwe Schöning,
Jacobo Torán:
Graph Isomorphism is Low for PP.
Computational Complexity 2: 301-330 (1992) |
| 39 | | 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) |
| 38 | | José L. Balcázar,
Uwe Schöning:
Logarithmic Advice Classes.
Theor. Comput. Sci. 99(2): 279-290 (1992) |
| 1990 |
|---|
| 37 | | Uwe Schöning:
Complexity Cores and Hard Problem Instances.
SIGAL International Symposium on Algorithms 1990: 232-240 |
| 1989 |
|---|
| 36 | | Uwe Schöning:
Logik für Informatiker, 2. Auflage
Bibliographisches Institut 1989 |
| 35 | | 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 |
| 34 | | Johannes Köbler,
Uwe Schöning,
Jacobo Torán:
On Counting and Approximation.
Acta Inf. 26(4): 363-379 (1989) |
| 33 | | Uwe Schöning:
Probabilistic Complexity Classes and Lowness.
J. Comput. Syst. Sci. 39(1): 84-100 (1989) |
| 1988 |
|---|
| 32 | | Johannes Köbler,
Uwe Schöning,
Jacobo Torán:
On Counting and Approximation.
CAAP 1988: 40-51 |
| 31 | | Uwe Schöning:
Robust Orale Machines.
MFCS 1988: 93-106 |
| 30 | | Uwe Schöning,
Klaus W. Wagner:
Collapsing Oracle Hierarchies, Census Functions and Logarithmically Many Queries.
STACS 1988: 91-97 |
| 29 | | Uwe Schöning:
Graph Isomorphism is in the Low Hierarchy.
J. Comput. Syst. Sci. 37(3): 312-323 (1988) |
| 1987 |
|---|
| 28 | | Uwe Schöning:
Logik für Informatiker
Bibliographisches Institut 1987 |
| 27 | | Uwe Schöning:
Complexity Cores and Hard-To-Prove Formulas.
CSL 1987: 273-280 |
| 26 | | Uwe Schöning:
Graph Isomorphism is in the Low Hierarchy.
STACS 1987: 114-124 |
| 25 | | Johannes Köbler,
Uwe Schöning,
Klaus W. Wagner:
The Difference and Truth-Table Hierarchies for NP.
ITA 21(4): 419-435 (1987) |
| 1986 |
|---|
| 24 | | Uwe Schöning:
Complexity and Structure
Springer 1986 |
| 23 | | Uwe Schöning:
Lower Bounds by Recursion Theoretic Arguments (Extended Abstract).
ICALP 1986: 370-375 |
| 22 | | 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 |
| 21 | | Pekka Orponen,
Uwe Schöning:
The Density and Complexity of Polynomial Cores for Intractable
Information and Control 70(1): 54-68 (1986) |
| 20 | EE | José L. Balcázar,
Ronald V. Book,
Uwe Schöning:
The polynomial-time hierarchy and sparse oracles.
J. ACM 33(3): 603-617 (1986) |
| 19 | | Uwe Schöning:
Complete Sets and Closeness to Complexity Classes.
Mathematical Systems Theory 19(1): 29-41 (1986) |
| 18 | | Pekka Orponen,
David A. Russo,
Uwe Schöning:
Optimal Approximations and Polynomially Levelable Sets.
SIAM J. Comput. 15(2): 399-408 (1986) |
| 17 | | José L. Balcázar,
Ronald V. Book,
Uwe Schöning:
Sparse Sets, Lowness and Highness.
SIAM J. Comput. 15(3): 739-747 (1986) |
| 1985 |
|---|
| 16 | | Pekka Orponen,
David A. Russo,
Uwe Schöning:
Polynomial Levelability and Maximal Complexity Cores.
ICALP 1985: 435-444 |
| 15 | | José L. Balcázar,
Uwe Schöning:
Bi-Immune Sets for Complexity Classes.
Mathematical Systems Theory 18(1): 1-10 (1985) |
| 14 | | Ker-I Ko,
Uwe Schöning:
On Circuit-Size Complexity and the Low Hierarchy in NP.
SIAM J. Comput. 14(1): 41-51 (1985) |
| 13 | | José L. Balcázar,
Ronald V. Book,
Uwe Schöning:
On Bounded Query Machines.
Theor. Comput. Sci. 40: 237-243 (1985) |
| 12 | | Uwe Schöning:
Robust Algorithms: A Different Approach to Oracles.
Theor. Comput. Sci. 40: 57-66 (1985) |
| 1984 |
|---|
| 11 | | 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 |
| 10 | | Uwe Schöning:
Robust Algorithms: A Different Approach to Oracles.
ICALP 1984: 448-453 |
| 9 | | José L. Balcázar,
Ronald V. Book,
Uwe Schöning:
Sparse Oracles, Lowness, and Highness.
MFCS 1984: 185-193 |
| 8 | | Pekka Orponen,
Uwe Schöning:
The Structure of Polynomial Complexity Cores (Extended Abstract).
MFCS 1984: 452-458 |
| 7 | | Uwe Schöning,
Ronald V. Book:
Immunity, Relativizations, and Nondeterminism.
SIAM J. Comput. 13(2): 329-337 (1984) |
| 6 | | Uwe Schöning:
Minimal pairs for P
Theor. Comput. Sci. 31: 41-48 (1984) |
| 5 | | Uwe Schöning:
On Small Generators
Theor. Comput. Sci. 34(3): 337-341 (1984) |
| 1983 |
|---|
| 4 | | Uwe Schöning,
Ronald V. Book:
Immunity (Extended Abstract).
ICALP 1983: 653-661 |
| 3 | | Uwe Schöning:
On the Dtructure of Deltap2.
Inf. Process. Lett. 16(4): 209-211 (1983) |
| 2 | | Uwe Schöning:
A Low and a High Hierarchy within NP.
J. Comput. Syst. Sci. 27(1): 14-28 (1983) |
| 1982 |
|---|
| 1 | | Uwe Schöning:
A Uniform Approach to Obtain Diagonal Sets in Complexity Classes.
Theor. Comput. Sci. 18: 95-103 (1982) |
