Joel Rybicki is a visiting Ph.D. student from Aalto University. He works on algorithm synthesis and distributed computing. His advisor is Jukka Suomela.

AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

MPI Audience

English

30 Minutes

Saarbrücken

We study the task of finding large cuts in d-regular triangle-free graphs. We give a new randomised algorithm that finds a cut with a large expected size. As a corollary, this shows that any d-regular triangle-free grpah has a cut of certain size. The algorithm can be interpreted as a very efficient randomised distributed algorithm: each node needs to produce only one random bit and the algorithm runs in one synchronous communication round. Finally, this work is an example of computational algorithm design: the algorithm was designed by a computer program.

This is joint work with Juho Hirvonen, Stefan Schmid and Jukka Suomela.

Christoph Lenzen

--email hidden

passcode not visible

logged in users only