John Lapinskas

34 papers A* 6B 1Journal 26Unranked 1
YearRankTypeTitle / Venue / Authors
2026 J jnl
The Instability of all Backoff Protocols.
CoRR
Leslie Ann Goldberg, John Lapinskas
2025 J jnl
Instability of backoff protocols with arbitrary arrival rates.
J. Comput. Syst. Sci.
Leslie Ann Goldberg, John Lapinskas
2024 A* conf
Nearly Optimal Independence Oracle Algorithms for Edge Estimation in Hypergraphs.
ICALP
Holger Dell, John Lapinskas, Kitty Meeks
2023 J jnl
Four universal growth regimes in degree-dependent first passage percolation on spatial random graphs I.
CoRR
Júlia Komjáthy, John Lapinskas, Johannes Lengler, Ulysse Schaller
2023 J jnl
Four universal growth regimes in degree-dependent first passage percolation on spatial random graphs II.
CoRR
Júlia Komjáthy, John Lapinskas, Johannes Lengler, Ulysse Schaller
2023 A* conf
Graph Ranking and the Cost of Sybil Defense.
EC
Gwendolyn Farach-Colton, Martin Farach-Colton, Leslie Ann Goldberg, Hanna Komlós, John Lapinskas, Reut Levi, Moti Medina, Miguel A. Mosteiro
2023 A* conf
Instability of backoff protocols with arbitrary arrival rates.
SODA
Leslie Ann Goldberg, John Lapinskas
2022 J jnl
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle.
SIAM J. Comput.
Holger Dell, John Lapinskas, Kitty Meeks
2022 J jnl
Instability of backoff protocols with arbitrary arrival rates.
CoRR
Leslie Ann Goldberg, John Lapinskas
2022 J jnl
Nearly optimal independence oracle algorithms for edge estimation in hypergraphs.
CoRR
Holger Dell, John Lapinskas, Kitty Meeks
2021 J jnl
Faster exponential-time algorithms for approximately counting independent sets.
Theor. Comput. Sci.
Leslie Ann Goldberg, John Lapinskas, David Richerby
2021 J jnl
Fine-Grained Reductions from Approximate Counting to Decision.
ACM Trans. Comput. Theory
Holger Dell, John Lapinskas
2020 A* conf
Approximately counting and sampling small witnesses using a colourful decision oracle.
SODA
Holger Dell, John Lapinskas, Kitty Meeks
2020 J jnl
Faster Exponential-time Algorithms for Approximately Counting Independent Sets.
CoRR
Leslie Ann Goldberg, John Lapinskas, David Richerby
2020 J jnl
Phase transitions of the Moran process and algorithmic consequences.
Random Struct. Algorithms
Leslie Ann Goldberg, John Lapinskas, David Richerby
2020 J jnl
Stopping explosion by penalising transmission to hubs in scale-free spatial random graphs.
CoRR
Júlia Komjáthy, John Lapinskas, Johannes Lengler
2019 J jnl
A Fixed-Parameter Perspective on #BIS.
Algorithmica
Radu Curticapean, Holger Dell, Fedor V. Fomin, Leslie Ann Goldberg, John Lapinskas
2019 J jnl
Approximately counting and sampling small witnesses using a colourful decision oracle.
CoRR
Holger Dell, John Lapinskas, Kitty Meeks
2019 J jnl
Asymptotically optimal amplifiers for the Moran process.
Theor. Comput. Sci.
Leslie Ann Goldberg, John Lapinskas, Johannes Lengler, Florian Meier, Konstantinos Panagiotou, Pascal Pfister
2018 A* conf
Fine-grained reductions from approximate counting to decision.
STOC
Holger Dell, John Lapinskas
2018 J jnl
Phase Transitions of the Moran Process and Algorithmic Consequences.
CoRR
Leslie Ann Goldberg, John Lapinskas, David Richerby
2017 B conf
A Fixed-Parameter Perspective on #BIS.
IPEC
Radu Curticapean, Holger Dell, Fedor V. Fomin, Leslie Ann Goldberg, John Lapinskas
2017 J jnl
A Fixed-Parameter Perspective on #BIS.
CoRR
Radu Curticapean, Holger Dell, Fedor V. Fomin, Leslie Ann Goldberg, John Lapinskas
2017 J jnl
Amplifiers for the Moran Process.
J. ACM
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, David Richerby
2017 J jnl
Fine-grained reductions from approximate counting to decision.
CoRR
Holger Dell, John Lapinskas
2016 A* conf
Amplifiers for the Moran Process.
ICALP
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, David Richerby
2016 J jnl
Approximately counting locally-optimal structures.
J. Comput. Syst. Sci.
Leslie Ann Goldberg, Rob Gysel, John Lapinskas
2016 J jnl
Asymptotically Optimal Amplifiers for the Moran Process.
CoRR
Leslie Ann Goldberg, John Lapinskas, Johannes Lengler, Florian Meier, Konstantinos Panagiotou, Pascal Pfister
2015 J jnl
Amplifiers for the Moran Process.
CoRR
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, David Richerby
2015 — conf
Approximately Counting Locally-Optimal Structures.
ICALP (1)
Leslie Ann Goldberg, Rob Gysel, John Lapinskas
2015 J jnl
On-line Ramsey Numbers of Paths and Cycles.
Electron. J. Comb.
Joanna Cyman, Tomasz Dzido, John Lapinskas, Allan Lo
2014 J jnl
Approximately counting locally-optimal structures.
CoRR
Leslie Ann Goldberg, Rob Gysel, John Lapinskas
2014 J jnl
Optimal covers with Hamilton cycles in random graphs.
Comb.
Dan Hefetz, Daniela Kühn, John Lapinskas, Deryk Osthus
2013 J jnl
Optimal Packings of Hamilton Cycles in Graphs of High Minimum Degree.
Comb. Probab. Comput.
Daniela Kühn, John Lapinskas, Deryk Osthus