ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

Direct Sum Fails for Zero-Error Average Communication (2016)

Springer

In: Algorithmica

add to mindlist on the mindlist

Details

Publication Date: 2016-03-29

Description: We show that in the model of zero-error communication complexity, direct sum fails for average communication complexity as well as for external information complexity. 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 complexity. In our examples the underlying distributions do not have full support. One interpretation of a distribution 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.

Print ISSN: 0178-4617

Electronic ISSN: 1432-0541

Topics: Computer Science , Mathematics

Published by Springer

	Location	Call Number	Expected	Availability

Others were also interested in ...

PAPER CURRENT

S·F·X

Fulltext

hit 1 - 1 | 1 hit