Holger Dell (Photo)

Research Interests

I have worked on a diverse set of projects in different areas of theoretical computer science.


Take a 3-CNF formula in n variables. Can a polynomial-time algorithm reduce its size to O(n) without destroying its satisfiability?

Exponential Time Hypotheses

We can determine the satisfiability of CNF-formulas in time 2^n. Can this be improved to 1.999^n?


Which tasks can only be achieved using randomness? Is there a way to reduce the amount of randomness used?

Counting Problems

Is there an algorithm for the Permanent that is faster than Ryser's formula?



Short CV

Madison, Wisconsin, USA
Berlin, Germany
PhD at the Humboldt University of Berlin under the supervision of Martin Grohe. Member of the research training group Methods for Discrete Structures and of the Berlin Mathematical School.
Saarbücken, Germany
BSc & MSc at Saarland University and at the Max Planck Institute for Computer Science. Markus Bläser supervised my MSc thesis, and Joachim Weickert supervised my BSc thesis.