ColloquiaReminder: talk by Adam Kalai today 2:30

[Meridel Trimble]

--------------------------------------------------------------------------------
-------- 

TOYOTA TECHNOLOGICAL INSTITUTE 
--------------------------------------------------------------------------------
-------- 

Date: Wednesday, March 5th, 2003

Time: 2:30 p.m. 

Place: Ryerson Hall 251 

Speaker: Adam Kalai, M.I.T. 

Homepage:
http://www.mit.edu/~akalai/

Title: Efficiency and Simplicity via Randomness

Abstract: Randomized algorithms are often simpler and more efficient than their 
deterministic counterparts. We first illustrate this with elementary 
randomized algorithms for classic problems. For the remainder, we 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. Finally, we 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.

*Refreshments will be served after the talk in Ryerson 255*