2026/08/04 by Daiki Suruga
Computer Science · Mathematics · #cs.CC #cs.IT #math.IT
arxiv created 2026/08/04 · arxiv updated 2026/08/06
The direct sum problem in computational complexity asks whether solving n independent instances of a computational task inherently requires n times the resources needed to solve a single instance. In this paper, we resolve a central form of the direct sum conjecture in randomized communication complexity. Specifically, we prove that the "amortized expected randomized communication complexity" of any function is exactly equal to its "zero-error information complexity"---a measure of the precise amount of information the communicating parties must reveal about their inputs to compute the function without error. This result also provides a tight characterization of the amortized "worst-case" randomized communication complexity up to a constant factor. To achieve our exact characterization, we introduce a new single-instance protocol embedding equipped with a prefix-verification mechanism to accurately localize global errors. Furthermore, we apply our new structural theorems to the fundamental Set-Disjointness problem. Our resulting exact asymptotic bounds for Set-Disjointness successfully refute a conjecture in DFHL18 regarding its scaling behavior.