31 citations · 62 across the 15 of their papers we have counts for
21 papers
Temporal Conductance and Bounds on the Voter Model for Dynamic Networks
Tatiana Rocha Avila, Holger Dell, John Lapinskas
The voter model is a classical stochastic process that models how opinions might spread through a network: at each step, every node lazily adopts the opinion of a random neighbour;…
Degree-dependent and distance-dependent contact rates interpolate between explosive, exponential and polynomial epidemic growth
Zylan Benjert, Júlia Komjáthy, Johannes Lengler +2
It is a fundamental question in epidemiology to estimate, model and predict the growth rate of a pandemic. Analogously, analysing the diffusion of innovation, (fake) news, memes, a…
The Instability of all Backoff Protocols
Leslie Ann Goldberg, John Lapinskas
In this paper we prove Aldous's conjecture from 1987 that there is no backoff protocol that is stable for any positive arrival rate. The setting is a communication channel for coor…
Polynomial growth in degree-dependent first passage percolation on spatial random graphs
Júlia Komjáthy, John Lapinskas, Johannes Lengler +1
In this paper we study a version of (non-Markovian) first passage percolation on graphs, where the transmission time between two connected vertices is non-iid, but increases by a p…
Four universal growth regimes in degree-dependent first passage percolation on spatial random graphs I
Júlia Komjáthy, John Lapinskas, Johannes Lengler +1
One-dependent first passage percolation is a spreading process on a graph where the transmission time through each edge depends on the direct surroundings of the edge. In particula…
Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
Holger Dell, John Lapinskas, Kitty Meeks
We study a query model of computation in which an n-vertex k-hypergraph can be accessed only via its independence oracle or via its colourful independence oracle, and each oracle q…
Instability of backoff protocols with arbitrary arrival rates
Leslie Ann Goldberg, John Lapinskas
In contention resolution, multiple processors are trying to coordinate to send discrete messages through a shared channel with limited communication. If two processors send at the…
Faster Exponential-time Algorithms for Approximately Counting Independent Sets
Leslie Ann Goldberg, John Lapinskas, David Richerby
Counting the independent sets of a graph is a classical #P-complete problem, even in the bipartite case. We give an exponential-time approximation scheme for this problem which is…
Stopping explosion by penalising transmission to hubs in scale-free spatial random graphs
Júlia Komjáthy, John Lapinskas, Johannes Lengler
We study the spread of information in finite and infinite inhomogeneous spatial random graphs. We assume that each edge has a transmission cost that is a product of an i.i.d. rando…
Approximately counting and sampling small witnesses using a colourful decision oracle
Holger Dell, John Lapinskas, Kitty Meeks
In this paper, we design efficient algorithms to approximately count the number of edges of a given -hypergraph, and to sample an approximately uniform random edge. The hypergra…
Phase Transitions of the Moran Process and Algorithmic Consequences
Leslie Ann Goldberg, John Lapinskas, David Richerby
The Moran process is a random process that models the spread of genetic mutations through graphs. If the graph is connected, the process eventually reaches "fixation", where every…
Graph Ranking and the Cost of Sybil Defense
Gwendolyn Farach-Colton, Martin Farach-Colton, Leslie Ann Goldberg +5
Ranking functions such as PageRank assign numeric values (ranks) to nodes of graphs, most notably the web graph. Node rankings are an integral part of Internet search algorithms, s…
Fine-grained reductions from approximate counting to decision
Holger Dell, John Lapinskas
In this paper, we introduce a general framework for fine-grained reductions of approximate counting problems to their decision versions. (Thus we use an oracle that decides whether…
A Fixed-Parameter Perspective on #BIS
Radu Curticapean, Holger Dell, Fedor Fomin +2
The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexi…
Asymptotically Optimal Amplifiers for the Moran Process
Leslie Ann Goldberg, John Lapinskas, Johannes Lengler +3
We study the Moran process as adapted by Lieberman, Hauert and Nowak. This is a model of an evolving population on a graph or digraph where certain individuals, called "mutants" ha…
Amplifiers for the Moran Process
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg +2
The Moran process, as studied by Lieberman, Hauert and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlyin…
Approximately counting locally-optimal structures
Leslie Ann Goldberg, Rob Gysel, John Lapinskas
A locally-optimal structure is a combinatorial structure such as a maximal independent set that cannot be improved by certain (greedy) local moves, even though it may not be global…
On-line Ramsey numbers of paths and cycles
Joanna Cyman, Tomasz Dzido, John Lapinskas +1
Consider a game played on the edge set of the infinite clique by two players, Builder and Painter. In each round, Builder chooses an edge and Painter colours it red or blue. Builde…
Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
Daniela Kühn, John Lapinskas, Deryk Osthus +1
A conjecture of Thomassen from 1982 states that for every k there is an f(k) so that every strongly f(k)-connected tournament contains k edge-disjoint Hamilton cycles. A classical…
Optimal packings of Hamilton cycles in graphs of high minimum degree
Daniela Kühn, John Lapinskas, Deryk Osthus
We study the number of edge-disjoint Hamilton cycles one can guarantee in a sufficiently large graph G on n vertices with minimum degree d = (1/2+a)n. For any constant a > 0, we gi…
Optimal covers with Hamilton cycles in random graphs
Dan Hefetz, Daniela Kühn, John Lapinskas +1
A packing of a graph G with Hamilton cycles is a set of edge-disjoint Hamilton cycles in G. Such packings have been studied intensively and recent results imply that a largest pack…