Theory days

Estonia-Latvia

Invited talk by Jukka Suomela

Understanding computation via computation

abstract: As theoretical computer scientists, we seek to understand what can be automated, but what do we know about automating our own work? Is it possible for us to outsource our own research questions to computers?

In this talk I will survey some of our recent success stories related to the use of computational techniques in the study of algorithms and computational complexity. My focus will be on the theory of distributed computing; the models of distributed computing appear to be particularly well-suited for computational investigations.

I will give examples of distributed algorithms that were designed or co-designed by computers and that far outperform any previous human-designed algorithms. I will describe some meta-algorithmic techniques - how to design algorithms for designing algorithms - and we will also see an example of how to use computers to discover lower bound proofs.

Relevant papers

http://arxiv.org/abs/1702.05456 (PODC 2017) http://arxiv.org/abs/1502.04963 (SIROCCO 2015) http://arxiv.org/abs/1304.5719 (J. Comput. Syst. Sci. 2016) http://arxiv.org/abs/1402.2543

bio

Jukka Suomela (http://users.ics.aalto.fi/suomela/) is an Assistant Professor in the Department of Computer Science at Aalto University. His work focuses on the theoretical foundations of distributed computing, with particular emphasis on the concept of locality. He is a member of the steering committees of DISC, SIROCCO, and ADGA and a member of the council of EATCS, he has recently served in the programme committees of e.g. ICALP 2017, DISC 2017, and PODC 2016, and he is one of the local chairs of ALGO 2018.