Uwe Schöning

Affiliations:
  • University of Ulm, Institute for Theoretical Informatics, Germany
  • University of Stuttgart, Germany (PhD 1981)


According to our database1, Uwe Schöning authored at least 94 papers between 1981 and 2020.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2020
Promise Problems on Probability Distributions.
Proceedings of the Complexity and Approximation - In Memory of Ker-I Ko, 2020

2016
Engineering a Lightweight and Efficient Local Search SAT Solver.
Proceedings of the Algorithm Engineering - Selected Results and Surveys, 2016

2014
Improving Implementation of SLS Solvers for SAT and New Heuristics for k-SAT with Long Clauses.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2014, 2014

Ant colony optimization with group learning.
Proceedings of the Genetic and Evolutionary Computation Conference, 2014

Information Theoretic Measures for Ant Colony Optimization.
Proceedings of the Analysis of Large and Complex Data, 2014

2013
RNA-Pareto: interactive analysis of Pareto-optimal RNA sequence-structure alignments.
Bioinform., 2013

Structural RNA alignment by multi-objective optimization.
Bioinform., 2013

2012
Turings Arbeiten über Berechenbarkeit - eine Einführung und Lesehilfe.
Inform. Spektrum, 2012

Choosing Probability Distributions for Stochastic Local Search and the Role of Make versus Break.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2012, 2012

Kryptologie-Kompendium.
Mathematik für Anwendungen 2, Lehmanns Media, ISBN: 978-3-86541-515-8, 2012

Das Erfüllbarkeitsproblem SAT - Algorithmen und Analysen.
Mathematik für Anwendungen 1, Lehmann, ISBN: 978-3-86541-473-1, 2012

2011
Search heuristics and the influence of non-perfect randomness: examining Genetic Algorithms and Simulated Annealing.
Comput. Stat., 2011

2010
Das SAT-Problem.
Inform. Spektrum, 2010

Using Stochastic Indexed Grammars for RNA Structure PredictionWith Pseudoknots.
Bull. EATCS, 2010

Comparing Two Stochastic Local Search Algorithms for Constraint Satisfaction Problems.
Proceedings of the Computer Science, 2010

Mathe-Toolbox - Mathematische Notationen, Grundbegriffe und Beweismethoden.
Lehmanns Media, ISBN: 978-3-86541-369-7, 2010

2007
Randomized Algorithms for 3-SAT.
Theory Comput. Syst., 2007

Principles of Stochastic Local Search.
Proceedings of the Unconventional Computation, 6th International Conference, 2007

2006
Smaller superconcentrators of density 28.
Inf. Process. Lett., 2006

A note on the size of Craig Interpolants.
Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

2005
Algorithmics in Exponential Time.
Proceedings of the STACS 2005, 2005

Randomized Quicksort and the Entropy of the Random Source.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

New Algorithmic Paradigms in Exponential Time Algorithms.
Proceedings of the New Computational Paradigms, 2005

Ideen der Informatik - grundlegende Modelle und Konzepte, 2. Auflage.
Oldenbourg, ISBN: 978-3-486-57833-1, 2005

2004
Randomized Quicksort and the Entropy of the Random Number Generator
Electron. Colloquium Comput. Complex., 2004

2002
A deterministic (2-2/(k+1))<sup>n</sup> algorithm for k-SAT based on local search.
Theor. Comput. Sci., 2002

A Probabilistic Algorithm for k -SAT Based on Limited Local Search and Restart.
Algorithmica, 2002

A Probabilistic 3-SAT Algorithm Further Improved.
Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

Ideen der Informatik: Grundlegende Modelle und Konzepte
Oldenbourg, ISBN: 3-486-25899-0, 2002

2001
New Algorithms for k -SAT Based on the Local Search Principle.
Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

Algorithmik.
Spektrum Akadem. Verl., ISBN: 978-3-8274-1092-4, 2001

2000
Construction of expanders and superconcentrators using Kolmogorov complexity.
Random Struct. Algorithms, 2000

Mastering the Master Theorem.
Bull. EATCS, 2000

Deterministic Algorithms for <i>k</i>-SAT Based on Covering Codes and Local Search.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Logik für Informatiker, 5. Auflage.
Spektrum-Hochschultaschenbuch, Spektrum Akadem. Verl., ISBN: 978-3-8274-1005-4, 2000

1999
A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
Gems of theoretical computer science.
Springer, ISBN: 978-3-540-64425-5, 1998

1997
Complexity of Presburger Arithmetic with Fixed Quantifier Dimension.
Theory Comput. Syst., 1997

Better Expanders and Superconcentrators by Kolmogorov Complexity.
Proceedings of the SIROCCO'97, 1997

Resolution Proofs, Exponential Bounds, and Kolmogorov Complexity.
Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

High Sets for NP.
Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

Theoretische Informatik - kurzgefaßt, 3. Auflage.
Hochschultaschenbuch, Spektrum Akademischer Verlag, ISBN: 978-3-8274-0250-9, 1997

Algorithmen - kurz gefasst.
Hochschultaschenbuch, Spektrum Akademischer Verlag, ISBN: 978-3-8274-0232-5, 1997

1995
If NP has Polynomial-Size Circuits, then MA=AM.
Theor. Comput. Sci., 1995

Theoretische Informatik kurzgefaßt, 2. Auflage.
Spektrum Akademischer Verlag, ISBN: 978-3-86025-711-1, 1995

Logik für Informatiker, 4. Auflage.
Reihe Informatik, Spektrum Akademischer Verlag, ISBN: 978-3-86025-684-8, 1995

Perlen der theoretischen Informatik - 9 weitere Themen.
Universität, 1995

Perlen der theoretischen Informatik.
BI-Wissenschaftsverlag, ISBN: 978-3-411-17331-0, 1995

1994
Instance Complexity.
J. ACM, 1994

1993
On Random Reductions from Sparse Sets to Tally Sets.
Inf. Process. Lett., 1993

The Graph Isomorphism Problem: Its Structural Complexity
Progress in Theoretical Computer Science, Birkhäuser/Springer, ISBN: 978-1-4612-0333-9, 1993

1992
Logarithmic Advice Classes.
Theor. Comput. Sci., 1992

Turing Machines with Few Accepting Computations and Low Sets for PP.
J. Comput. Syst. Sci., 1992

Graph Isomorphism is Low for PP.
Comput. Complex., 1992

Reductions to Sets of Low Information Content.
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

Theoretische Informatik kurz gefasst.
BI-Wissenschaftsverlag, ISBN: 978-3-411-15641-2, 1992

Logik für Informatiker, 3. Auflage
Reihe Informatik 56, Bibliographisches Institut, ISBN: 3-411-14013-5, 1992

1990
Complexity Cores and Hard Problem Instances.
Proceedings of the Algorithms, 1990

1989
Probabilistic Complexity Classes and Lowness.
J. Comput. Syst. Sci., 1989

On Counting and Approximation.
Acta Informatica, 1989

Logik für Informatiker, 2. Auflage
Reihe Informatik 56, Bibliographisches Institut, ISBN: 3-411-14012-7, 1989

1988
Graph Isomorphism is in the Low Hierarchy.
J. Comput. Syst. Sci., 1988

Collapsing Oracle Hierarchies, Census Functions and Logarithmically Many Queries.
Proceedings of the STACS 88, 1988

Robust Orale Machines.
Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

The power of counting.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987
The Difference and Truth-Table Hierarchies for NP.
RAIRO Theor. Informatics Appl., 1987

Complexity Cores and Hard-To-Prove Formulas.
Proceedings of the CSL '87, 1987

Logik für Informatiker
Reihe Informatik 56, Bibliographisches Institut, ISBN: 3-411-03164-6, 1987

1986
The Density and Complexity of Polynomial Cores for Intractable Sets.
Inf. Control., July, 1986

Optimal Approximations and Polynomially Levelable Sets.
SIAM J. Comput., 1986

Sparse Sets, Lowness and Highness.
SIAM J. Comput., 1986

Complete Sets and Closeness to Complexity Classes.
Math. Syst. Theory, 1986

The polynomial-time hierarchy and sparse oracles.
J. ACM, 1986

Lower Bounds by Recursion Theoretic Arguments (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

What Is a Hard Instance of a Computational Problem?.
Proceedings of the Structure in Complexity Theory, 1986

Complexity and Structure
Lecture Notes in Computer Science 211, Springer, ISBN: 3-540-16079-5, 1986

1985
Robust Algorithms: A Different Approach to Oracles.
Theor. Comput. Sci., 1985

On Bounded Query Machines.
Theor. Comput. Sci., 1985

On Circuit-Size Complexity and the Low Hierarchy in NP.
SIAM J. Comput., 1985

Bi-Immune Sets for Complexity Classes.
Math. Syst. Theory, 1985

Polynomial Levelability and Maximal Complexity Cores.
Proceedings of the Automata, 1985

1984
On Small Generators
Theor. Comput. Sci., 1984

Minimal pairs for P
Theor. Comput. Sci., 1984

Immunity, Relativizations, and Nondeterminism.
SIAM J. Comput., 1984

The Structure of Polynomial Complexity Cores (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

Sparse Oracles, Lowness, and Highness.
Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

Sparse Oracles and Uniform Complexity Classes
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
A Low and a High Hierarchy within NP.
J. Comput. Syst. Sci., 1983

On the Dtructure of Delta<sup>p</sup><sub>2</sub>.
Inf. Process. Lett., 1983

Immunity (Extended Abstract).
Proceedings of the Automata, 1983

1982
A Uniform Approach to Obtain Diagonal Sets in Complexity Classes.
Theor. Comput. Sci., 1982

On NP-decomposable sets.
SIGACT News, 1982

1981
A note on complete sets for the polynomial-time hierarchy.
SIGACT News, 1981

Untersuchungen zur Struktur von NP und verwandten Komplexitätsklassen mit Hilfe verschiedener polynomieller Reduktionen.
PhD thesis, 1981


  Loading...