Pith. sign in

REVIEW 1 major objections 4 minor 21 references

A Lower Bound on the Essential Interactive Capacity of Binary Memoryless Symmetric Channels

T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that every binary memoryless symmetric channel with positive Shannon capacity has essential interactive capacity at least 0.0302 times its Shannon capacity, giving the first explicit constant for interactive simulation…

desk verdict A serious, largely sound construction whose advertised constant 0.0302 is contradicted by the paper's own rate formula; the actual evaluation gives roughly 0.023. read the letter →

arxiv 1908.07367 v2 pith:7KT4BFUR submitted 2019-08-20 cs.IT math.IT

Assaf Ben-Yishai , Young-Han Kim , Or Ordentlich , Ofer Shayevitz This is my paper · ORCID
classification cs.ITmath.IT MSC 94A1594A2494B0568Q11
keywords interactivecommunicationessentialcapacitybinarymemorylesssymmetricchannelschannelrewind-if-errorschemeextendedHammingcodeBhattacharyyaparameterdeterministiccoding
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Interactive communication is the problem of simulating the transcript of a two-party conversation over a noisy channel, where each party's next bit depends on what the other has just said. The paper defines the essential interactive capacity of a channel as the largest rate at which the transcript of any interactive protocol can be simulated with a deterministic coding scheme, with no public or private randomness and no freedom to assume the speaking order in the simulated protocol. The central result is an explicit fraction: for every binary memoryless symmetric (BMS) channel with positive Shannon capacity, this interactive capacity is at least 0.0302 times the Shannon capacity. The proof is carried by a rewind-if-error scheme that transmits transcript bits uncoded in blocks, checks each block with an extended-Hamming code in the first layer and randomized polynomial evaluations in higher layers, and rewinds the protocol whenever an error is detected. The paper then removes the randomness by reducing the required random bits and extracting them from the channel noise, leaving a deterministic scheme.

What carries the argument

The load-bearing mechanism is a rewind-if-error coding scheme: simulate $k$ transcript bits uncoded, then have both parties compute and compare error-detection summaries, rewinding the protocol cursors and resimulating any block whose summary is inconsistent. The first layer compares syndromes of an extended-Hamming code; higher layers compare evaluations of the transcript-bit vectors at a random point over a finite field, checking both the transcript bits and all lower-layer rewind bits. Repetition coding with majority vote converts a noisy channel to a BSC with a small crossover probability, at a rate cost governed by $\log(1/\delta)/\log(1/\beta)$; the clean-channel analysis is then patched to all BMS channels by the extremal property that the BSC maximizes the Bhattacharyya parameter among BMS channels of equal Shannon capacity. The scheme's rate expression balances block length $k$, repetition counts, and the layered detection overhead, and the final ratio uses $k=2^9$ and $\delta=0.00018908$.

What would settle it

Take a mixture of $\mathrm{BSC}(0.05)$ and $\mathrm{BSC}(0.4)$ with equal probabilities, compute its Shannon capacity $C = 1 - E[h(T)]$ and its Bhattacharyya parameter $E[2\sqrt{T(1-T)}]$, and compare with the Bhattacharyya parameter of the BSC with capacity $C$. If the mixture's value exceeds the BSC value, the key lemma behind the BMS generalization is false. Alternatively, any explicit upper bound on the interactive-capacity ratio below $0.0302$ for a specific BMS channel would refute Theorem 1.

Watch

Extended reading notes

Core claim

Theorem 1 states that for any BMS channel with positive Shannon capacity, the ratio between interactive capacity and Shannon capacity is at least 0.0302. Theorem 2 proves the same ratio for the binary symmetric channel with any crossover probability. The argument first symmetrizes the speaking order, then applies a layered rewind-if-error scheme whose first-layer error detection uses an extended-Hamming code and whose higher layers use polynomial-evaluation checks; repetitions reduce any crossover probability to a small target. The transfer from the BSC to all BMS channels rests on Lemma 8: among BMS channels with a fixed Shannon capacity, the BSC has the largest Bhattacharyya parameter, so the BSC is the worst case for the repetition step. Section IX turns the randomized scheme deterministic, using $O(\sqrt{n})$ random test points extracted from the channel noise, so the 0.0302 ratio holds under the paper's strictest setup.

Load-bearing premise

The load-bearing premise is that, among all binary memoryless symmetric channels with a fixed Shannon capacity, the binary symmetric channel is the worst case because it has the largest Bhattacharyya parameter; the proof of that premise depends on a concavity inequality for the inverse binary entropy function, and if that inequality fails the bound for the whole BMS family does not follow.

Editorial extensions

If this is right

  • Under the paper's definitions, every BMS channel with positive Shannon capacity can simulate any interactive protocol at transcript rate at least $0.0302\,C_{Sh}$, with deterministic coding and no shared randomness.
  • Because the paper's definition is stricter than the prior interactive-capacity notions in the literature, the same $0.0302$ fraction also lower-bounds those looser capacities.
  • For protocols with a fixed alternating speaking order, the scheme achieves twice the rate, $0.0604\,C_{Sh}$, before the adaptive-order penalty is applied.
  • As a BMS channel approaches a clean binary channel, the guaranteed fraction tends to $1$, so the constant is not a barrier in the high-capacity regime.
  • For the BSC with very small crossover probability $\varepsilon$, the scheme attains $1 - O(\sqrt{h(\varepsilon)})$ of Shannon capacity, matching the earlier small-noise asymptotic.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial: the $0.0302$ floor converts into a worst-case overhead of about $33/C_{Sh}$ channel uses per transcript bit, which makes the abstract guarantee concrete for communication-complexity applications.
  • Editorial: the number should be read as a property of this particular scheme rather than the true interactive capacity; replacing the extended-Hamming first layer with any code with better short-block misdetection behavior would likely improve the constant.
  • Editorial: treating erasures as free detections, as the paper's tie-as-erasure discussion suggests, points to a testable specialization: a binary erasure channel version of the scheme should beat the $0.0302$ floor, since its errors are already flagged.
  • Editorial: the paper's derandomization recipe, namely sublinear random test points extracted from the channel, is general enough that other rewind-if-error schemes with $o(n)$ random bits could be made deterministic at negligible rate loss.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper defines a strong notion of interactive capacity for binary memoryless symmetric (BMS) channels: the maximal rate at which the transcript of any interactive protocol with adaptive speaker order can be reliably simulated using a deterministic coding scheme without public or private randomness. The main contribution is a claimed lower bound C_I/C_Sh >= 0.0302 for every BMS channel with positive Shannon capacity. The proof is built from a rewind-if-error scheme for the BSC using extended-Hamming error detection in a first layer and randomized polynomial hashing in higher layers, followed by a repetition-code reduction for larger crossover probabilities. The BMS extension is obtained via the extremal property that among BMS channels of a given capacity the BSC maximizes the Bhattacharyya parameter. The paper also explains how to derandomize the scheme by reducing the number of random test points and extracting randomness from the channel.

Significance. If the stated constant were correct, this would be the first explicit positive fraction of Shannon capacity guaranteed for interactive simulation over any BMS channel under the paper's restrictive model, including deterministic schemes. The coding scheme is explicit and the proof is largely self-contained, with the analysis of the layered rewind-if-error scheme being intricate and detailed. The claimed numerical constant is the central advertised result and appears in the abstract, Theorem 1, and Theorem 2.

major comments (1)
  1. [Section V, Theorem 2 and Eq. (8)] The numerical claim C_I/C_Sh >= 0.0302 is not supported by the paper's own formulas. Setting k=512, delta=0.00018908, a=3, and a_tilde=5 in Eq. (8), with log taken base 2 and beta=2*sqrt(delta(1-delta)), gives R_BSC(delta,k) approximately 0.629. The terms involving Pe1 and beta^{2k} are numerically negligible; the numerator is about 0.9029, and the denominator is about 1.4354. Applying the factor 1/2 for adaptive speaker order and Lemma 4 then yields C_I/C_Sh >= R_BSC/(2(log_2(1/delta)+1)) approximately 0.629/(2*13.37) about 0.0235, not 0.0302. Reaching 0.0302 would require R_BSC about 0.807, which is impossible because the numerator of Eq. (8) is already at most 1 - k*delta < 0.904. The constant 0.0302 must therefore be corrected, or an alternative calculation must be supplied. This issue directly affects the main theorem and the abstract.
minor comments (4)
  1. [Section V, Theorem 2] There is a wording error in the theorem statement: 'CSh(ε) the and interactive capacity CI(ε) the following bound holds' should be rewritten as a complete grammatical sentence.
  2. [Section V, after Eq. (8)] The phrase 'k is can be take as any integer a power of two' should read 'k can be taken as any integer power of two'.
  3. [Section VIII, Lemma 8] The BMS generalization depends on the concavity of x -> sqrt(h^{-1}(x)(1-h^{-1}(x))) from [8]; for completeness, the authors should state the exact theorem from [8] that establishes this extremal property, since it is load-bearing for the BMS claim.
  4. [Section IX-A] In the discussion of the number of random test points, the sentence 'We start by noting that by construction of error detection scheme, using independently drawn test points for its different actuations, will make their corresponding error mis-detection events statistically independent' is missing an article; it should be 'by construction of the error detection scheme'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the 0.0302 bound is obtained by evaluating a closed-form scheme analysis; external citations are non-self and non-load-bearing.

full rationale

I traced the derivation chain from Theorems 3 and 2 to Theorem 1. Theorem 3's rate expression (8) is derived from the rewind-if-error scheme via explicit error-probability bounds (Lemmas 2, 3, 5) and a channel-use bound (22); the constants a=3, \tilde a=5, k=2^9, and \delta=0.00018908 are design parameters substituted into the closed-form expression, not fitted to data and not renamed predictions. Lemma 4's repetition argument uses the externally cited lautum-information inequality, and Lemma 8's BMS reduction uses the externally cited extremal result of Guill\u00e9n i F\u00e0bregas et al. [8]; neither citation is self-referential, and neither restates the target lower bound. Section IX's derandomization is auxiliary and uses standard von Neumann extraction, so it does not carry the load of the main lower bound. The only concern I noticed is arithmetical: the displayed formulas may not numerically yield 0.0302 at the stated parameter choices, but arithmetic correctness is not a circularity issue. No load-bearing step equates the conclusion with an input by construction, so the derivation is self-contained for circularity purposes.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central claim introduces no new physical entity; the 'essential interactive capacity' is a definition. All parameters are explicit design choices in the coding scheme rather than hidden fits, and the mathematical assumptions are standard or clearly cited.

free parameters (4)
  • block length k = 512 = 2^9
    Chosen in the proof of Theorem 2 to evaluate the rate bound; must be a power of two with k <= 1/(8*delta).
  • target crossover delta = 0.00018908
    Chosen to optimize the final lower bound; the scheme is run on a BSC(delta) after repetition coding.
  • repetition count a = 3
    Number of repetitions for polynomial-based error detection bits; hand-picked in Theorem 3.
  • repetition count a_tilde = 5
    Number of repetitions for first-layer syndrome and feedback bits; hand-picked in Theorem 3.
assumptions (4)
  • domain assumption BMS channel can be represented as a mixture of BSCs via a sufficient statistic (Definition 1).
    Used throughout the BMS generalization; standard in the polar codes literature.
  • domain assumption Among BMS channels with capacity C, the BSC maximizes the Bhattacharyya parameter (Guillen i Fabregas et al. [8]).
    Load-bearing for Lemma 8 and Theorem 1; the proof cites Eq. (27), including concavity of an h^{-1} expression.
  • domain assumption Lautum information is at least mutual information for the BSC (Palomar and Verdu [20]).
    Used in Lemma 4 to replace the repetition overhead by log(1/delta)+1.
  • standard math Standard probabilistic and algebraic tools (Chernoff, Holder, Bertrand's postulate, dual code weight enumerators).
    Used in Lemmas 2, 3, 6, 11 and Appendix B.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Lower Bound on the Essential Interactive Capacity of Binary Memoryless Symmetric Channels." pith.science (2026). https://pith.science/paper/7KT4BFUR

@misc{pith2026190807367,
  author       = {Pith},
  title        = {Pith review of: A Lower Bound on the Essential Interactive Capacity of Binary Memoryless Symmetric Channels},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7KT4BFUR}},
  note         = {Machine review of arXiv:1908.07367}
}
abstract

The essential interactive capacity of a discrete memoryless channel is defined in this paper as the maximal rate at which the transcript of any interactive protocol can be reliably simulated over the channel, using a deterministic coding scheme. In contrast to other interactive capacity definitions in the literature, this definition makes no assumptions on the order of speakers (which can be adaptive) and does not allow any use of private / public randomness; hence, the essential interactive capacity is a function of the channel model only. It is shown that the essential interactive capacity of any binary memoryless symmetric (BMS) channel is at least $0.0302$ its Shannon capacity. To that end, we present a simple coding scheme, based on extended-Hamming codes combined with error detection, that achieves the lower bound in the special case of the binary symmetric channel (BSC). We then adapt the scheme to the entire family of BMS channels, and show that it achieves the same lower bound using extremes of the Bhattacharyya parameter.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 20 canonical work pages

  1. [1]

    Two-way communication channels,

    C. E. Shannon, “Two-way communication channels,” in Proceedings of the F ourth Berkeley Symposium on Mathematic al Statistics and Probability, V olume 1: Contributions to the Theory of Statistics . The Regents of the University of California, 1961

    work page 1961

  2. [2]

    Coding for interactive communication: a sur vey,

    R. Gelles, “Coding for interactive communication: a sur vey,” URL http://www. cs. princeton. edu/˜ rgelles/papers/surv ey. pdf, 2015

    work page 2015

  3. [3]

    Communication on noisy channels: A codi ng theorem for computation,

    L. J. Schulman, “Communication on noisy channels: A codi ng theorem for computation,” in Proceedings., 33rd Annual Symposium on F oundations of Computer Science . IEEE, 1992, pp. 724–733

    work page 1992

  4. [4]

    R. G. Gallager, Low-Density Parity-Check Codes . MIT Press, 1963

    work page 1963

  5. [5]

    New Y ork: John Wiley & Sons, 1968

    ——, Information Theory and Reliable Communication . New Y ork: John Wiley & Sons, 1968

    work page 1968

  6. [6]

    Richardson and R

    T. Richardson and R. Urbanke, Modern coding theory . Cambridge university press, 2008

    2008

  7. [7]

    Channel polarization: A method for construc ting capacity-achieving codes for symmetric binary-input memoryless channels,

    E. Arikan, “Channel polarization: A method for construc ting capacity-achieving codes for symmetric binary-input memoryless channels,” IEEE Transactions on Information Theory , vol. 55, no. 7, pp. 3051–3073, July 2009

    work page 2009

  8. [8]

    Extreme s of error exponents,

    A. Guillén i Fàbregas, I. Land, and A. Martinez, “Extreme s of error exponents,” IEEE Transactions on Information Theory , vol. 59, no. 4, pp. 2201–2207, 2013. 29

    work page 2013

Show all 21 references
  1. [9]

    On th e construction of polar codes,

    R. Pedarsani, S. H. Hassani, I. Tal, and E. Telatar, “On th e construction of polar codes,” in ISIT. IEEE, 2011, pp. 11–15

    2011

  2. [10]

    Interactive channel capacity,

    G. Kol and R. Raz, “Interactive channel capacity,” in Proceedings of the forty-fifth annual ACM symposium on Theor y of computing. ACM, 2013, pp. 715–724

    2013

  3. [11]

    Kushlevitz and N

    E. Kushlevitz and N. Nisan, Communication Complexity . Cambridge University Press, 1997

    1997

  4. [12]

    Kløve and V

    T. Kløve and V . Korzhik, Error detecting codes: general theory and their applicatio n in feedback communication systems . Springer Science & Business Media, 2012, vol. 335

    2012

  5. [13]

    V arious techniques used in connection with random digits,

    J. V on Neumann, “V arious techniques used in connection with random digits,” Appl. Math Ser , vol. 12, no. 5, pp. 36–38, 1951

    1951

  6. [14]

    The efficient construction of an unbiased ran dom sequence,

    P . Elias, “The efficient construction of an unbiased ran dom sequence,” The Annals of Mathematical Statistics , pp. 865–870, 1972

    1972

  7. [15]

    Coding for interactive communication ,

    L. J. Schulman, “Coding for interactive communication ,” IEEE Transactions on Information Theory , vol. 42, no. 6, pp. 1745–1756, 1996

    1996

  8. [16]

    Some complexity questions related to dis tributive computing (preliminary report),

    A. C.-C. Yao, “Some complexity questions related to dis tributive computing (preliminary report),” in Proceedings of the eleventh annual ACM symposium on Theory of computing . ACM, 1979, pp. 209–213

    1979

  9. [17]

    Interactive channel capacity revisited ,

    B. Haeupler, “Interactive channel capacity revisited ,” in F oundations of Computer Science (FOCS), 2014 IEEE 55th Annu al Symposium on . IEEE, 2014, pp. 226–235

    2014

  10. [18]

    Explicit capacity approaching coding for interactiv e communication,

    R. Gelles, B. Haeupler, G. Kol, N. Ron-Zewi and A. Wigder son, “Explicit capacity approaching coding for interactiv e communication,” IEEE Transactions on Information Theory , vol. 64, pp. 6546 – 6560, October 2018

    2018

  11. [19]

    The interactive capacity of the binary symmetric channel i s at least 1/40 the shannon capacity,

    A. Ben-Yishai, Y -H Kim, O. Ordentlich and O. Shayevitz, “The interactive capacity of the binary symmetric channel i s at least 1/40 the shannon capacity,” in ISIT 2019

    2019

  12. [20]

    Lautum information,

    D. P . Palomar and S. V erdú, “Lautum information,” IEEE transactions on information theory , vol. 54, no. 3, pp. 964–975, 2008

    2008

  13. [21]

    Probability of error, equivoc ation, and the chernoff bound,

    M. Hellman and J. Raviv, “Probability of error, equivoc ation, and the chernoff bound,” IEEE Transactions on Information Theory, vol. 16, no. 4, pp. 368–372, 1970. 30

    1970

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.