[math-ias] FW: IAS TCS/DM Seminars -- Week of December 3, 3012

[Dottie Phares]

INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540
 
Theoretical Computer Science/Discrete Math Seminars
Week of December 3, 2012
 
 
 
 
Monday, December 3
 
Computer Science/Discrete Mathematics Seminar I
Topic:                    Information Complexity and Exact Communication
Bounds
Speaker:               Mark Braverman, Princeton University
Time/Room:         11:15am - 12:15pm/S-101
Abstract:               See below
 
 
 
Tuesday, December 4
 
Computer Science/Discrete Mathematics Seminar II
Topic:                    Delegation for Bounded Space
Speaker:               Ran Raz, Weizmann Institute; Member, School of
Mathematics
Time/Room:         10:30am - 12:30pm/S-101
 
 
 
 
               Information Complexity and Exact Communication Bounds
               Mark Braverman
 
In this talk we will discuss information complexity -- a measure of the
amount of information Alice
and Bob need to exchange to solve a problem over distributed inputs. We will
present an
information-theoretically optimal protocol for computing the AND of two bits
distributed between
Alice and Bob. We prove that the information complexity of AND is ~1.4923
bits. We use the optimal
protocol and its properties to obtain tight bounds for the Disjointness
problem, showing that the
randomized communication complexity of Disjointness on n bits is ~0.4827n ±
o(n).
Based on joint work with Ankit Gard, Denis Pankratov, and Omri Weinstein
 
 
 
Computer Science/Discrete Math Seminars can be found on our web page:






http://www.math.ias.edu/csdm
http://www.math.ias.edu

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/mailman/private/all/attachments/20121127/c2a39907/attachment-0002.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Dec03_CSDM.pdf
Type: application/pdf
Size: 2324 bytes
Desc: not available
URL: <http://imap.math.ias.edu/mailman/private/all/attachments/20121127/c2a39907/attachment-0002.pdf>