[Colloquium] Kant/M.S. Presentation/July 22, 2005

[Margaret Jaffey]

This is an announcement of Ravi Kant's Master's Presentation.

----------------------------
Date:  Friday, July 22, 2005

Time:  11:30 a.m.

Place:  Ryerson 277

M.S. Candidate:  Ravi Kant

M.S. Paper Title:  Multiparty Quantum Communication

Abstract:
We introduce a quantum version of the multiparty communication game of
Chandra, Furst and Lipton. This is the quantum analogue of the "number 
on
the forehead" model in which the communicating parties are allowed to
exchange qubits. We show that the quantum model is at least as strong as
its clasical counterpart. We show that the complexity of almost all
functions in this model is \Omega(n). This holds true even in the 
bounded
error version of the game. We also briefly describe a recent 
simultaneous
messages model of quantum communication introduced by Kerenidis and show
that our lower bound for almost all functions holds in this model as 
well.

Advisor: Prof. Laszlo Babai

A draft copy of Ravi Kant's MS Paper is available in Ry 161A.

-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Margaret P. Jaffey				margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 161A)		(773) 702-6011
The University of Chicago		http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-