Adam Kalai (Massachusetts Institute of Technology):
Efficiency and Simplicity via Randomness
Randomized algorithms are often simpler and more efficient than their
deterministic counterparts. We first illustrate this with elementary
randomized algorithms for classic problems. We then focus on online
algorithms, i.e. algorithms that adapt to an unknown environment. In many
such cases, randomness is provably necessary for good online performance.
In other cases, randomization can be used surprisingly to analyze
deterministic algorithms. We also present an intuitive and efficient
randomized algorithm with optimal guarantees for a range of online
problems.
Some of the entertaining problems that we discuss are: pattern matching
with wildcards, the online driving-to-work problem, and online portfolios.