David Wajc

Matching Theory under Uncertainty Degree Type: Ph.D. in Computer Science
Advisor(s): Bernhard Haeupler
Graduated: August 2020

Abstract:

Traditionally, optimization in computer science has been studied in the full information setting: data is collected, a program is run, and then the output is used. However, the increasing pervasiveness of user-facing applications is increasingly shifting the focus to computation under incomplete information: data is generated continuously by users, who expect their new data to quickly affect the externalized solution. This modern computational paradigm motivates a renewed interest in computation under uncertainty (about the input), including online, dynamic and streaming algorithms.

Many problems providing the renewed impetus for studying algorithms under uncertainty come from the field of matching theory–the study of pairing agents/items. Examples abound, arising ind is parate applications, from ride-sharing apps, to Internet advertising, to online gaming. This motivates the study of matching theory under uncertainty. Moreover, the study of matching theory has historically played a key role in the development of immensely influential techniques for computation more broadly. An additional motivation for studying matching theory under uncertainty, then, is its potential to provide similar fundamental insights for computation under uncertainty more broadly.

In this thesis we answer several longstanding open problems in the area of matching theory under uncertainty, and hint at some methods with potential broader applicability to computation under uncertainty. This again illustrates the pivotal role of matching theory, this time in modern settings. In Part I, we study online algorithms; here, the input is revealed in parts, in some adversarial order, in the form of requests, to which we must respond immediately and irrevocably. In Part II, we study online algorithms under structural and stochastic assumptions which are motivated by information about practical inputs of interest, allowing for better guarantees than possible for worst-case inputs. Finally, in Part III, we study dynamic algorithms, where the input is constantly changing, and the algorithm's choices, while not irrevocable, must be quick; in the same part, we study streaming algorithms, motivated by big-data applications, where choices are not irrevocable, but are restricted to only using a limited amount of memory compared to the (massive) input size.

Thesis Committee:
Bernhard Haeupler (Chair)
Anupam Gupta
R. Ravi
Cliff Stein (Columbia University)
Ova Svensson (École Polytechnique Fédérale de Lausanne - EPFL)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Keywords:
Matching, Matching Theory, Uncertainty, Online Algorithms, Dynamic Algorithms, Streaming Algorithms