Direct product via round-preserving compression

DOI10.1007/978-3-642-39206-1_20zbMATH Open1336.68086OpenAlexW190822590MaRDI QIDQ5326564FDOQ5326564

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

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

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)

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
• Title not available (Why is that?)
• 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)