Search ACM DL

Search Issue

enter search term and/or author name

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