Uwe Schöning

Proceedings of the Complexity and Approximation - In Memory of Ker-I Ko, 2020

2016

Engineering a Lightweight and Efficient Local Search SAT Solver.

[BibT_eX]

[DOI]

Adrian Balint

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.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2014, 2014

Ant colony optimization with group learning.

[BibT_eX]

[DOI]

Proceedings of the Genetic and Evolutionary Computation Conference, 2014

Information Theoretic Measures for Ant Colony Optimization.

[BibT_eX]

[DOI]

Proceedings of the Analysis of Large and Complex Data, 2014

2013

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

[BibT_eX]

[DOI]

Bioinform., 2013

Structural RNA alignment by multi-objective optimization.

[BibT_eX]

[DOI]

Thomas Schnattinger

Hans A. Kestler

Bioinform., 2013

2012

Turings Arbeiten über Berechenbarkeit - eine Einführung und Lesehilfe.

[BibT_eX]

[DOI]

Wolfgang Thomas

Inform. Spektrum, 2012

Choosing Probability Distributions for Stochastic Local Search and the Role of Make versus Break.

[BibT_eX]

[DOI]

Adrian Balint

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2012, 2012

Kryptologie-Kompendium.

[BibT_eX]

[DOI]

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

Das Erfüllbarkeitsproblem SAT - Algorithmen und Analysen.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Markus Maucher

Hans A. Kestler

Comput. Stat., 2011

2010

Das SAT-Problem.

[BibT_eX]

[DOI]

Inform. Spektrum, 2010

Using Stochastic Indexed Grammars for RNA Structure PredictionWith Pseudoknots.

[BibT_eX]

[DOI]

Monika von Knop

Bull. EATCS, 2010

Comparing Two Stochastic Local Search Algorithms for Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2010

Mathe-Toolbox - Mathematische Notationen, Grundbegriffe und Beweismethoden.

[BibT_eX]

[DOI]

Hans A. Kestler

Lehmanns Media, ISBN: 978-3-86541-369-7, 2010

2007

Randomized Algorithms for 3-SAT.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2007

Principles of Stochastic Local Search.

[BibT_eX]

[DOI]

Proceedings of the Unconventional Computation, 6th International Conference, 2007

2006

Smaller superconcentrators of density 28.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2006

A note on the size of Craig Interpolants.

[BibT_eX]

[DOI]

Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

2005

Algorithmics in Exponential Time.

[BibT_eX]

[DOI]

Proceedings of the STACS 2005, 2005

Randomized Quicksort and the Entropy of the Random Source.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

New Algorithmic Paradigms in Exponential Time Algorithms.

[BibT_eX]

[DOI]

Proceedings of the New Computational Paradigms, 2005

Ideen der Informatik - grundlegende Modelle und Konzepte, 2. Auflage.

[BibT_eX]

Christos H. Papadimitriou

Oldenbourg, ISBN: 978-3-486-57833-1, 2005

2004

Randomized Quicksort and the Entropy of the Random Number Generator

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

2002

A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search.

[BibT_eX]

[DOI]

Prabhakar Raghavan

Theor. Comput. Sci., 2002

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

[BibT_eX]

[DOI]

Algorithmica, 2002

A Probabilistic 3-SAT Algorithm Further Improved.

[BibT_eX]

[DOI]

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

Ideen der Informatik: Grundlegende Modelle und Konzepte

[BibT_eX]

Oldenbourg, ISBN: 3-486-25899-0, 2002

2001

New Algorithms for k -SAT Based on the Local Search Principle.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

Algorithmik.

[BibT_eX]

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

2000

Construction of expanders and superconcentrators using Kolmogorov complexity.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2000

Mastering the Master Theorem.

[BibT_eX]

Bull. EATCS, 2000

Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Logik für Informatiker, 5. Auflage.

[BibT_eX]

Spektrum-Hochschultaschenbuch, Spektrum Akadem. Verl., ISBN: 978-3-8274-1005-4, 2000

1999

A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

Gems of theoretical computer science.

[BibT_eX]

Randall Pruim

Springer, ISBN: 978-3-540-64425-5, 1998

1997

Complexity of Presburger Arithmetic with Fixed Quantifier Dimension.

[BibT_eX]

[DOI]

Theory Comput. Syst., 1997

Better Expanders and Superconcentrators by Kolmogorov Complexity.

[BibT_eX]

Proceedings of the SIROCCO'97, 1997

Resolution Proofs, Exponential Bounds, and Kolmogorov Complexity.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

High Sets for NP.

[BibT_eX]

Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

Theoretische Informatik - kurzgefaßt, 3. Auflage.

[BibT_eX]

Hochschultaschenbuch, Spektrum Akademischer Verlag, ISBN: 978-3-8274-0250-9, 1997

Algorithmen - kurz gefasst.

[BibT_eX]

Hochschultaschenbuch, Spektrum Akademischer Verlag, ISBN: 978-3-8274-0232-5, 1997

1995

If NP has Polynomial-Size Circuits, then MA=AM.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1995

Theoretische Informatik kurzgefaßt, 2. Auflage.

[BibT_eX]

Spektrum Akademischer Verlag, ISBN: 978-3-86025-711-1, 1995

Logik für Informatiker, 4. Auflage.

[BibT_eX]

Reihe Informatik, Spektrum Akademischer Verlag, ISBN: 978-3-86025-684-8, 1995

Perlen der theoretischen Informatik - 9 weitere Themen.

[BibT_eX]

Universität, 1995

Perlen der theoretischen Informatik.

[BibT_eX]

BI-Wissenschaftsverlag, ISBN: 978-3-411-17331-0, 1995

1994

Instance Complexity.

[BibT_eX]

[DOI]

J. ACM, 1994

1993

On Random Reductions from Sparse Sets to Tally Sets.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1993

The Graph Isomorphism Problem: Its Structural Complexity

[BibT_eX]

[DOI]

Progress in Theoretical Computer Science, Birkhäuser/Springer, ISBN: 978-1-4612-0333-9, 1993

1992

Logarithmic Advice Classes.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1992

Turing Machines with Few Accepting Computations and Low Sets for PP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1992

Graph Isomorphism is Low for PP.

[BibT_eX]

[DOI]

Comput. Complex., 1992

Reductions to Sets of Low Information Content.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

Theoretische Informatik kurz gefasst.

[BibT_eX]

BI-Wissenschaftsverlag, ISBN: 978-3-411-15641-2, 1992

Logik für Informatiker, 3. Auflage

[BibT_eX]

Reihe Informatik 56, Bibliographisches Institut, ISBN: 3-411-14013-5, 1992

1990

Complexity Cores and Hard Problem Instances.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1990

1989

Probabilistic Complexity Classes and Lowness.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1989

On Counting and Approximation.

[BibT_eX]

[DOI]

Acta Informatica, 1989

Logik für Informatiker, 2. Auflage

[BibT_eX]

Reihe Informatik 56, Bibliographisches Institut, ISBN: 3-411-14012-7, 1989

1988

Graph Isomorphism is in the Low Hierarchy.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1988

Collapsing Oracle Hierarchies, Census Functions and Logarithmically Many Queries.

[BibT_eX]

[DOI]

Klaus W. Wagner

Proceedings of the STACS 88, 1988

Robust Orale Machines.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

The power of counting.

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987

The Difference and Truth-Table Hierarchies for NP.

[BibT_eX]

[DOI]

Klaus W. Wagner

RAIRO Theor. Informatics Appl., 1987

Complexity Cores and Hard-To-Prove Formulas.

[BibT_eX]

[DOI]

Proceedings of the CSL '87, 1987

Logik für Informatiker

[BibT_eX]

Reihe Informatik 56, Bibliographisches Institut, ISBN: 3-411-03164-6, 1987

1986

The Density and Complexity of Polynomial Cores for Intractable Sets.

[BibT_eX]

[DOI]

Inf. Control., July, 1986

Optimal Approximations and Polynomially Levelable Sets.

[BibT_eX]

[DOI]

David A. Russo

SIAM J. Comput., 1986

Sparse Sets, Lowness and Highness.

[BibT_eX]

[DOI]

SIAM J. Comput., 1986

Complete Sets and Closeness to Complexity Classes.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1986

The polynomial-time hierarchy and sparse oracles.

[BibT_eX]

[DOI]

J. ACM, 1986

Lower Bounds by Recursion Theoretic Arguments (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

What Is a Hard Instance of a Computational Problem?.

[BibT_eX]

[DOI]

Proceedings of the Structure in Complexity Theory, 1986

Complexity and Structure

[BibT_eX]

[DOI]

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

1985

Robust Algorithms: A Different Approach to Oracles.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1985

On Bounded Query Machines.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1985

On Circuit-Size Complexity and the Low Hierarchy in NP.

[BibT_eX]

[DOI]

Ker-I Ko

SIAM J. Comput., 1985

Bi-Immune Sets for Complexity Classes.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1985

Polynomial Levelability and Maximal Complexity Cores.

[BibT_eX]

[DOI]

David A. Russo

Proceedings of the Automata, 1985

1984

On Small Generators

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1984

Minimal pairs for P

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1984

Immunity, Relativizations, and Nondeterminism.

[BibT_eX]

[DOI]

SIAM J. Comput., 1984

The Structure of Polynomial Complexity Cores (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

Sparse Oracles, Lowness, and Highness.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

Sparse Oracles and Uniform Complexity Classes

[BibT_eX]

[DOI]

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

A Low and a High Hierarchy within NP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1983

On the Dtructure of Deltap2.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1983

Immunity (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, 1983

1982

A Uniform Approach to Obtain Diagonal Sets in Complexity Classes.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1982

On NP-decomposable sets.

[BibT_eX]

[DOI]

SIGACT News, 1982

1981

A note on complete sets for the polynomial-time hierarchy.

[BibT_eX]

[DOI]

SIGACT News, 1981

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

[BibT_eX]

[DOI]