[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

THEORY SEMINAR

Tues., November 19, 2013
3:00 p.m.
Ryerson 251
 
Shachar Lovett
Univ. of California San Diego
cseweb.ucsd.edu/~slovett
 
 
 
Title: “Communication is bounded by root of rank”.
 
Abstract: The log rank conjecture is one of the fundamental open problems in communication complexity. It speculates that if for a boolean f(x,y), its associated matrix M_{x,y}=f(x,y) has rank r (over the reals), then there exists a deterministic protocol computing f which uses only poly-log(r) bits of communication. There is a trivial protocol which uses r bits of communication, and further progress on this problem reduced it to O(r) bits [Kotlov-Lovasz'96, Kotlov '97] and more recently to O(r/log(r)) bits assuming a number theoretic conjecture [BenSasson-L-RonZewi'12]. In this work, we prove an (unconditional) upper bound of O(r^{1/2} log(r)) bits.
 
 
Hosts: Prof. Razborov
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20131119/141b192e/attachment.htm