Holger Dell (Photo)

Research Interests

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

Kernelization

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?

Derandomization

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?

Teaching

Publications

Short CV

2011–2013
Madison, Wisconsin, USA
2007–2011
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.
2004–2007
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.