Andrew Drucker
Tue 17 Mar 2015, 16:00 - 17:00
Informatics Forum (IF-4.31/4.33)

If you have a question about this talk, please contact: Rik Sarkar (rsarkar)

Speaker: Andrew Drucker, University of Edinburgh

    Title: Confident predictions against an adversary

    Venue: Tuesday March 17, 16:00, Room IF 4.31/4.33


Confident predictions against an adversary


Andrew Drucker


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.




[A. Drucker, High-confidence predictions under adversarial uncertainty.  ITCS'12/TOCT'13]