3 papers
cs.CC2008
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…
cs.CC2000
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…
cs.CC2000
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…