Trading information complexity for error

DOI10.4086/TOC.2018.V014A006MaRDI QIDQ4568116zbMATH OpenOpenAlexFDO

Authors Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li

Publication date 15 June 2018

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

communication complexityinformation complexity

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• scientific article; zbMATH DE number 7204267
• From information to exact communication
• Interactive information complexity
• Interactive Information Complexity
• Interactive information complexity

Cites work

• A Mathematical Theory of Communication
• A strong direct product theorem for disjointness
• Amortized Communication Complexity
• An information statistics approach to data stream and communication complexity
• Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching
• Communication complexity theory: thirty-five years of set disjointness
• Direct product via round-preserving compression
• Exponential separation of information and communication for Boolean functions
• How to compress interactive communication
• scientific article; zbMATH DE number 2038719 (Why is no real title available?)
• scientific article; zbMATH DE number 7204267 (Why is no real title available?)
• Information complexity is computable
• Information Equals Amortized Communication
• Information lower bounds via self-reducibility
• Interactive Information Complexity
• New strong direct product results in communication complexity
• On the distributional complexity of disjointness
• Some Results on Distributed Source Coding for Interactive Function Computation
• The Communication Complexity of Correlation
• The Infinite-Message Limit of Two-Terminal Interactive Source Coding
• The Probabilistic Communication Complexity of Set Intersection

Cited in

(6)

• Trading information complexity for error. II: The case of a large error and the external information complexity
• Communication complexity with small advantage
• scientific article; zbMATH DE number 7204267 (Why is no real title available?)
• scientific article; zbMATH DE number 7250149 (Why is no real title available?)
• From information to exact communication
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)

This page was built for publication: Trading information complexity for error

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