🔢 mathematics

Zero-error information equals amortized communication complexity

This paper resolves a central form of the direct sum conjecture in randomized communication complexity by proving that the amortized expected communication complexity of any function is exactly equal to its zero-error information complexity, a result achieved through a novel protocol embedding that also refutes a prior conjecture regarding the scaling behavior of Set-Disjointness.

Original authors: Daiki Suruga

Published 2026-08-06

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Daiki Suruga

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive puzzle, but instead of doing it alone, you have a friend on the other side of the world. You both have pieces of the picture, and you need to talk to each other to figure out the final image. In the world of computer science, this is called communication complexity. It's all about counting how many words (or bits of data) you need to exchange to solve a problem.

Now, imagine you don't just have one puzzle, but a million identical ones. The big question scientists have been asking for decades is: If solving one puzzle takes 10 words of conversation, does solving a million puzzles take exactly 10 million words? Or, is there a clever trick where you can "amortize" the cost—like buying in bulk—to get the job done with fewer words per puzzle? This is known as the Direct Sum Problem. It's a fundamental question about the limits of efficiency: Can we compress our conversations when we do things in bulk, or is the universe strictly linear?

For a long time, the answer seemed to be "it depends," and in some tricky scenarios, the answer was a surprising "no, you can't save that much." But a new paper by Daiki Suruga from the University of Waterloo has finally cracked the code for the most standard version of this problem. Suruga proves that the amount of information you must reveal to solve a task perfectly (with zero mistakes) is the exact ruler that measures how much you'll need to talk when solving millions of those tasks at once. It turns out that even if you are allowed to make a few mistakes overall, the "perfect" version of the task still dictates the cost.

The Big Discovery: The "Perfect" Blueprint

In this paper, Suruga tackles the Direct Sum problem in the world of randomized communication. This is a setting where Alice and Bob (the two friends solving the puzzle) are allowed to flip coins to help them decide what to say next, and they are allowed to make a small, controlled number of mistakes in their final answer.

The paper's main finding is a precise mathematical formula that connects two very different concepts: Communication Cost (how much they talk) and Information Complexity (how much they actually learn about each other's secrets).

Suruga proves that if you want to solve $n$ independent copies of a task $f$ with a total error rate of $\epsilon$ (meaning you might get the answer wrong on a few of the $n$ puzzles, but not too many), the average amount of talking you need per puzzle settles down to a specific number as $n$ gets huge. That number is exactly $(1 - \epsilon)$ times the Zero-Error Information Complexity of the single task.

Think of it like this: Imagine you are trying to guess a secret number. The "Zero-Error Information Complexity" is the absolute minimum amount of "clues" you need to reveal to be 100% sure of the number. Suruga shows that even if you are okay with being wrong 10% of the time (an error rate of 0.1), the cost of solving a billion puzzles isn't determined by the "10%-error" version of the task. Instead, it's determined by the "100%-perfect" version, just scaled down by the fact that you're allowed to fail 10% of the time. The formula is simple: Average Cost = (1 - Error Rate) × Perfect Information Cost.

Why This Changes the Rules

Before this paper, there was a lingering suspicion that maybe the "cost" of solving many puzzles was determined by the "cost" of solving one puzzle with the same error rate allowed. For example, if you allow a 10% error rate for one puzzle, maybe the bulk cost is based on that 10% version.

Suruga's work explicitly rules this out. The paper demonstrates that the "bulk" cost is actually tied to the zero-error version of the problem. This is a bit counterintuitive. It's like saying that even if you are playing a game where you can miss a few shots, the difficulty of playing a whole season is still dictated by how hard it is to hit a perfect shot every single time. The "perfect" version of the game sets the price tag for the whole season.

The paper also addresses a specific, famous problem called Set-Disjointness. This is a classic puzzle where Alice and Bob have lists of items, and they need to figure out if their lists share any common items. A previous study had made a guess (a conjecture) about how the communication cost for this problem would scale when solving many instances at once. Suruga's new formula proves that guess wrong. The scaling behavior is different than what was previously thought, correcting the mathematical record for one of the most important problems in this field.

How They Did It: The "Prefix Check" Trick

To prove this, Suruga invented a clever new way of simulating a single puzzle inside a massive batch of puzzles. Imagine you are trying to solve one puzzle, but you are actually part of a team solving a million.

The paper introduces a mechanism called prefix-verification. Here's how it works in the story:

Alice and Bob pick one random puzzle from the million to focus on.
They start simulating the solution for the entire million puzzles.
However, before they get to their chosen puzzle, they have to check if they got all the previous puzzles right.
If they made a mistake on any of the earlier puzzles, they immediately stop and say, "Abort! We messed up the prefix."
If they got everything right so far, they continue to their chosen puzzle.

This "Abort" signal is the key. It allows them to isolate errors. If the team makes a mistake early on, they stop talking, which saves a lot of communication. By mathematically analyzing how often they have to abort versus how often they succeed, Suruga showed that the "cost" of the whole batch is mathematically locked to the "zero-error" cost of a single instance.

The Bottom Line

This paper doesn't just suggest a trend; it provides a mathematical proof (a rigorous, step-by-step logical argument) that settles the question for the standard "global error" model. It tells us that the efficiency of solving many problems at once is strictly bounded by the information needed to solve one problem perfectly.

So, the next time you wonder if doing things in bulk saves you time or effort, remember Suruga's finding: In the world of computer communication, the "perfect" version of the task is the boss. Even if you are allowed to be a little less precise, the price you pay for the whole group is still set by the cost of being perfect, just discounted by how much error you're willing to accept. It's a precise, proven rule that finally closes the book on a decades-old debate about how computers talk to each other.

Technical Summary: Zero-error Information Equals Amortized Communication Complexity

1. Problem Statement

This paper addresses the direct sum problem in randomized communication complexity. The central question is whether solving $n$ independent instances of a computational task $f$ inherently requires $n$ times the resources needed to solve a single instance, or if "amortization" allows for savings. Specifically, the paper investigates the asymptotic behavior of the randomized communication complexity $R_\varepsilon(f^n)$ for $n$ instances of a relation $f$ under a global error model (where the total error probability over all $n$ instances is bounded by $\varepsilon$ ).

While previous work established that the direct sum conjecture fails under a per-instance error model (where each instance must have error $\le \varepsilon$ ), the status of the conjecture under the standard global error model remained open. The paper seeks to determine the precise asymptotic limit:
$\lim_{n \to \infty} \frac{R_\varepsilon(f^n)}{n}$

2. Methodology

The author employs a combination of information-theoretic tools and novel protocol constructions to establish tight lower and upper bounds.

2.1 Core Concepts

Zero-Error Information Complexity ( $IC_0(f)$ ): Defined as the minimum information cost required to compute $f$ with zero error, maximized over all input distributions.
Distributional Information Complexity: Measures the information revealed by a protocol transcript under a specific input distribution $\mu$ .
Asymmetric Information Complexity: A specialized measure ( $IC^{U_0}_{FP=0, FN \le \varepsilon}$ ) tailored for one-sided error constraints, focusing on distributions supported on 0-inputs.

2.2 Key Technical Innovations

Prefix-Verification Embedding: To prove lower bounds, the author introduces a new single-instance protocol embedding. Unlike standard embeddings that struggle to localize global errors, this method allows Alice and Bob to simulate an $n$ $n$ -instance protocol $\Pi_n$ $Π_{n}$ on a single coordinate $I$ $I$ chosen uniformly at random. Crucially, Bob actively verifies the correctness of the prefix (all instances $< I$ $< I$ ) during simulation.
- If the prefix is correct, the simulation continues.
- If an error is detected in the prefix, Bob sends an "Abort" signal.
- This mechanism ensures that the single-instance error is reduced to $O(\varepsilon/n)$ while bounding the abort probability by the global error $\varepsilon$ . This allows the author to relate the amortized cost of $n$ instances to the zero-error information complexity of a single instance.
Probabilistic Switching and Compression: For upper bounds, the author combines standard interactive message compression techniques (reducing communication to match information cost) with a probabilistic switching strategy. The protocol either halts immediately (with probability $\varepsilon$ ) or simulates $n$ copies of an optimal zero-error protocol (with probability $1-\varepsilon$ ).
Two-Step Strategy for Composition: For the composition of functions (specifically $OR_n \circ f$ ), the author utilizes a "Random Subsampling" followed by "Evaluating Skewed Inputs" strategy. This allows them to handle the asymmetry of false positives and false negatives by conditioning the input distribution on the absence of positive coordinates in the initial sample.

3. Key Contributions and Results

3.1 Exact Characterization of Amortized Expected Complexity

The paper establishes an exact asymptotic limit for the expected randomized communication complexity under a global error bound $\varepsilon$ .
Theorem 1: For any $\varepsilon \in (0, 1)$ and relation $f$ :
$\lim_{n \to \infty} \frac{R_\varepsilon(f^n)}{n} = (1 - \varepsilon) IC_0(f)$
This result demonstrates that the amortized cost is determined by the zero-error information complexity, not the $\varepsilon$ -error information complexity. The factor $(1-\varepsilon)$ arises because the protocol can afford to abort (or fail) with probability $\varepsilon$ , effectively reducing the "useful" communication load.

3.2 Bounds on Amortized Worst-Case Complexity

Building on the expected case, the author derives tight bounds for the standard worst-case randomized communication complexity.
Theorem 2:
$(1 - \varepsilon) IC_0(f) \le \liminf_{n \to \infty} \frac{R_\varepsilon(f^n)}{n} \le \limsup_{n \to \infty} \frac{R_\varepsilon(f^n)}{n} \le IC_0(f)$
Corollary 1: The amortized worst-case complexity is $\Theta(IC_0(f))$ .
This confirms that the direct sum conjecture (in the form $\Omega(n \cdot R_\varepsilon(f)) = R_\varepsilon(f^n)$ ) fails under the global error model for search problems (relational problems), as the amortized cost is strictly less than $n \cdot R_\varepsilon(f)$ due to the exponential separation between information and communication complexity established in prior work [GKR16a]. However, the paper explicitly notes that it remains an open question whether this failure extends to total functions, as no such separation is currently known for them.

3.3 One-Sided Error and Function Composition

The author extends their techniques to the composition $OR_n \circ f$ under strict one-sided error constraints (Zero False Positives, bounded False Negatives).
Theorem 3:
$\lim_{n \to \infty} \frac{R_{FP=0, FN \le \varepsilon}(OR_n \circ f)}{n} = IC^{U_0}_{FP=0, FN \le \varepsilon}(f)$
This provides an exact characterization where the limit is governed by a specialized asymmetric information complexity measure defined over distributions supported on 0-inputs.

3.4 Refutation of a Conjecture on Set-Disjointness

Applying Theorem 3 to the Set-Disjointness problem ( $DISJ_n$ , which is $OR_n \circ \text{AND}$ ), the paper resolves an open conjecture from Ref. [DFHL18].

Conjecture [DFHL18]: Proposed that standard randomized communication scales as $n \cdot IC^{U_0}_{FP=0, FN \le \varepsilon}(\text{AND}) + o(n)$ .
Refutation: The author shows that the correct scaling is governed by the asymmetric measure $R_{FP=0, FN \le \varepsilon}$ , not the standard two-sided bounded error $R_\varepsilon$ . They note that for Set-Disjointness, the standard complexity vanishes trivially at $\varepsilon = 1/2$ , whereas the proposed information complexity measure remains strictly positive, proving the conjecture false.

4. Significance and Claims

The paper claims to resolve a central form of the direct sum conjecture in randomized communication complexity. Its primary significance lies in:

Exact Characterization: Providing the first exact asymptotic characterization of amortized randomized communication complexity under the global error model, linking it precisely to zero-error information complexity.
Structural Insight: Introducing the "prefix-verification" embedding mechanism, which offers a refined tool for localizing global errors in interactive protocols, yielding exact results rather than just bounds.
Resolution of Open Problems: Successfully refuting a specific conjecture regarding the scaling behavior of the Set-Disjointness problem, clarifying the distinction between standard two-sided error and one-sided error regimes in amortized settings.

The author emphasizes that while the direct sum theorem fails in the general sense for search problems (due to the gap between information and communication complexity), their work precisely quantifies the "savings" achievable through amortization, showing it is exactly determined by the zero-error information cost of the base function. They further clarify that the failure of the direct sum theorem under the global error model is currently established for search problems, while the case for total functions remains an open problem.