Robust Algorithms in the Face of Uncertainty

Algorithms for optimization and decision-making face many sources of uncertainty: inputs that change over time, are too large to read or store, or are held by strategic agents. We will cover different models of uncertainty, as well as techniques for coping with it. In particular, we will focus on robust algorithms that provide meaningful guarantees such as competitive ratio and regret analysis even when the uncertainty cannot be resolved by learning a reliable model. Sample topics include online algorithms and learning, streaming algorithms, and sublinear-time algorithms. Prerequisite: CS161.