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
∙
03/31/2022
Instability of backoff protocols with arbitrary arrival rates
In contention resolution, multiple processors are trying to coordinate t...
research
∙
05/11/2020
Faster Exponential-time Algorithms for Approximately Counting Independent Sets
Counting the independent sets of a graph is a classical #P-complete prob...
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
∙
04/06/2018
Phase Transitions of the Moran Process and Algorithmic Consequences
The Moran process is a randomised algorithm that models the spread of ge...
research
∙
07/14/2017