Search ACM DL

Search Issue

enter search term and/or author name

**Asking the Metaquestions in Constraint Tractability**

Hubie Chen, Benoit Larose

Article No.: 11

DOI: 10.1145/3134757

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

DOI: 10.1145/3132720

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

DOI: 10.1145/3110290

The C_{1}, … , s_{k} of length at most ℓ and numbers *m* and *d*, whether there is a length-*m* string *s*...

**Hardness of Approximation for Strip Packing**

Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, Michał Pilipczuk

Article No.: 14

DOI: 10.1145/3092026

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

Hubie Chen

Article No.: 15

DOI: 10.1145/3087534

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...