BARC/EADS Talk by Petteri Kaski

On Friday 15 June 2018 , assistant professor Petteri Kaski from Aalto University, Helsinki, Finland will give a talk at BARC.

Titel

How proofs are prepared at Camelot

Abstract

This talk looks at algorithm designs that (a) tolerate silent hardware errors and (b) prepare a correctness proof that can be checked probabilistically with substantially less resources than it takes to solve the problem with the asymptotically fastest known algorithms. Our starting point is a framework of Williams [CCC'16] for noninteractive Merlin--Arthur proofs of batch evaluation, which we [PODC'16] extend with the observation that Merlin's magic is not needed: mere Knights can prepare the proof, in parallel, and with intrinsic error-correction. This design framework captures with multiplicative polylogarithmic overhead in the total running time the fastest known algorithms for a number of hard problems ranging from computing the chromatic polynomial of a graph to counting k-cliques. We will also discuss our recent proof-of-concept implementation of the framework on NVIDIA GPUs [ALENEX'18].

This is joint work with Andreas Björklund (Lund University).

Bio

Petteri Kaski is an Assistant Professor in the Department of Computer Science, Aalto University, Helsinki, Finland. His current research interests lie in theory and engineering of exact algorithms for search and enumeration problems, ranging from algebraic techniques for pattern search in graphs to classification problems in combinatorics. He is the recipient of a Kirkman Medal awarded by the Institute of Combinatorics and Its Applications, and a Young Researcher Prize awarded by the Finnish Foundation for Technology Promotion.