research
∙
11/07/2022
Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
We study a query model of computation in which an n-vertex k-hypergraph ...
share
research
∙
07/01/2021
Modular counting of subgraphs: Matchings, matching-splittable graphs, and paths
We systematically investigate the complexity of counting subgraph patter...
research
∙
07/10/2019
Approximately counting and sampling small witnesses using a colourful decision oracle
In this paper, we prove "black box" results for turning algorithms which...
research
∙
02/13/2019
Counting Answers to Existential Questions
Conjunctive queries select and are expected to return certain tuples fro...
research
∙
12/07/2018
Kernelization of Packing Problems
Kernelization algorithms are polynomial-time reductions from a problem t...
research
∙
05/22/2018
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
The Strong Exponential Time Hypothesis and the OV-conjecture are two pop...
research
∙
04/25/2018
Extensor-Coding
We devise an algorithm that approximately computes the number of paths o...
research
∙
02/24/2018
Weisfeiler-Leman meets Homomorphisms
In this paper, we relate a beautiful theory by Lovász with a popular heu...
research
∙
10/04/2017
Note on "The Complexity of Counting Surjective Homomorphisms and Compactions"
Focke, Goldberg, and Živný (arXiv 2017) prove a complexity dichotomy for...
research
∙
07/14/2017