Time+Place: Tuesday 05/05/2015 14:30 Room 337-8 Taub Bld.
Title: Oblivious Algorithms - How to Serve in the Dark
Speaker: Yossi Azar - Colloquium Lecture http://www.cs.tau.ac.il/~azar/
Affiliation: Blavatnik School of Computer Science, Tel-Aviv University
Host: Erez Petrank

Abstract:

 
How much an algorithm needs to know on the input ? We survey oblivious
algorithms in the literature (algorithms that weakly depend on the input!).
Then we study an example of an oblivious algorithm for some balls and bins
game. Specifically an algorithm which serves in the dark without any
feedback at all, i.e., does not see the sequence, the content of the bins,
and even the results of its actions. We compare its gain to the gain of an
optimal, open eyes, strategy that gets the same input sequence.
Surprisingly, we show that although no information is ever provided to the
algorithm, choosing an action using non-uniform probability distribution
improves its performance over the uniform choice. Finally, we present an
application relating to a mechanism for bounded capacity auctions.

The talk is based on papers joint with Ilan R. Cohen (2015) and Ilan R.
Cohen and Iftah Gamzu (2013). The first 75% of the talk is oriented towards
a general computer science audience.

Short BIO:

Yossi Azar is a Professor at the Blavatnik School of Computer Science in
Tel-Aviv university. He received his Ph.D. from Tel-Aviv University in 1989.
He spent several years in Stanford, DEC and IBM in California and joined
Tel-Aviv university in 1994. Between 2002-2004 Yossi was the chair of the
department of Computer Science and then in 2006-2009 he was in Microsoft
Research in Redmond. Between 2011-2014 Yossi was the head of the school of
Computer Science in Tel Aviv university. His research interests include
design and analysis of algorithms, especially related to online,
approximation and algorithmic game theory. 


Desserts will be served from 14:15
Lecture starts at 14:30