{"id":"f048e47e-3e80-4d4f-a3ba-76b2fe06305e","arxiv_id":"1908.07367","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"The interactive capacity of every binary memoryless symmetric channel is at least 0.0302 times its Shannon capacity, achieved by a deterministic rewind-if-error coding scheme.","lead":"This paper proves that any binary symmetric noisy channel can carry interactive conversations at a guaranteed fraction of its ordinary data rate, at least 3.02 percent. It supplies an explicit deterministic coding scheme and attaches the first concrete number to a question open since the early 1990s.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Stated 0.0302 lower bound is contradicted by the paper's own rate expression: substituting Theorem 2's parameters into Eq. (8) gives R_BSC≈0.60 and a final ratio ≈0.023, not 0.0302.","rationale":"The reader's conditional verdict is appropriate, but the stated weakest assumption (Lemma 8 and the BMS concavity step) is not where the argument breaks. The concavity invoked there is standard and the BMS reduction is plausible. The real soft spot is internal and already visible in the BSC case: the rate expression printed as Eq. (8), evaluated at the parameters selected in Theorem 2, gives a final guaranteed ratio of roughly 0.023 rather than 0.0302. This follows from substituting k=512, δ=0.00018908 and from the overhead count in Eq. (22), which yields the denominator in Eq. (8). The headline constant would require R_BSC≈0.81, whereas the formula gives about 0.61. The issue is mechanical and checkable, not a challenge to the interactive-capacity framework, and the scheme may still yield a smaller positive constant. Because the numerical theorem as stated is unsupported by the paper's own equations, the conditional verdict should stand pending correction or an explicit calculation.","tokens_in":26555,"tokens_out":36806,"duration_ms":353077,"concrete_test":"Write a short script that evaluates Eq. (8) exactly (with log base 2, a=3, \\tilde a=5) for the values used in Theorem 2: k=512, δ=0.00018908, plus a sweep over powers of two k and δ≤1/(8k). Compute F(δ,k)=R_BSC(δ,k)/(2(log_2(1/δ)+1)). If max F is below 0.0302, Theorem 1 as stated is not supported. As a cross-check, recompute the numerator and denominator term-by-term from Eqs. (20)-(22), especially the ∑_{l≥2} 3 log k · l(a+2l) k^{L-l} overhead and the 3β^a terms, to identify which quantity was dropped in the stated 0.0302.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing problem is not in the BMS generalization; it is in the BSC rate calculation that feeds Theorem 1. Theorem 2 instructs us to use k=2^9 and δ=0.00018908 in Theorem 3, to divide by 2 for adaptive speaker order, and to pay the repetition penalty log_2(1/δ)+1 from Lemma 4. Evaluating the displayed rate formula Eq. (8) with a=3, \\tilde a=5, log=log_2 yields kδ≈0.0968, P_e1≈2e-7, and a denominator of about 1.435 (the 3log k [...] term from higher-layer error detection in Eq. (22) contributes about 0.318). Hence R_BSC≈0.607. The final bound is R_BSC/(2(log_2(1/δ)+1))≈0.607/(2*13.37)≈0.0227, well below 0.0302. Reaching 0.0302 would require R_BSC≈0.807, which is not obtained at any admissible (δ,k) under (8); a rough sweep suggests the maximum lies near 0.025-0.026. Thus the numerical claim in Theorem 1/2 is not a consequence of the formulas in the paper. The scheme may still give a positive constant, but the advertised constant needs correction or an alternative calculation.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":26868,"tokens_out":19818,"duration_ms":178255,"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":[{"comment":"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.","section":"Section V, Theorem 2 and Eq. (8)"}],"minor_comments":[{"comment":"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.","section":"Section V, Theorem 2"},{"comment":"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'.","section":"Section V, after Eq. (8)"},{"comment":"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.","section":"Section VIII, Lemma 8"},{"comment":"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'.","section":"Section IX-A"}],"recommendation":"major_revision","confidential_remarks":"The discrepancy between the advertised constant 0.0302 and the value that follows from the paper's own rate expression is the central obstacle to publication. The scheme and its analysis appear largely sound, and the paper would still make a meaningful contribution after the constant is corrected (e.g., to about 0.023) or after an alternative calculation is provided that actually yields 0.0302."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"My take on arXiv:1908.07367: the paper does something genuinely useful. It presents a deterministic rewind-if-error scheme for interactive communication over any BMS channel, with layered error detection (extended-Hamming at the bottom, polynomial hashing above), repetition coding, and a randomness-extraction argument that removes public randomness. The construction is careful, and the analysis of the error events is coherent. If the numerical claim were right, this would be the first explicit constant since Schulman.\n\nThe problem is the number. When I plug the parameters from Theorem 2 into Eq. (8) — k=2^9, δ=0.00018908 — the rate before repetition and symmetrization comes out around 0.607, not the 0.807 needed to reach 0.0302 after the factor 1/2 and the Lemma 4 penalty of log2(1/δ)+1 ≈ 13.37. Concretely, the numerator is about 0.871 after the k^2/(k-1) amplification of Pe1+3β^3, the denominator is about 1.435, giving R≈0.607; then 0.607/(2*13.37) ≈ 0.0227. A rough sweep over admissible (k,δ) puts the maximum near 0.025–0.026, still below the advertised 0.0302.\n\nThis looks like an arithmetic error rather than a broken scheme. Lemma 5–7 are consistent with the construction, the layered rewinding argument holds together, and the BMS reduction via the Bhattacharyya extremal property is plausible. The deterministic conversion in Section IX also seems fine. The flaw is localized to the numeric evaluation in Theorem 2, but it is load-bearing: the headline claim as stated does not follow from the displayed formulas.\n\nWhat does this mean for us? The paper deserves a serious referee, but only with a clear request to recompute the constant and provide a reproducible evaluation. If the corrected value is around 0.023–0.026, the contribution still stands as an explicit constant with a deterministic scheme, which is a meaningful milestone. I would not cite the 0.0302 number until it is fixed, and the paper needs a major revision before acceptance.","headline":"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.","tokens_in":27387,"tokens_out":7685,"would_cite":false,"duration_ms":69326,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A24","94B05","68Q11"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["interactive communication","essential interactive capacity","binary memoryless symmetric channels","binary symmetric channel","rewind-if-error scheme","extended Hamming code","Bhattacharyya parameter","deterministic coding"],"falsifier":"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.","tokens_in":26354,"feed_emoji":"📡","tokens_out":12074,"duration_ms":114478,"temperature":0.7,"pith_summary":"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.","feed_headline":"Binary symmetric channels: interactive speed reaches 3.02% of Shannon","feed_subtitle":"Any two-party protocol can be simulated at 3.02% of Shannon capacity, with no shared randomness.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces interactive communication over noisy channels and the rewind-if-error principle, establishing that a positive interactive capacity exists whenever Shannon capacity is positive.","marker":"[3]"},{"why":"Supplies the extremal fact that the BSC has the largest Bhattacharyya parameter among BMS channels of a given Shannon capacity, which carries the bound from the BSC to all BMS channels.","marker":"[8]"},{"why":"Defines an earlier interactive capacity and gives a small-noise rewind-if-error scheme that the present layered construction is inspired by and improves upon.","marker":"[10]"},{"why":"Provides the randomized polynomial-evaluation error-detection method used in the higher layers of the scheme.","marker":"[11]"},{"why":"Supplies the error-detection performance of the extended-Hamming code, including its properness, used in the first layer.","marker":"[12]"},{"why":"Gives the repetition-coding and feedback arguments that underpin the conversion of a noisy channel to a low-noise BSC and the rate-loss accounting.","marker":"[5]"},{"why":"Provides the simple pairwise randomness-extraction procedure that lets the scheme draw its random test points from channel noise.","marker":"[13]"}],"fun_headline_variants":["Interactive capacity lower bound: 3.02% of Shannon for BMS channels","BMS channels: guaranteed interactive rate at least 3.02% of Shannon","New bound: Interactive capacity ≥ 3.02% Shannon for BMS channels","Essential interactive capacity: BMS lower bound 0.0302 Shannon"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Interactive capacity lower bound: 3.02% of Shannon for BMS channels","BMS channels: guaranteed interactive rate at least 3.02% of Shannon","New bound: Interactive capacity ≥ 3.02% Shannon for BMS channels","Essential interactive capacity: BMS lower bound 0.0302 Shannon"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000515,"raw_usage":{"total_tokens":2482,"prompt_tokens":907,"completion_tokens":1575,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":1490}},"tokens_in":523,"tokens_out":1575,"duration_ms":13108,"temperature":1.0,"reasoning_tokens":1490,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:23:12.234027+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Communication on noisy channels: A codi ng theorem for computation,","cited_arxiv_id":null,"evidence_quote":"Introduces interactive communication over noisy channels and the rewind-if-error principle, establishing that a positive interactive capacity exists whenever Shannon capacity is positive."},{"cited_title":"Extreme s of error exponents,","cited_arxiv_id":null,"evidence_quote":"Supplies the extremal fact that the BSC has the largest Bhattacharyya parameter among BMS channels of a given Shannon capacity, which carries the bound from the BSC to all BMS channels."},{"cited_title":"Interactive channel capacity,","cited_arxiv_id":null,"evidence_quote":"Defines an earlier interactive capacity and gives a small-noise rewind-if-error scheme that the present layered construction is inspired by and improves upon."},{"cited_title":"Kushlevitz and N","cited_arxiv_id":null,"evidence_quote":"Provides the randomized polynomial-evaluation error-detection method used in the higher layers of the scheme."},{"cited_title":"Kløve and V","cited_arxiv_id":null,"evidence_quote":"Supplies the error-detection performance of the extended-Hamming code, including its properness, used in the first layer."},{"cited_title":"New Y ork: John Wiley & Sons, 1968","cited_arxiv_id":null,"evidence_quote":"Gives the repetition-coding and feedback arguments that underpin the conversion of a noisy channel to a low-noise BSC and the rate-loss accounting."},{"cited_title":"V arious techniques used in connection with random digits,","cited_arxiv_id":null,"evidence_quote":"Provides the simple pairwise randomness-extraction procedure that lets the scheme draw its random test points from channel noise."}],"review_version":1}