All reports by Author Holger Dell:

__
TR14-075
| 16th May 2014
__

Holger Dell#### A simple proof that AND-compression of NP-complete problems is hard

Revisions: 3

__
TR10-078
| 27th April 2010
__

Holger Dell, Thore Husfeldt, Martin WahlĂ©n#### Exponential Time Complexity of the Permanent and the Tutte Polynomial

Revisions: 1

__
TR10-038
| 10th March 2010
__

Dieter van Melkebeek, Holger Dell#### Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses

Revisions: 1

Holger Dell

Drucker (2012) proved the following result: Unless the unlikely complexity-theoretic collapse coNP is in NP/poly occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a simple proof of this result.

An AND-compression is ... more >>>

Holger Dell, Thore Husfeldt, Martin WahlĂ©n

The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of $n$-variable 3-CNF formulas requires time $\exp(\Omega(n))$. We relax this hypothesis by introducing its counting version #ETH, namely that every algorithm that counts the satisfying assignments requires time $\exp(\Omega(n))$. We transfer the sparsification lemma for $d$-CNF formulas to the counting ... more >>>

Dieter van Melkebeek, Holger Dell

Consider the following two-player communication process to decide a language $L$: The first player holds the entire input $x$ but is polynomially bounded; the second player is computationally unbounded but does not know any part of $x$; their goal is to cooperatively decide whether $x$ belongs to $L$ at small ... more >>>