LFCS Seminar: Andrew Drucker: Confident predictions against an adversary
Andy Drucker, University of Edinburgh. Confident predictions against an adversary.
What 


When 
Mar 17, 2015 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Add event to calendar 
vCal iCal 
Abstract: We study the setting in which the bits of an unknown infinite binary sequence x are revealed sequentially to an observer. We show that quite limited assumptions about x allow one to make nontrivial predictions about unseen bits.
Our main focus is the task of predicting a single 0 from among the bits of x, at a time of our choosing. This models various situations in which we must perform an action of fixed duration, and must predict a "safe" time to perform it. We give a randomized algorithm that succeeds (with high probability) against any sequence x whose 1s are sufficiently sparse in the limit. Subject to this mild condition, the sequence need not be generated according to a known probabilistic model, but may be chosen adversarially.
Reference:
[A. Drucker, Highconfidence predictions under adversarial uncertainty. ITCS'12/TOCT'13]