Direct product via round-preserving compression

DOI10.1007/978-3-642-39206-1_20MaRDI QIDQ5326564zbMATH OpenOpenAlexFDO

Authors Mark Braverman, Anup Rao, O. Weinstein, Amir Yehudayoff

Publication date 6 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-39206-1_20

Mathematics Subject Classification ID

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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• A direct product theorem for two-party bounded-round public-coin communication complexity
• scientific article; zbMATH DE number 2038719
• How to compress interactive communication
• New strong direct product results in communication complexity
• How to compress interactive communication

Cited in

(11)

• Trading information complexity for error
• New strong direct product results in communication complexity
• Simulation theorems via pseudo-random properties
• Interactive Information Complexity
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• Interactive information complexity
• scientific article; zbMATH DE number 1559552 (Why is no real title available?)
• A direct product theorem for two-party bounded-round public-coin communication complexity
• Certifying equality with limited interaction
• Towards a reverse Newman's theorem in interactive information complexity
• Lifting Theorems for Equality

This page was built for publication: Direct product via round-preserving compression

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