# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

On 5.4.2012 at 12:20 in S6, there is the following noon lecture:

# Coalescing Balls and Bins

## Jarett Schwartz

## Abstract

We analyze a process, motivated by a distributed algorithm from a system at Microsoft Research where n singleton bins merge until we have d bins. After relating this process to the Kingman Coalescent process from evolutionary biology and random compositions with d parts, we find a closed form for the expected maximum bin size for constant d, as n tends to infinity. Then, we present results for various choices of d = f(n). If time allows, we will propose problems relating to extensions to this process ("waking" bins, power of two choices, etc.).

This is joint work with Siddhartha Sen.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

Webmaster: kamweb.mff.cuni.cz Archive page