About Me

Currently, I am a postdoc in the group of Dániel Marx at CISPA in Saarbrücken, Germany.
I am doing research in theoretical computer science, where my main work is at the intersection of parameterized complexity and counting complexity.

I received my DPhil (PhD) in Computer Science from the University of Oxford in November 2020, where I was very fortunate to be supervised by Leslie Ann Goldberg and Standa Živný. Previously, I received an M.Sc. and a B.Sc. in Mathematics from TU Berlin and TU Dresden, respectively.

Some keywords that fit the scope of my research: Graph Theory, Computational Counting Problems, Parameterized Algorithms and Complexity, Graph Homomorphisms, Multivariate Complexity.

I love to hike, boulder, climb, run, backpack, kayak, ski, and be out in nature in general. There is a lot of music that I passionately listen to, and you can always tempt me with a board game evening with friends.

News

04/2024 ICALP accept for our paper on the real source of hardness of fundamental problems on bounded-treewidth graphs.
03/2024 SICOMP paper on counting induced subgraphs together with Marc Roth!
03/2024 PODS accept for our paper on counting answers to unions of conjunctive queries. I will present it in Chile in June :).
02/2024 SoCG accept for our paper on Multicut problems in embedded graphs. Florian Hörsch will present it in Athens.
03/2024 New website! ;)
02/2024 I am on the program committee for IPEC 2024.
01/2024 TALG paper about counting list homomorphisms on graphs with bounded treewidth together with Dániel Marx and Pawel Rzążewski.

Publications

Peer-reviewed

Barış Can Esmer, Jacob Focke, Dániel Marx, Paweł Rzążewski
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
ICALP 2024 (to appear) arXiv 2023

Jacob Focke, Leslie Ann Goldberg, Marc Roth and Stanislav Živný
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
PODS 2024 (to appear) arXiv 2023

Jacob Focke, Florian Hörsch, Shaohua Li, Dániel Marx
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
SOCG 2024 (to appear) arXiv 2023

Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs

Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations

Jacob Focke, Dániel Marx, Pawel Rzazewski
Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight Complexity Bounds

Jacob Focke, Marc Roth
Counting Small Induced Subgraphs with Hereditary Properties

Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
Counting Homomorphisms to K4-minor-free Graphs, modulo 2

Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
The Complexity of Approximately Counting Retractions to Square-Free Graphs

Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
The Complexity of Approximately Counting Retractions

Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný
The Complexity of Counting Surjective Homomorphisms and Compactions

Jacob Focke, Nicole Megow, Julie Meißner
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments

Preprints

Jacob Focke, Fabian Frei, Shaohua Li, Dániel Marx, Philipp Schepper, Roohani Sharma, Karol Węgrzycki
Hitting Meets Packing: How Hard Can it Be?

Barış Can Esmer, Jacob Focke, Dániel Marx, Paweł Rzążewski
List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs

Thesis

Jacob Focke
On the complexity of counting homomorphisms under surjectivity constraints

Academic Service

I am on the program committee for IPEC 2024.

In summer 2023 I was a lecturer for the Advanced Course Techniques for Counting Problems
(co-organized with Philip Wellnitz).

I reviewed manuscripts for ESA2024, WG2024, ICALP2024, STOC2024, SODA2024, ESA2023, WG2023, ICALP2023, STOC2023, SODA2023, SICOMP2023, IPL2023, STOC2022, MFCS2022, TCS2022, Inf&Comp2022, STACS2021, ICALP2021, DM2021, TCS2021, STACS2020, SODA2020, ITCS2020, TCS2020, STACS2019.

Contact

Office

Room 3.02
Kaiserstraße 21
66386 St. Ingbert
Germany

Get in touch at jacobfocke @ cispade