Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Direct Sum Fails for Zero Error Average Communication
Speaker:Shay Moran
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Lecture
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 11 March 2014
Please note: New Time!
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
We show that in the model of zero error communication complexity,

direct sum fails for average communication complexity
as well as for external information cost.
Our example also refutes
a version of a conjecture by Braverman et al that
in the zero error case amortized communication complexity equals external information cost.

In our examples the underlying distributions do not have full support.
One interpretation of a distributions of non full support is as a promise
given to the players (the players have a guarantee on their inputs).
This brings up the issue of promise versus non-promise problems
in this context.

Joint work with Gillat Kol, Amir Shpilka and Amir Yehudayoff

Contact
Name(s):Shay Moran
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Shay Moran, 03/10/2014 12:29 PM
  • Shay Moran, 03/08/2014 03:56 PM -- Created document.