31 citations · 62 across the 15 of their papers we have counts for
5 papers · 1 filter
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…
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…
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…