4 citations · 7 across the 6 of their papers we have counts for
6 papers · 1 filter
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…
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…
A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions
Christian Glasser, Lane A. Hemaspaandra
This paper discusses advances, due to the work of Cai, Naik, and Sivakumar and Glasser, in the complexity class collapses that follow if NP has sparse hard sets under reductions we…
A Moment of Perfect Clarity I: The Parallel Census Technique
Christian Glasser, Lane A. Hemaspaandra
We discuss the history and uses of the parallel census technique---an elegant tool in the study of certain computational objects having polynomially bounded census functions. A seq…