Swarthmore College Department of Computer Science

Talk by Jeff Kinne, University of Wisconsin Madison

Finding Hay in a Haystack - Randomized Algorithms
Monday, February 15, 2010
SCI 240, 4:00 pm (cookies at 3:45)

Abstract

This talk focuses on the power of randomized algorithms. Randomness is a powerful algorithm design technique. Many important problems can be solved by randomized algorithms that are either much more efficient or much simpler to implement than the best-known deterministic algorithms (algorithms that do not use randomness).

In the first half of the talk, we look at a problem - selecting the k-th smallest number out of an unsorted list -- that can provably be solved more efficiently by randomized than deterministic algorithms. We look at a classic simple randomized algorithm that solves the problem using O(n) comparisons. This portion of the talk is aimed at anyone who has at least taken CS 21 Intro to Computer Science.

In the second half of the talk, I discuss my own research on the power of randomized algorithms. There are some problems where there is an exponential gap between the best-known deterministic and randomized algorithms. A major open question is whether these randomized algorithms can be "derandomized" - converted into deterministic algorithms without too much loss in efficiency. A widely-held conjecture states that randomized algorithms can be derandomized. I will discuss the best-known results in this direction and some motivation for the conjecture. An exciting new approach that is part of my work derandomizes a number of classes of randomized algorithms by considering "typically-correct" derandomization - efficient deterministic simulations that are allowed to make a small number of mistakes.