Open Lecture — Algorithm Design in the Modern Era: Dealing with Uncertainty and Incentives

In the good old days, algorithms research was quite simple, at least in terms of its socio-economic context: a problem was formulated, usually by application demand, and an algorithm was designed to solve it correctly and efficiently on a single computer. This was all under the assumptions that accurate inputs were readily available, and that what mattered was that the problem was solved efficiently in the worst-case. Instead, we now collect massive amounts of data that allow us to predict, at least stochastically, what inputs we will actually need to handle. On the other hand, this data is often supplied by users with an economic goal, who may have an incentive to provide inaccurate inputs if that will yield a more beneficial output from their perspective. In this talk, we survey a few of the algorithmic gems, challenges and connections that have emerged as a result of these changes.

Light refreshments will be served before the lecture at 3:30 p.m.