Improved direct sum theorem in classical communication complexity

2005/04/19 by Rahul Jain, Jain, Rahul
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Other Computer Science (cs.OH) #cs.OH #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.cs/0504087

Withdrawn due to critical error

openalex publication_date 2005/04/19 · arxiv created 2005/04/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Withdrawn due to critical error.

Related

• Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
• Communication Complexity
• A direct sum theorem in communication complexity via message compression
• A near-optimal direct-sum theorem for communication complexity
• Direct Sum Theorems From Fortification