Direct sum fails for zero-error average communication

DOI10.1007/s00453-016-0144-9zbMath1353.68092OpenAlexW2332880008MaRDI QIDQ343859

Amir Shpilka, Gillat Kol, Amir Yehudayoff, Shay Moran

Publication date: 29 November 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0144-9

zbMATH Keywords

information complexitycommunication complexityamortized communication complexityexternal informationpromise problems

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cites Work

• Unnamed Item
• New Strong Direct Product Results in Communication Complexity
• How to Compress Interactive Communication
• A strong direct product theorem for disjointness
• Certifying Equality With Limited Interaction.
• Interactive Information Complexity
• Amortized Communication Complexity
• Communication Complexity
• The Communication Complexity of Correlation
• Information Equals Amortized Communication
• From information to exact communication

This page was built for publication: Direct sum fails for zero-error average communication