enter search term and/or author name
Asking the Metaquestions in Constraint Tractability
Hubie Chen, Benoit Larose
Article No.: 11
The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there is an assignment to the variables satisfying all of the constraints. One formulation of the CSP...
Canonizing Graphs of Bounded Tree Width in Logspace
Michael Elberfeld, Pascal Schweitzer
Article No.: 12
Graph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two graphs are isomorphic exactly if their canons are equal. We show that graphs of bounded tree width...
Finding Consensus Strings with Small Length Difference between Input and Solution Strings
Markus L. Schmid
Article No.: 13
Strip packing is a classical packing problem, where the goal is to pack a set of rectangular objects into a strip of a given width, while minimizing the total height of the packing. The problem has multiple applications, for example, in scheduling...
Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness
Article No.: 15
We present and study a framework in which one can present alternation-based lower bounds on proof length in proof systems for quantified Boolean formulas. A key notion in this framework is that of proof system ensemble, which is...