PaperlayerView exact revision on arXiv

Source-linked AI summary

Constant-Loss Round-Preserving Direct Sums for Information Complexity

Haoran Wang

arXiv:2610.15377v1cs.CCcs.ITmath.IT

TL;DR

The paper asks whether Gap-Majority can retain its optimal information bound without losing communication rounds, and extends the question to additive observables over product inputs. It uses centered conditional-mean innovations and variance amortization to derive round-preserving single-coordinate protocols. For balanced Gap-Majority, the extracted decision has information cost IC(π)/n + O(1) and error at most 0.499.

  • Problem

    For Gap-Majority, a strong information bound was known, but preserving the original number of messages in the reduction incurred O(log n) information loss.

    Source: §1 · p. 1, §4.1 · p. 7

  • Method

    The proof encodes centered conditional-mean innovations and uses a telescoping variance bound to control the information cost of extracted protocols.

    Source: §1.3 · p. 3, §3.3 · p. 6

  • Results

    Bob’s variance is at most 0.998, information cost is IC(π)/n + O(1), and the posterior-majority decision errs with probability at most 0.499.

    Source: §4.1 · p. 7

  • Takeaways & Limitations

    The theorem extends round-preserving extraction to additive square-integrable observables when terminal-answer support is bounded.

    Source: §1.2 · p. 2

    The extracted single-instance protocol’s worst-case communication length is not bounded by this result.

    Source: §4.1 · p. 7

Abstract

from arXiv · show

Strong direct-sum theorems relate the information needed to solve many independent instances of a communication problem to the information needed for one instance. For Gap-Majority composition, an optimal information bound was previously known, but preserving the number of communication rounds incurred an additional logarithmic loss. We prove a round-preserving Gap-Majority lemma with constant additive information loss, independent of both the number of instances and the number of rounds. More generally, we establish a variance direct-sum theorem for additive square-integrable observables over product distributions. For protocols with a bounded number of terminal answer values, the extracted single-coordinate protocols preserve the round budget, and their average information cost is at most the original information cost divided by the number of coordinates, plus a term depending only on the answer alphabet and the allowed variance loss. The proof uses centered counterfactual conditional means and a global variance amortization argument. Rather than encoding absolute conditional means for every possible terminal answer, we encode the information not already determined by the common view. The total squared innovation is controlled by a telescoping variance potential, yielding an information loss independent of the number of coordinates. We also derive same-round mean-square estimation bounds for arbitrary terminal outputs.

1 Introduction

The section asks whether success on an independent-instance Gap-Majority sum forces information proportional to the number of instances, while retaining the round budget. It presents a round-preserving direct-sum theorem and a variance-based proof approach.

1 Introduction

  • The motivating question is whether a successful protocol for the sum reveals information proportional to the number of independent instances.Information cost has an exact chain rule, while adding interaction can undermine round-sensitive lower bounds.Source: §1 · p. 1

1.1 Prior work and the round constraint

  • Sawettamalya and Yu obtained information cost IC(π)/n + O(1), but their reduction either changed the message count or incurred O(log n) loss when preserving rounds.The open question was whether constant loss and round preservation could hold simultaneously.Source: §1.1 · p. 1

1.2 Main results

  • For terminal answers with support at most m, Theorem 1.1 extracts r-round single-coordinate protocols under a variance allowance Δ.For i.i.d. inputs, a uniformly chosen coordinate gives a single protocol with the same bounds.Source: §1.2 · p. 2
  • For balanced Gap-Majority, observer variance is at most 0.99n, yielding the conjectured same-round constant-loss extraction at fixed Δ.The terminal answer is binary and σ² = 1.Source: §1.2 · p. 2
  • For arbitrary terminal outputs, the paper uses likelihood rank for low-rank channels and quantitative approximation for unrestricted rank.The low-rank reduction compresses the answer before coordinate peeling.Source: §1.2 · p. 2, §1.3 · p. 3

1.3 Proof overview

  • The proof encodes centered differences between conditional means and predictions from the common view, then controls their total squared size through telescoping variance.Quantizing these innovations converts the global L2 bound into an information-cost bound.Source: §1.3 · p. 3

2 Preliminaries

The preliminaries fix the distributional communication model and the message convention used for the direct-sum arguments. They also state the factorization, variance, and entropy tools used in the proof.

2 Preliminaries

  • Alice receives X, Bob receives Y, they share public randomness and exchange an r-message transcript, and Bob answers after Alice’s last message.The model allows Bob private randomness for the answer and assumes standard Borel input and answer spaces.Source: §2 · p. 3
  • Conditioning on the transcript, public randomness, and disjoint fixed coordinates preserves factorization of the remaining product inputs.Local postprocessing of Bob’s answer preserves the property because it modifies only the Bob-side factor.Source: §2 · p. 3
  • The law of total variance decomposes conditional variance into finer conditional variance plus the squared change in conditional means.This identity supplies the variance accounting used in the decomposition.Source: §2 · p. 3
  • Quantizing a square-integrable variable at a measurable step size yields an entropy bound controlled by its squared magnitude and the step size.The proof adds uniform noise to the quantized value and bounds its entropy using Gaussian maximum entropy.Source: §2 · p. 3

3 Proof of the direct-sum theorem

The proof replaces absolute conditional means with quantized innovations and amortizes their squared magnitude through a telescoping variance potential. This bounds the information added during round-preserving coordinate extraction.

3 Proof of the direct-sum theorem

  • The proof replaces the auxiliary message in the round-preserving peeling of with a quantized innovation, after centering the observables without changing conditional variance.Source: §3 · p. 4

3.1 Counterfactual innovations

  • Alice encodes each branch’s conditional-mean innovation relative to the common view, and Bob reconstructs the realized branch with mean-square error at most δ.A post-answer resampling step supports charging squared innovations across hypothetical branches to the branch realized.Source: §3.1 · pp. 4–5

3.2 The innovation-energy telescope

  • The quantized reconstruction’s error bounds the next observer variance, and summing the resulting inequalities telescopes the variance terms across the peeling process.The argument starts from V_n ≤ Var(S_n) = nσ².Source: §3.2 · pp. 5–6

3.3 From energy to information

  • The information increase from appending the quantized innovation vector is bounded using its conditional entropy, while the coordinate and residual children’s prior information costs sum to at most the parent’s.The parameter choices δ = Δ/2 and ρ = Δ/(4σ²) yield theorem 1.1.Source: §3.3 · p. 6

4 Consequences

Applying the variance theorem to balanced Gap-Majority yields a same-round single-instance protocol with bounded error and information cost IC(π)/n + O(1). The resulting information bound also yields a communication lower bound, but does not control worst-case length of the extracted protocol.

4.1 Gap-Majority

  • Bob’s posterior-majority decision errs with probability at most 0.499, while the extracted protocol has information cost IC(π)/n + O(1).This establishes theorem 1.2 for balanced f, using theorem 1.1 with m = 2 and Δ = 0.008.Source: §4.1 · p. 7
  • Since information cost is at most communication cost, the same theorem yields a communication lower bound, but it does not bound the extracted protocol’s worst-case length.Source: §4.1 · p. 7

5 Terminal likelihood rank

This section reduces low-likelihood-rank terminal channels to protocols with at most as many answer symbols as the channel’s rank. The reduction preserves the messages and information cost while retaining the variance-relevant behavior of the observable.

5 Terminal likelihood rank

  • The reduction compresses the terminal alphabet before peeling coordinates, preserving the observable’s squared conditional mean rather than simulating the original answer.The compressed channel retains the moment equations, and its conditional mean is unchanged, so the law of total variance establishes the variance claim.Source: §5 · pp. 7–8
  • A terminal channel of likelihood rank at most s can be replaced by an at-most-s-symbol answer protocol without increasing transcript information cost or message count.Bob produces the replacement answer locally after the last message; the construction preserves the variance relevant to the theorem.Source: §5 · p. 7
  • The proof places the observable’s conditional mean in the finite-dimensional likelihood space and uses a convex-geometric reduction to retain the needed moments with few answer values.The retained points and weights preserve the moment equations; the finite-dimensional construction can be implemented measurably with fresh public randomness.Source: §5 · pp. 7–8
  • Likelihood rank can remain bounded while the answer alphabet grows: the example has rank at most three, making the conclusion independent of m.The rank bound applies to the original terminal channel.Source: §5 · p. 9

6 Arbitrary terminal outputs and mean-square estimation

For unrestricted-rank terminal outputs, this section gives a quantitative approach under a finite-fourth-moment condition. It also obtains a single-logarithm information loss under an additional condition on posterior gain.

6 Arbitrary terminal outputs and mean-square estimation

  • With unrestricted-rank terminal outputs and finite fourth moment, the theorem gives a quantitative reduction for sums of i.i.d. observables.The theorem is stated for a centered observable with positive variance and an arbitrary terminal answer.Source: §6 · p. 9
  • The proof quantizes the centered posterior gain U by truncating its magnitude and rounding the retained magnitude down on a geometric grid, while preserving a constant fraction of E U^2.It then applies the finite-answer theorem to the quantized answer; under the fourth-moment condition, the proof instead uses the sign of U and a binary answer.Source: §6 · pp. 9–10
  • The additive information loss is O_gamma(log2(2 + 1/gamma)); an additional condition on posterior gain suffices for a single logarithm.The stated additional condition bounds E U^4 by K(E U^2)^2 whenever E U^2 is positive.Source: §6 · p. 10

AI assistance

The manuscript reports use of ChatGPT during exploratory derivations, proof review, literature checking, and editing.

AI assistance

  • ChatGPT was used for exploratory derivations, proof review, literature checking, and manuscript editing; the author takes responsibility for the arguments and statements.The disclosure assigns responsibility for the manuscript’s arguments and statements to the author.Source: AI assistance · p. 10

A One-step peeling and information identities

The one-step peeling argument constructs residual and coordinate children by resampling the missing inputs, so both can simulate the parent protocol. The information costs are controlled by the chain rule, while a centered auxiliary message and variance identities support the recursive analysis.

A One-step peeling and information identities

  • The residual and coordinate children use public and private resampling of missing coordinates, and both reproduce the parent’s joint law and simulate its transcript before the extra message.The two simulated transcripts’ internal information costs sum to at most the parent’s information cost by the chain rule.Source: A One-step peeling and information… · p. 11
  • Only the residual child receives Alice’s quantized vector, whose additional information about Bob’s real input is zero conditional on Alice’s input and private randomness.The additional Alice-input information is bounded by the conditional entropy estimated in the main proof.Source: A One-step peeling and information… · p. 11
  • Conditional independence across the peeled coordinate supports the variance identities; the reconstructed conditional mean has mean-square error at most delta, yielding V_(k-1) ≤ U_k + delta.The variance terms telescope after summing over k.Source: A One-step peeling and information… · p. 11
Loading 2610.15377v1…