The slime mold Physarum can compute shortest paths and construct nice networks

21^st September 2016, 13:00 Ashton Lecture Theatre
Professor Dr. Kurt Mehlhorn
Max Planck Institute

Abstract

Physarum is a slime mold. It was observed over the past 15 years that the mold is able to solve shortest path problems and to construct nice networks (Nakagaki-Yamada-Toth,Tero-Takagi-et al). In a nutshell, the shortest path experiment is as follows: A maze is built and the mold is made to cover the entire maze. Food is then provided at two positions and the evolution of the slime is observed. Over time, the slime retracts to the shortest path connecting the two food sources. A video showing the experiment is available at http://people.mpi-inf.mpg.de/~mehlhorn/ftp/SlimeAusschnitt.webm

A mathematical model of the slime's dynamic behavior was proposed by Tero-Kobayashi-Nakagaki. Extensive computer simulations confirm the experimental findings; the slime retracts to the shortest path. We (joint work with Vincenzo Bonifaci and Girish Varma) have have proved convergence (Journal of Theoretical Biology, 2012, ICALP 2013) of the continuous model and its discretization.

I will start with the video mentioned above. Then I review the mathematical model and explain the computer simulation. Next, I will discuss how we formulated the right conjecture based on computer experiments. Finally, I will briefly discuss the convergence proof.

In the second part of the talk, I will discuss follow-up work by Straszak and Vishnoi (ITCS 2016) and the slime ability to construct networks. I will close with some open problem. Some canonical auction scenarios -- involving simultaneous markets or dynamic trading, for example -- are descriptively simple yet resist analytical game-theoretic solution. We gain traction on such problems by combining simulation, search, and machine learning with game-theoretic reasoning, in an approach we call "empirical game-theoretic analysis". EGTA studies have produced strategic insights and improved strategies for simultaneous ascending auctions and continuous double auctions, as well as the more complex domains presented by a series of Trading Agent Competition events. Our most recent investigation, of simultaneous one-shot auctions, demonstrates the utility of EGTA for suggesting and evaluating theoretical characterizations of equilibrium bidding strategies.

Biography

Professor Dr. Kurt Mehlhorn (born 1949) is a world-wide Top-Leader in Theoretical Computer Science.
Professor Mehlhorn is currently the Director of the Max Planck Institute for Computer Science and also Professor in the Computer Science Dept. of the Universitat des Saarlandes in Germany. He has been a Vice President of the Max Planck Society.

Professor Dr. Kurt Mehlhorn is a Fellow of EATCS and of ACM. He is also a Member of Academia Europaea and of the Leopoldina National Academy of Germany.
He has been awarded the ACM Paris Kanellakis Theory and Practice Award , the EATCS award (2010) , the Leibnitz Award and the Humboldt Award. He has also received the prestigious Erasmus Medal of Academia Europaea and many other awards.
Kurt Mehlhorn is the co-creator of the LEDA programming language and the originator of the field of Algorithmic Engineering.

Additional Materials

• http://people.mpi-inf.mpg.de/~mehlhorn/ftp/SlimeAusschnitt.webm