Exponential Separation of Information and Communication for Boolean Functions

DOI10.1145/2907939zbMath1412.68082OpenAlexW2556081204MaRDI QIDQ5895073

Gillat Kol, Anat Ganor, Ran Raz

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2907939

zbMATH Keywords

information complexitycommunication complexitydirect sumamortized communication complexitycommunication compression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Related Items (9)

Relative Discrepancy Does not Separate Information and Communication Complexity ⋮ The landscape of communication complexity classes ⋮ The communication complexity of functions with large outputs ⋮ The work of Mark Braverman ⋮ Communication and information complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Exponential Separation of Communication and External Information ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets

This page was built for publication: Exponential Separation of Information and Communication for Boolean Functions