Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan:
Private Information Retrieval
Private Information Retrieval
This remarkable paper introduced a fundamental primitive in the field of cryptography: how to query a data base fully preserving the privacy of the query. The work introduced the notion of private information retrieval (PIR), gave the first protocols that allow users to retrieve items from distributed databases without revealing which item — thereby founding a new subfield at the intersection of cryptography, information theory, and complexity theory. Its definitions and constructions have shaped decades of research, enabled practical variants, and remain a cornerstone for privacy-preserving data access.
Peter Auer, Nicoló Cesa-Bianchi, Yoav Freund, Robert Schapire:
Gambling in a rigged casino: The adversarial multi-armed bandit problem
Gambling in a rigged casino: The adversarial multi-armed bandit problem
This paper introduced the adversarial multi-armed bandit as well as (what later become known as) the contextual bandit problems, deviating from the online decision-making tradition that made stochastic assumptions about the sequence of decisions. The paper provided the first algorithms achieving sub-linear regret for these problems and a tight lower bound for the smallest attainable regret, introducing some key algorithmic and lower bounding techniques that continue to inspire contemporary developments. By showing that robust performance guarantees are feasible even when payoffs are chosen by an adversary, the paper has had a profound influence in the theory and practice of algorithms in settings ranging from the more benign to the more worst-case, including reinforcement learning, online convex optimization, game theory and multi-agent learning. Meanwhile, contextual bandits now constitute the algorithmic underpinnings of personalization in online content recommendations and display advertising, and are increasingly being applied in health care.