Holger Dell

Contact

• Office: Room 414, E1 3
• Phone: +49-681-302-4447
• Telegram: @holgerdell
• Email:
• Physical mail:
  Cluster of Excellence (MMCI)
  Saarland Informatics Campus E1.7
  66123 Saarbrücken
  Germany

Projects

Interactive simulation of the color refinement algorithm (source on github)

Teaching

• Multivariate Algorithmics
  (Winter 2018/19)
• 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

• Lovász Meets Weisfeiler and Leman
  (html, pdf)
• 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
  TCS 2018 / 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
  arXiv 2018 / 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 CSR 2019, 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.