Holger Dell

Contact

• Room 414, E1 3
• Office phone: +49-681-302-4447
• Skype: Chat, Call
• Postal address » « Hide addresses
  Cluster of Excellence (MMCI)
  Saarland Informatics Campus E1.7
  66123 Saarbrücken
  Germany
  

Research

Algorithms & Complexity is about the power and the limits of computation. Can every cryptographic encryption scheme be broken? For which problems can we beat the exhaustive search method? Is randomness necessary for efficient computation? As of today, no one knows the answers to these fundamental questions.

Teaching

• Grundzüge von Algorithmen und Datenstrukturen
  (Winter 2017/18)
• P vs. NP seminar
  (Summer 2017)
• Complexity Theory
  (Winter 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)

Publications

• Lovász Meets Weisfeiler and Leman
  Holger Dell, Martin Grohe, and Gaurav Rattan
  ICALP 2018 / arxiv 2018
• Extensor-Coding
  Cornelius Brand, Holger Dell, and Thore Husfeldt
  STOC 2018 / arxiv 2018
• More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
  Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof
  STOC 2018 / arXiv 2018
• Fine-grained reductions from approximate counting to decision
  Holger Dell and John Lapinskas
  STOC 2018 / arXiv 2017
• 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
  IPEC 2017 / 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
  Algorithmica 2018 / 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

Service

• Member of the Steering Committee of PACE.
• Member of the Program Committees of SODA 2019, CSR 2018, PACE 2017, PACE 2016, ESA 2016, IPEC 2015, and IPEC 2014.

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