Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Andrew Drucker: Confident predictions against an adversary

LFCS Seminar: Andrew Drucker: Confident predictions against an adversary

— filed under:

Andy Drucker, University of Edinburgh. Confident predictions against an adversary.

What
  • LFCS Seminar
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, High-confidence predictions under adversarial uncertainty. ITCS'12/TOCT'13]

Document Actions