Holger Dell

Contact

• Room 414, E1 3
• Office phone: +49-681-302-4447
• Postal address » « Hide addresses
  Shipping Address
  Holger Dell, Room 414
  Saarland University
  Campus, Building E1.3
  66123 Saarbrücken
  Germany

  Billing Address
  Saarland University
  Cluster of Excellence
  Campus, Building E1.7
  66123 Saarbrücken
  Germany

Research

Complexity theorists study the power and the limits of computation. Can every cryptographic encryption scheme be broken? How much time is required to solve the problems that we care about? Is randomness necessary for efficient computation? As of today, no one knows the answers to these fundamental questions.

Teaching

• P vs. NP: Is it difficult to be creative?
  (Summer 2017)
• Complexity Theory
  (Fall 2016/17)
• Complexity Theory
  (Summer 2015)
• Algorithms for the Satisfiability Problem
  (Fall 2014/15)
• Pseudorandomness and Derandomization
  (Spring 2013)

Talks

• Finding Detours is FPT
  (html, pdf)
• Fine-Grained Counting Complexity I
  (video, html, pdf)

Service

• Organizing the Tree Width Challenge of PACE 2017: The Second Parameterized Algorithms and Computational Experiments Challenge.
• PACE 2016: The First Parameterized Algorithms and Computational Experiments Challenge.

Publications

• Homomorphisms are a good basis for counting small subgraphs
  Radu Curticapean, Holger Dell, and Dániel Marx
  STOC 2017 / arXiv 2017
• A Fixed-Parameter Perspective on #BIS
  Radu Curticapean, Holger Dell, Fedor Fomin, Leslie Ann Goldberg, and John Lapinskas
  arXiv 2017
• Finding Detours is Fixed-parameter Tractable
  Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor Fomin
  ICALP 2017 / arXiv 2016
• Counting edge-injective homomorphisms and k-matchings on restricted graph classes
  Radu Curticapean, Holger Dell, and Marc Roth
  STACS 2017 / arXiv 2017
• Fine-grained dichotomies for the Tutte plane and Boolean #CSP
  Cornelius Brand, Holger Dell, and Marc Roth
  IPEC 2016 / arXiv 2016
• Complexity and Approximability of Parameterized MAX-CSPs
  Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke
  Algorithmica 2017 / IPEC 2015 / arXiv 2015
• The Parity of Set Systems under Random Restrictions with Applications to Exponential Time Problems
  Andreas Björklund, Holger Dell, and Thore Husfeldt
  ICALP 2015
• AND-compression of NP-complete problems: Streamlined proof and minor observations
  Holger Dell
  Algorithmica 2016 / IPEC 2014 / ECCC 2014 / arXiv 2014
• Is Valiant–Vazirani's Isolation Probability Improvable?
  Holger Dell, Valentine Kabanets, Dieter van Melkebeek, and Osamu Watanabe
  Computational Complexity 2013 / CCC 2012 / ECCC 2012
• Kernelization of Packing Problems
  Holger Dell and Dániel Marx
  SODA 2012
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
  Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén
  Transactions on Algorithms 2014 / ECCC 2012 / ICALP 2010
• On Problems as Hard as CNFSAT
  Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström
  Transactions on Algorithms 2016 / CCC 2012 / arXiv 2011
• Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses
  Holger Dell and Dieter van Melkebeek
  Journal of the ACM 2014 / STOC 2010 / ECCC 2010
• Complexity of the Bollobás–Riordan Polynomial
  Markus Bläser, Holger Dell, and Johann Makowsky
  Theory of Computing Systems 2010 / CSR 2008
• Complexity and Approximability of the Cover Polynomial
  Markus Bläser, Holger Dell, and Mahmoud Fouz
  Computational Complexity 2011
• Complexity of the Cover Polynomial
  Markus Bläser and Holger Dell
  ICALP 2007

Curriculum Vitae

• Universität des Saarlandes, Germany
  (2014–2019)
  Head (W2-equivalent) of the independent research group Foundations of Exact Algorithms in the Cluster of Excellence Multimodal Computing and Interaction.
• Simons Insitute and UC Berkeley, USA
  (August 2015 – May 2016)
  Simons–Berkeley Research Fellow, participating in the programs Fine-Grained Complexity and Algorithm Design and Counting Complexity and Phase Transitions.
• LIAFA, Université Paris Diderot, France
  (2013–2014)
  Postdoctoral Fellow in the Algorithms and Complexity Group.
• University of Wisconsin–Madison, USA
  (2011–2013)
  Postdoctoral Fellow in the Feodor Lynen Program of the Alexander von Humboldt Foundation. Hosted by Dieter van Melkebeek.
• Humboldt-Universität zu Berlin, Germany
  (2007–2011)
  PhD student under the supervision of Martin Grohe. Fellow in the research training group Methods for Discrete Structures and the Berlin Mathematical School.
• Universität des Saarlandes, Germany
  (2004–2007)
  MSc under the supervision of Markus Bläser and BSc under the supervision of Joachim Weickert. Also worked at the Max Planck Institute for Computer Science.