John Lapinskas

Email: john.[surname]@cs.ox.ac.uk
Office: 008, Wolfson Building

Department of Computer Science
University of Oxford
Wolfson Building, Parks Road
Oxford, OX1 3QD, United Kingdom

• About Me
• CV (PDF)
• Publications
• Teaching

List of publications

• Approximately counting and sampling small witnesses using a colourful decision oracle (with Holger Dell and Kitty Meeks). Conference version submitted. arXiv.
• Phase transitions of the Moran process and algorithmic consequences (with Leslie Ann Goldberg and David Richerby). To appear in Random Structures and Algorithms. arXiv.
• Fine-grained reductions from approximate counting to decision (with Holger Dell). Submitted. An abbreviated version appears in STOC 2018. arXiv, conference.
• A fixed-parameter perspective on #BIS (with Radu Curticapean, Holger Dell, Fedor Fomin and Leslie Ann Goldberg). Algorithmica (2019), 1--21. An abbreviated version appears in IPEC 2017 (best paper prize). arXiv, conference, journal.
• Asymptotically optimal amplifiers for the Moran process (with Leslie Ann Goldberg, Johannes Lengler, Florian Meier, Konstantinos Panagiotou and Pascal Pfister). Theoretical Computer Science 758 (2019), 73--93. arXiv, journal.
• Amplifiers for the Moran process (with Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg and David Richerby). Journal of the ACM 64.1 (2017). An abbreviated version appears in ICALP 2016 (Track A, best paper prize). arXiv, conference, journal.
• Approximately counting locally-optimal structures (with Leslie Ann Goldberg and Rob Gysel). Journal of Computer and System Sciences 82.6 (2016), 1144--1160. An abbreviated version appears in ICALP 2015 (Track A). arXiv, conference, journal.
• On-line Ramsey numbers of paths and cycles (with Joanna Cyman, Tomasz Dzido and Allan Lo). Electronic Journal of Combinatorics 22.1 (2015). arXiv, journal.
• Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments (with Daniela Kühn, Deryk Osthus and Viresh Patel). Proceedings of the LMS 109.3 (2014), 733--762. arXiv, journal.
• Optimal packings of Hamilton cycles in graphs of high minimum degree (with Daniela Kühn and Deryk Osthus). Combinatorics, Probability and Computing 22 (2013), 394--416. arXiv, journal.
• Optimal covers with Hamilton cycles in random graphs (with Dan Hefetz, Daniela Kühn and Deryk Osthus). Combinatorica 34.5 (2014), 573--576. arXiv, journal.