A direct sum theorem in communication complexity via message compression

DOI10.1007/3-540-45061-0_26MaRDI QIDQ4449184zbMATH OpenFDO

Authors Rahul Jain, Pranab Sen, Jaikumar Radhakrishnan

Publication date 8 February 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2719/27190300.htm

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

Recommendations

• scientific article; zbMATH DE number 1421021
• Composition theorems in communication complexity
• Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching
• On the Compression of Messages in the Multi-Party Setting
• Communication complexity of sum-type functions invariant under translation
• On a communication complexity problem in combinatorial number theory
• Kolmogorov Complexity and Combinatorial Methods in Communication Complexity
• Kolmogorov complexity and combinatorial methods in communication complexity
• An algebraic approach to communication complexity
• Two-way communication complexity of sum-type functions for one processor to be informed

Cited in

(32)

• The direct sum of universal relations
• Simulation theorems via pseudo-random properties
• Lower bounds for predecessor searching in the cell probe model
• New strong direct product results in communication complexity
• How to compress interactive communication
• How to compress interactive communication
• Quantum information complexity
• Direct sum fails for zero error average communication
• Superlinear lower bounds for multipass graph processing
• A direct product theorem for two-party bounded-round public-coin communication complexity
• Towards a reverse Newman's theorem in interactive information complexity
• Direct sum fails for zero-error average communication
• Relative discrepancy does not separate information and communication complexity
• Lower bounds on information complexity via zero-communication protocols and applications
• Interactive Information Complexity
• Trading information complexity for error
• Interactive information complexity
• Compressing interactive communication under product distributions
• scientific article; zbMATH DE number 1421021 (Why is no real title available?)
• Lifting Theorems for Equality
• Direct product via round-preserving compression
• Communication Lower Bounds Via the Chromatic Number
• Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching
• Compressed communication complexity of longest common prefixes
• Two-party direct-sum questions through the lens of multiparty communication complexity
• Information dissemination via broadcasts in the presence of adversarial noise
• Ning Cai's work on communication complexity
• Channel simulation: theory and applications to lossy compression and differential privacy
• Quantum broadcast channel simulation via multipartite convex splitting
• Direct sums for parity decision trees
• Choosing, agreeing, and eliminating in communication complexity
• A characterization of average case communication complexity

This page was built for publication: A direct sum theorem in communication complexity via message compression

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