[Colloquium] Gasarch Talk Today at 3:00 p.m.

[Margaret Jaffey]

Note: The start time for William Gasarch's talk this afternoon has  
been changed to 3:00 p.m.


             Department of Computer Science/The University of Chicago

                     S E M I N A R   A N N O U N C E M E N T


Date:  Friday, November 4, 2005

Time:  3:00 p.m.

Location:  Ryerson 251

Guest Speaker:  William Gasarch from the University of Maryland at  
College Park

Talk Title:  Communication Complexity of Hamming Distance

Abstract:
Alice and Bob want to know if two strings of length $n$ are almost  
equal. That is, do they differ on at most $a$ bits? We are concerned  
with how many bits they must communicate to determine this.
We show that 1) If $0\le a\le O(\sqrt n)$ then any deterministic  
protocol for this problem requires at least $n$ bits. 2) If $0\le a 
\le n-1$ then any deterministic protocol for this problem requiers at  
least $n-2$ bits.
Our results are obtained by lower-bounding the ranks of the  
appropriate matrices. Hence our lower bounds also apply to some  
quantum communication complexity models.

Speaker's host: Lance Fortnow

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=