Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 9 Issue 3, October 2017

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 Closest Substring Problem is to decide, for given strings s1, … , sk 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...