ACM DL

Computation Theory (TOCT)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computation Theory (TOCT), Volume 6 Issue 2, May 2014

Clique Cover and Graph Separation: New Incompressibility Results
Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström
Article No.: 6
DOI: 10.1145/2594439

The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity. In this article, we show that, unless the polynomial hierarchy collapses to its third level, the following...

Hard Instances of Algorithms and Proof Systems
Yijia Chen, Jörg Flum, Moritz Müller
Article No.: 7
DOI: 10.1145/2601336

If the class TAUT of tautologies of propositional logic has no almost optimal algorithm, then every algorithm A deciding TAUT has a hard sequence, that is, a polynomial time computable sequence witnessing that A is not almost optimal. We show that...

The Complexity of Approximately Counting Tree Homomorphisms
Leslie Ann Goldberg, Mark Jerrum
Article No.: 8
DOI: 10.1145/2600917

We study two computational problems, parameterised by a fixed tree H. #HOMSTO(H) is the problem of counting homomorphisms from an input graph G to H. #WHOMSTO(H) is the problem of counting weighted...

A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
Article No.: 9
DOI: 10.1145/2601327

The following two decision problems capture the complexity of comparing integers or rationals that are succinctly represented in product-of-exponentials notation, or equivalently, via arithmetic circuits using only multiplication and division...