Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, December 06, 2016, 12:15 pm
Duration: 45 minutes
Location: OAT S15/S16/S17
Speaker: Fabio Banfi
We will present the paper "Ant-Inspired Density Estimation via Random Walks" by Musco, Su, and Lynch (2016). We know that ants can estimate the density of their population to perform several important tasks. The central question of this work is: how can they achieve this accurately by only sampling the density of their local environment over time? We present a simplified model of ants performing a round-based random walk on a torus which allows studying the problem from a theoretical perspective. In each round, every ant updates a counter which keeps track of the total number of collisions with other ants so far. It is easy to show that this counting leads to an unbiased estimate of the density if the ants are uniformly distributed at the start of the process. The main result of the paper is that the estimate is concentrated around its expectation. In this talk, we will expose some of the novel techniques introduced by the authors to prove the main result.
Automatic MiSe System Software Version 1.4803M | admin login