Exponential Separation of Information and Communication for Boolean Functions
From MaRDI portal
Publication:5895073
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
information complexitycommunication complexitydirect sumamortized communication complexitycommunication compression
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
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
