John Lapinskas

According to our database, John Lapinskas authored at least 18 papers between 2013 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Nearly Optimal Independence Oracle Algorithms for Edge Estimation in Hypergraphs.

Holger Dell, John Lapinskas, Kitty Meeks

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Four universal growth regimes in degree-dependent first passage percolation on spatial random graphs II.

Júlia Komjáthy, John Lapinskas, Johannes Lengler, Ulysse Schaller

CoRR, 2023

Four universal growth regimes in degree-dependent first passage percolation on spatial random graphs I.

Júlia Komjáthy, John Lapinskas, Johannes Lengler, Ulysse Schaller

CoRR, 2023

Instability of backoff protocols with arbitrary arrival rates.

Leslie Ann Goldberg, John Lapinskas

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Graph Ranking and the Cost of Sybil Defense.

Gwendolyn Farach-Colton, Martin Farach-Colton, Leslie Ann Goldberg, Hanna Komlós, John Lapinskas, Reut Levi, Moti Medina, Miguel A. Mosteiro

Proceedings of the 24th ACM Conference on Economics and Computation, 2023

2022

Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle.

Holger Dell, John Lapinskas, Kitty Meeks

SIAM J. Comput., 2022

2021

Fine-Grained Reductions from Approximate Counting to Decision.

Holger Dell, John Lapinskas

ACM Trans. Comput. Theory, 2021

Faster exponential-time algorithms for approximately counting independent sets.

Leslie Ann Goldberg, John Lapinskas, David Richerby

Theor. Comput. Sci., 2021

2020

Phase transitions of the Moran process and algorithmic consequences.

Leslie Ann Goldberg, John Lapinskas, David Richerby

Random Struct. Algorithms, 2020

Stopping explosion by penalising transmission to hubs in scale-free spatial random graphs.

Júlia Komjáthy, John Lapinskas, Johannes Lengler

CoRR, 2020

Approximately counting and sampling small witnesses using a colourful decision oracle.

Holger Dell, John Lapinskas, Kitty Meeks

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

Asymptotically optimal amplifiers for the Moran process.

Leslie Ann Goldberg, John Lapinskas, Johannes Lengler, Florian Meier, Konstantinos Panagiotou, Pascal Pfister

Theor. Comput. Sci., 2019

A Fixed-Parameter Perspective on #BIS.

Radu Curticapean, Holger Dell, Fedor V. Fomin, Leslie Ann Goldberg, John Lapinskas

Algorithmica, 2019

2017

Amplifiers for the Moran Process.

Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, David Richerby

J. ACM, 2017

2016

Approximately counting locally-optimal structures.

Leslie Ann Goldberg, Rob Gysel, John Lapinskas

J. Comput. Syst. Sci., 2016

2015

On-line Ramsey Numbers of Paths and Cycles.

Joanna Cyman, Tomasz Dzido, John Lapinskas, Allan Lo

Electron. J. Comb., 2015

2014

Optimal covers with Hamilton cycles in random graphs.

Dan Hefetz, Daniela Kühn, John Lapinskas, Deryk Osthus

Comb., 2014

2013

Optimal Packings of Hamilton Cycles in Graphs of High Minimum Degree.

Daniela Kühn, John Lapinskas, Deryk Osthus

Comb. Probab. Comput., 2013