Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 6 Issue 4, August 2014

The complexity of the comparator circuit value problem
Stephen A. Cook, Yuval Filmus, Dai Tri Man Lê
Article No.: 15
DOI: 10.1145/2635822

In 1990, Subramanian [1990] defined the complexity class CC as the set of problems log-space reducible to the comparator circuit value problem (CCV). He and Mayr showed that NL ⊆ CC ⊆ P, and proved that in addition to CCV several other...

FPT is characterized by useful obstruction sets: Connecting algorithms, kernels, and quasi-orders
Michael R. Fellows, Bart M. P. Jansen
Article No.: 16
DOI: 10.1145/2635820

Many graph problems were first shown to be fixed-parameter tractable using the results of Robertson and Seymour on graph minors. We show that the combination of finite, computable obstruction sets and efficient order tests is not just one way of...

The complexity of counting homomorphisms to cactus graphs modulo 2
Andreas Göbel, Leslie Ann Goldberg, David Richerby
Article No.: 17
DOI: 10.1145/2635825

A homomorphism from a graph G to a graph H is a function from V(G) to V(H) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally...