Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Tuesday, December 06, 2016, 12:15 pm

Duration: 45 minutes

Location: OAT S15/S16/S17

Speaker: Fabio Banfi

Ant-Inspired Density Estimation via Random Walks

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login