Exponential separation of information and communication for Boolean functions
DOI10.1145/2907939zbMATH Open1412.68082OpenAlexW2556081204MaRDI QIDQ5895073FDOQ5895073
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
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
communication complexitydirect sumamortized communication complexityinformation 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)
Cited In (11)
- The communication complexity of functions with large outputs
- Title not available (Why is that?)
- Relative Discrepancy Does not Separate Information and Communication Complexity
- Query-to-Communication Lifting Using Low-Discrepancy Gadgets
- Exponential Separation of Communication and External Information
- The landscape of communication complexity classes
- Canalizing Boolean Functions Maximize Mutual Information
- Communication and information complexity
- The work of Mark Braverman
- Title not available (Why is that?)
- Exponential Separation of Information and Communication for Boolean Functions
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)
