THE REES DISTINGUISHED LECTURER SERIES

Professor Joel Spencer

 Computer Science Department at NYU

"Erdos Magic"

Thursday October 16, 2003

3:30 - 4:30 118 Purnell Hall

The probabilistic method is a lasting legacy of the late Paul Erdos. We show through several examples how one can prove the existence of an object (e.g.: coloring, game strategy, independent set) by analyzing an appropriately defined randomized algorithm that attempts to find that object. The Magic: When the randomized algorithm has positive probability of success then the object absolutely positively much exist!

 

"Liar"

Friday October 17, 2003

3:30 - 4:30 104 Gore Hall

Paul tries to find a number from 1 to n by asking q questions from Carole. The kicker: Carole is allowed to lie, but at most k times. (Try it with n=100, q=10, k-1!). What is the largest n for which Paul will win. This problem, which may be viewed as coding theory with feedback, has a surprisingly precise result for k fixed. In more recent work, we restrict Carole to a half-lie, no may be answered yes but yes must be answered yes. We discuss joint work on this “Z channel” with Ioana Dumitriu and Catherine Yan. The methods involve linear algebra and combinatorics.

Refreshments served immediately after talk in Ewing 436.