Christian Glaßer

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

The Complexity of Computing Second Solutions.

[BibT_eX]

[DOI]

Fynn Godau

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

2024

Oracle without Optimal Proof Systems outside Nondeterministic Subexponential Time.

[BibT_eX]

[DOI]

CoRR, 2024

An Oracle with no UP-Complete Sets, but NP = PSPACE.

[BibT_eX]

[DOI]

David Dingel

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

2023

Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP.

[BibT_eX]

[DOI]

Martin G. Herold

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

2022

Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP.

[BibT_eX]

[DOI]

Anton Ehrmanntraut

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

2020

NP-Completeness, Proof Systems, and Disjoint NP-Pairs.

[BibT_eX]

[DOI]

Titus Dose

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

2017

Emptiness Problems for Integer Circuits.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Introduction to Autoreducibility and Mitoticity.

[BibT_eX]

[DOI]

Proceedings of the Computability and Complexity, 2017

2016

Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic.

[BibT_eX]

[DOI]

Peter Jonsson

Barnaby Martin

Proceedings of the Pursuit of the Universal - 12th Conference on Computability in Europe, 2016

2015

Constraint Satisfaction Problems around Skolem Arithmetic.

[BibT_eX]

[DOI]

Peter Jonsson

Barnaby Martin

CoRR, 2015

2014

Disjoint NP-Pairs and Propositional Proof Systems.

[BibT_eX]

[DOI]

SIGACT News, 2014

Perfect correspondences between dot-depth and polynomial-time hierarchies.

[BibT_eX]

[DOI]

Klaus W. Wagner

J. Comput. Syst. Sci., 2014

Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013

Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions.

[BibT_eX]

[DOI]

Dung T. Nguyen

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Structural Complexity of Multiobjective NP Search Problems.

[BibT_eX]

[DOI]

Krzysztof Fleszar

Fabian Lipp

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

2011

The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions.

[BibT_eX]

[DOI]

Krzysztof Fleszar

Fabian Lipp

Electron. Colloquium Comput. Complex., 2011

Applications of Discrepancy Theory in Multiobjective Approximation.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

Unions of Disjoint NP-Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

2010

Hardness and Approximability in Multi-Objective Optimization.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Balanced Combinations of Solutions in Multi-Objective Optimization

[BibT_eX]

[DOI]

CoRR, 2010

10501 Executive Summary - Advances and Applications of Automata on Words and Trees.

[BibT_eX]

[DOI]

Proceedings of the Advances and Applications of Automata on Words and Trees, 12.12., 2010

10501 Abstracts Collection - Advances and Applications of Automata on Words and Trees.

[BibT_eX]

[DOI]

Proceedings of the Advances and Applications of Automata on Words and Trees, 12.12., 2010

Approximability and Hardness in Multi-objective Optimization.

[BibT_eX]

[DOI]

Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010

2009

Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

The Fault Tolerance of NP-Hard Problems.

[BibT_eX]

[DOI]

Aduri Pavan

Proceedings of the Language and Automata Theory and Applications, 2009

2008

Splitting NP-Complete Sets.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages.

[BibT_eX]

[DOI]

Victor L. Selivanov

Proceedings of the STACS 2008, 2008

Multiobjective Disk Cover Admits a PTAS.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

Space-Efficient Informational Redundancy.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

The Shrinking Property for NP and coNP.

[BibT_eX]

[DOI]

Victor L. Selivanov

Proceedings of the Logic and Theory of Algorithms, 2008

2007

Languages polylog-time reducible to dot-depth 1/2.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2007

The Complexity of Unions of Disjoint Sets.

[BibT_eX]

[DOI]

Proceedings of the STACS 2007, 2007

Non-mitotic Sets.

[BibT_eX]

[DOI]

Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

Satisfiability of Algebraic Circuits over Sets of Natural Numbers.

[BibT_eX]

[DOI]

Matthias Waldherr

Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

Equivalence Problems for Circuits over Sets of Natural Numbers.

[BibT_eX]

[DOI]

Katrin Herr

Matthias Waldherr

Proceedings of the Computer Science, 2007

The Informational Content of Canonical Disjoint NP-Pairs.

[BibT_eX]

[DOI]

Liyu Zhang

Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006

Mitosis in Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 2006

Redundancy in Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the STACS 2006, 2006

Machines that Can Output Empty Words.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy.

[BibT_eX]

[DOI]

Klaus W. Wagner

Proceedings of the Developments in Language Theory, 10th International Conference, 2006

Survey of Disjoint NP-pairs and Relations to Propositional Proof Systems.

[BibT_eX]

[DOI]

Liyu Zhang

Proceedings of the Theoretical Computer Science, 2006

2005

A Reducibility that Corresponds to Unbalanced Leaf-Language Classes

[BibT_eX]

[DOI]

Klaus W. Wagner

Electron. Colloquium Comput. Complex., 2005

Polylog-Time Reductions Decrease Dot-Depth.

[BibT_eX]

[DOI]

Proceedings of the STACS 2005, 2005

Canonical Disjoint NP-Pairs of Propositional Proof Systems.

[BibT_eX]

[DOI]

Liyu Zhang

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

Autoreducibility, Mitoticity, and Immunity.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

2004

Counting with Counterfree Automata

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

A Protocol for Serializing Unique Strategies.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Generation Problems.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Reductions between Disjoint NP-Pairs.

[BibT_eX]

[DOI]

Samik Sengupta

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

Properties of NP-Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Relativizing Function Classes.

[BibT_eX]

[DOI]

Gerd Wechsung

J. Univers. Comput. Sci., 2003

Small Bounded-Error Computations and Completeness

[BibT_eX]

[DOI]

Elmar Böhler

Daniel Meister

Electron. Colloquium Comput. Complex., 2003

Error-Bounded Probabilistic Computations between MA and AM.

[BibT_eX]

[DOI]

Elmar Böhler

Daniel Meister

Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

Disjoint NP-Pairs.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2001

Forbidden-patterns and word extensions for concatenation hierarchies.

[BibT_eX]

[DOI]

PhD thesis, 2001

The Boolean Structure of Dot-Depth One.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 2001

Level 5/2 of the Straubing-Thérien Hierarchy for Two-Letter Alphabets.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 5th International Conference, 2001

A polynomial-time approximation scheme for base station positioning in UMTS networks.

[BibT_eX]

[DOI]

Proceedings of the 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M 2001), 2001

2000

A moment of perfect clarity I: the parallel census technique.

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

SIGACT News, 2000

A moment of perfect clarity II: consequences of sparse sets hard for NP with respect to weak reductions.

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

SIGACT News, 2000

Languages of Dot-Depth 3/2.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

The Complexity of Base Station Positioning in Cellular Networks.

[BibT_eX]

Steffen Reith

Heribert Vollmer

Proceedings of the ICALP Workshops 2000, 2000

Decidable Hierarchies of Starfree Languages.

[BibT_eX]

[DOI]