Exponential separation of information and communication for Boolean functions

DOI10.1145/2907939zbMATH Open1412.68082OpenAlexW2556081204MaRDI QIDQ5895073FDOQ5895073

Authors: Anat Ganor, Gillat Kol, 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

Recommendations

• Exponential Separation of Information and Communication for Boolean Functions
• Exponential separation of communication and external information
• Relative discrepancy does not separate information and communication complexity
• Exponential separation of communication and external information
• Relative discrepancy does not separate information and communication complexity

zbMATH Keywords

communication complexitydirect sumamortized communication complexityinformation 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)

Cited In (16)

• Trading information complexity for error
• The communication complexity of functions with large outputs
• Exponential separation of communication and external information
• The landscape of communication complexity classes
• Canalizing Boolean Functions Maximize Mutual Information
• Simplified separation of information and communication
• Communication complexity under product and nonproduct distributions
• Query-to-communication lifting using low-discrepancy gadgets
• Sign rank vs discrepancy
• Communication and information complexity
• The work of Mark Braverman
• Exponential Separation of Information and Communication for Boolean Functions
• Exponential separation of communication and external information
• Relative discrepancy does not separate information and communication complexity
• Lower bounds on information complexity via zero-communication protocols and applications
• Relative discrepancy does not separate information and communication complexity

This page was built for publication: Exponential separation of information and communication for Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5895073)