Author name cluster

Michael Bauland

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

MFCS Conference 2005 Conference Paper

Isomorphic Implication

Michael Bauland
Edith Hemaspaandra

Abstract We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set of constraints, this problem is in P, NP-complete, or NP-hard, coNP-hard, and in \({\rm P^{NP}_{||}}\). We show how to extend the NP-hardness and coNP-hardness to \({\rm P^{NP}_{||}}\) -hardness for some cases, and conjecture that this can be done in all cases.

Details

MFCS Conference 2005 Conference Paper

The Complexity of Satisfiability Problems: Refining Schaefer's Theorem

Eric Allender
Michael Bauland
Neil Immerman
Henning Schnoor
Heribert Vollmer

Abstract Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NP-complete, and identified all tractable cases. Schaefer’s dichotomy theorem actually shows that there are at most two constraint satisfaction problems, up to polynomial-time isomorphism (and these isomorphism types are distinct if and only if P ≠ NP). We show that if one considers AC 0 isomorphisms, then there are exactly six isomorphism types (assuming that the complexity classes NP, P, ⊕L, NL, and L are all distinct).

Details

SAT Conference 2004 Conference Paper

An Algebraic Approach to the Complexity of Generalized Conjunctive Queries

Michael Bauland
Philippe Chapdelaine
Nadia Creignou
Miki Hermann
Heribert Vollmer

Kolaitis and Vardi pointed out that constraint satisfaction and conjunctive query containment are essentially the same problem. We study the Boolean conjunctive queries under a more detailed scope, where we investigate their counting problem by means of the algebraic approach through Galois theory, taking advantage of Post’s lattice. We prove a trichotomy theorem for the generalized conjunctive query counting problem, showing this way that, contrary to the corresponding decision problems, constraint satisfaction and conjunctive-query containment differ for other computational goals. We also study the audit problem for conjunctive queries asking whether there exists a frozen variable in a given query. This problem is important in databases supporting statistical queries. We derive a dichotomy theorem for this audit problem that sheds more light on audit applicability within database systems.

Details