BARC talk by John Lapinskas

Thursday, 5 March 2020, John Lapinskas, lecturer at the University of Bristol, will give a talk on "Fine-grained reductions from approximate counting to decision".

Title:
Fine-grained reductions from approximate counting to decision.

Abstract:
Many decision problems can naturally be phrased as: "Does a witness exist?". For example, SAT asks whether a CNF formula has a satisfying assignment. These problems all have "natural" counting versions, in which we ask: "How many witnesses exist?". For example, #SAT asks how many satisfying assignments a CNF formula has. Often, these problems are #P-complete to solve exactly, but can be solved approximately in polynomial time. It is easy to show that an approximate counting algorithm yields a decision algorithm, but surprisingly, the opposite is often true as well - for example, a subexponential-time algorithm for SAT would yield a subexponential-time approximation algorithm for #SAT. This talk will be about a new way of bootstrapping decision algorithms to approximate counting algorithms, with two key advantages. First, the framework is highly general and applies to many of the most important problems in fine-grained and parameterised complexity, including k-SUM, k-OV, and k-Clique. Second, unlike classical results in the area, the process is efficient in the sense of adding very little overhead to the running time of the original decision algorithm.

Bio:
John Lapinskas received his PhD in mathematics at Birmingham in 2014 (supervised Daniela Kühn), before spending five years as a postdoc with Leslie Goldberg in Oxford. Since 2019, he has been a computer science lecturer at the University of Bristol. His current research is focused on problems involving approximate counting and/or social and semantic networks, but he is interested in anything involving some combination of algorithms, graphs, and probability.