scientific article; zbMATH DE number 7009619

DOI10.4086/toc.2018.v014a020zbMath1412.68060OpenAlexW2405665546MaRDI QIDQ4612484

No author found.

Publication date: 31 January 2019

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2018.v014a020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

information complexitycommunication complexityfooling distributionseparation of complexity measures

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (4)

The communication complexity of functions with large outputs ⋮ The work of Mark Braverman ⋮ On the Communication Complexity of Key-Agreement Protocols. ⋮ Exponential Separation of Communication and External Information

Cites Work

• Unnamed Item
• A Mathematical Theory of Communication
• A discrepancy lower bound for information complexity
• The communication complexity of addition
• An information statistics approach to data stream and communication complexity
• Some intersection theorems for ordered sets and graphs
• On the distributional complexity of disjointness
• How to Compress Interactive Communication
• Information Equals Amortized Communication
• Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
• Interactive Information Complexity
• The Probabilistic Communication Complexity of Set Intersection
• Computing with Noisy Information
• Compressing Interactive Communication Under Product Distributions
• Communication Complexity
• Relative Discrepancy Does Not Separate Information and Communication Complexity
• The Communication Complexity of Correlation
• Public vs Private Coin in Bounded-Round Information
• Exponential separation of communication and external information
• Interactive compression for product distributions
• Exponential Separation of Information and Communication for Boolean Functions

This page was built for publication: