Christian Glaßer

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

Emptiness problems for integer circuits.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

2019

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

[BibT_eX]

[DOI]

Titus Dose

Electron. Colloquium Comput. Complex., 2019

2017

Circuit satisfiability and constraint satisfaction around Skolem Arithmetic.

[BibT_eX]

[DOI]

Peter Jonsson

Barnaby Martin

Theor. Comput. Sci., 2017

Introduction to Autoreducibility and Mitoticity.

[BibT_eX]

[DOI]

Proceedings of the Computability and Complexity, 2017

2016

Efficient algorithms for membership in boolean hierarchies of regular languages.

[BibT_eX]

[DOI]

Victor L. Selivanov

Theor. Comput. Sci., 2016

2015

Constraint Satisfaction Problems around Skolem Arithmetic.

[BibT_eX]

[DOI]

Peter Jonsson

Barnaby Martin

CoRR, 2015

2014

Unions of Disjoint NP-Complete Sets.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 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

2013

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

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

[BibT_eX]

[DOI]

Dung T. Nguyen

Electron. Colloquium Comput. Complex., 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 shrinking property for NP and coNP.

[BibT_eX]

[DOI]

Victor L. Selivanov

Theor. Comput. Sci., 2011

The fault tolerance of NP-hard problems.

[BibT_eX]

[DOI]

Aduri Pavan

Inf. Comput., 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

2010

Equivalence Problems for Circuits over Sets of Natural Numbers.

[BibT_eX]

[DOI]

Katrin Herr

Matthias Waldherr

Theory Comput. Syst., 2010

Space-efficient informational redundancy.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2010

Hardness and Approximability in Multi-Objective Optimization.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Satisfiability of algebraic circuits over sets of natural numbers.

[BibT_eX]

[DOI]

Matthias Waldherr

Discret. Appl. Math., 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

Non-mitotic sets.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

2008

Splitting NP-Complete Sets.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Languages of Dot-Depth 3/2.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2008

The complexity of unions of disjoint sets.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

Multiobjective Disk Cover Admits a PTAS.

[BibT_eX]

[DOI]

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

2007

Canonical disjoint NP-pairs of propositional proof systems.

[BibT_eX]

[DOI]

Liyu Zhang

Theor. Comput. Sci., 2007

Autoreducibility, mitoticity, and immunity.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2007

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

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2007

The Informational Content of Canonical Disjoint NP-Pairs.

[BibT_eX]

[DOI]

Liyu Zhang

Electron. Colloquium Comput. Complex., 2007

2006

Properties of NP-Complete Sets.

[BibT_eX]

[DOI]

SIAM J. Comput., 2006

Error-bounded probabilistic computations between MA and AM.

[BibT_eX]

[DOI]

Elmar Böhler

Daniel Meister

J. Comput. Syst. Sci., 2006

Mitosis in Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 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

2005

Generation problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Machines that can Output Empty Words

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems

[BibT_eX]

[DOI]

Liyu Zhang

Electron. Colloquium Comput. Complex., 2005

Redundancy in Complete Sets

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

A Reducibility that Corresponds to Unbalanced Leaf-Language Classes

[BibT_eX]

[DOI]

Klaus W. Wagner

Electron. Colloquium Comput. Complex., 2005

The complexity of base station positioning in cellular networks.

[BibT_eX]

[DOI]

Steffen Reith

Heribert Vollmer

Discret. Appl. Math., 2005

Polylog-Time Reductions Decrease Dot-Depth.

[BibT_eX]

[DOI]

Proceedings of the STACS 2005, 2005

2004

Disjoint NP-Pairs.

[BibT_eX]

[DOI]

SIAM J. Comput., 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

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

Reductions between Disjoint NP-Pairs

[BibT_eX]

[DOI]

Samik Sengupta

Electron. Colloquium Comput. Complex., 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

Decidable Hierarchies of Starfree Languages.

[BibT_eX]

[DOI]