COLLOQUIUM
Department of Computer Science and Engineering
University of South Carolina
 
Multiparty Communication Complexity

William Gasarch

Department of Computer Science
University of Maryland at College Park

Date: April 2, 2008
Time: 1430-1530
Place: Swearingen 1A03 (Faculty Lounge)

Abstract

Imagine that there are k people in a room and they each have on their
forehead a number between 0 and n.  Each person can see the other
people's numbers, but not theirs.  They want to know if the sum of all
of the numbers is divisible by n. Player 1 could just say "HEY,
PLAYER II, YOUR NUMBER IS BLAH BLAH," and then player 2 can determine
the answer.  This would take log2(n) bits of communication.  Can they
do better?  How well can they do?

Come and find out!

William (Bill) Gasarch holds the title of Full Professor in the newly
formed Department of Computer Science at the University of Maryland at
College Park. He received the BS degree in Mathematics and Computer
Science from the State University of New York at Stonybrook in 1980,
the MS degree in Applied Mathematics from Harvard University in 1982,
and the Ph.D. degree in Computer Science from Harvard University in
1985, with a thesis entitled "Recursion-Theoretic Techniques in
Complexity Theory and Combinatorics." He has been at the University
of Maryland at College Park since 1985. His main interests are
Complexity Theory and Combinatorics.  He runs a complexity blog and
has the worlds largest collection of Bob Dylan satires.