4 citations · 7 across the 6 of their papers we have counts for
8 papers
Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP
Fabian Egidy, Christian Glaßer, Martin Herold
We study the existence of optimal and p-optimal proof systems for classes in the Boolean hierarchy over . Our main results concern , i.e., the second leve…
Oracle with , but no Many-One Completeness in UP, DisjNP, and DisjCoNP
Anton Ehrmanntraut, Fabian Egidy, Christian Glaßer
We construct an oracle relative to which , but there are no many-one complete sets in , no many-one complete disjoint $\ma…
Constraint Satisfaction Problems around Skolem Arithmetic
Christian Glasser, Peter Jonsson, Barnaby Martin
We study interactions between Skolem Arithmetic and certain classes of Constraint Satisfaction Problems (CSPs). We revisit results of Glass er et al. in the context of CSPs and set…
Applications of Discrepancy Theory in Multiobjective Approximation
Christian Glaßer, Christian Reitwießner, Maximilian Witek
We apply a multi-color extension of the Beck-Fiala theorem to show that the multiobjective maximum traveling salesman problem is randomized 1/2-approximable on directed graphs and…
Balanced Combinations of Solutions in Multi-Objective Optimization
Christian Glaßer, Christian Reitwießner, Maximilian Witek
For every list of integers x_1, ..., x_m there is some j such that x_1 + ... + x_j - x_{j+1} - ... - x_m \approx 0. So the list can be nearly balanced and for this we only need one…
Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages
Christian Glasser, Heinz Schmitz, Victor Selivanov
The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were prev…