BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Balanced Allocations: The Power of Choice versus Noise - Dr Thomas
  Sauerwald - Department of Computer Science and Technology
DTSTART:20220601T140500Z
DTEND:20220601T145500Z
UID:TALK173723@talks.cam.ac.uk
CONTACT:Ben Karniely
DESCRIPTION:In the balanced allocation problem we wish to allocate m balls
  (jobs) into n bins (servers) by allowing each ball to choose from some bi
 ns sampled uniformly at random. The goal is to maintain a small gap betwee
 n the maximum load and average load. For the one-choice protocol\, where e
 ach ball is allocated to a random bin\, the gap diverges for large m. Howe
 ver\, for the two-choice protocol\, where each ball samples two bins and i
 s placed in the least loaded of the two\, it was shown that gap is only O(
 log log n) for all m. This dramatic improvement is widely known as ``power
  of two choices''\, and similar effects have been observed in hashing and 
 routing. \n\nIn this talk\, we will first give some intuition why two-choi
 ce maintains such a good balance in practice and theory. Then we will pres
 ent our recent results in settings where the load information is subject t
 o some noise. For example\, the queried load information of bins might be 
 (i) outdated\, (ii) subject to some adversarial or random perturbation or 
 (iii) only retrievable by binary queries. We prove that\, roughly speaking
 \, if the noise is not too strong\, then performance is not affected and t
 he O(log log n) gap bound of two-choice still holds. We also exhibit setti
 ngs with strong noise and show that having more choices can lead to a wors
 e performance.\n\nThis is based on joint work with Dimitrios Los.\n\n\nLin
 k to join virtually: https://cl-cam-ac-uk.zoom.us/j/97767639783?pwd=T09GcV
 JxZUNEUFEvRnZnbWwxeEwzQT09\n\nA recording of this talk is available to Uni
 versity of Cambridge members at the following link: https://www.cl.cam.ac.
 uk/seminars/wednesday/video/
LOCATION:Lecture Theatre 1\, Computer Laboratory\, William Gates Building
END:VEVENT
END:VCALENDAR