{"id":"fa5a4198-68ab-4064-a3ca-ac1ab7ab57f4","arxiv_id":"2512.21112","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Modeling information as confusion hypergraphs makes logical operations on information well-defined, so network coding requirements become logical formulae whose hypergraph entropy bounds the optimal message cost within a logarithmic gap.","lead":"This paper models information as confusion hypergraphs (downward-closed sets of confusable outcomes) and shows that logical operations such as AND, OR, and implication can compute optimal messages for network coding settings like the butterfly network. The cost of the optimal message is the entropy of the corresponding hypergraph formula, up to a logarithmic gap.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Abstract's universal \"simply entropy\" claim is contradicted by the paper's own Section V-I: in Slepian-Wolf coding the plain entropy H(M*) is not the cost, so the central claim holds only for a restricted class of settings.","rationale":"The reader's weakest assumption identifies the same load-bearing issue: the framework's cost formula H(M*) is not the correct communication cost in every coding setting because encoder-side constraints are not captured by plain hyperconfusion entropy. The paper itself admits this in Section V-I, so the abstract's universal 'simply entropy' claim is an overclaim. I agree with the conditional verdict: the core mathematics (Heyting algebra of hyperconfusions, unconfusing lemma, butterfly computation) appears coherent, but the claims need to be scoped to settings where the only constraint is M⊆F(...), with coarse entropy or explicit encoder-computability conditions elsewhere. This does not require rejecting the paper; it requires tightening the statement of the central claim. Hence no change to the reader's conditional verdict.","tokens_in":37033,"tokens_out":23301,"duration_ms":245286,"concrete_test":"Evaluate the C5 incidence Slepian-Wolf instance: let X have 5 values, Y the 5 edges of C5, and p uniform over the 10 incidence pairs. Compute H(M*) by Definition 3 and H(M*↘X) by Definition 23, where M* = Y→X. Also compute, by exhaustive search over partitions of X, the minimum H(M) over ordinary M satisfying X⊆M⊆M*. If H(M*↘X) (or the true ordinary-minimum) exceeds H(M*), the plain-entropy formula in the abstract is false for this valid zero-error coding setting. If they coincide, the Section V-I discrepancy is only apparent.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—that evaluating a hyperconfusion formula gives a message whose entropy is the optimal communication cost up to a logarithmic gap—requires that the unconfusing lemma (Lemma 7) produce an ordinary message that is a valid code for the original setting. In settings with encoder-side constraints this is not guaranteed. Section V-I states this explicitly: after converting M* = Y→X to an ordinary hat(M*) ⊆ M*, 'we may not have X ⊆ hat(M*), so the encoder may not be able to output hat(M*)'; hence H(M*) is not the correct cost and the paper introduces coarse entropy H(M*↘X). This is not an isolated corner case. Theorem 21's H* minimizes over M ∈ OIs(Ω) with only X∩M⊆Y and Y∩M⊆X, omitting the encoder-computability condition X∩Y⊆M. For a general butterfly setup where the satellite receives only X and Y, the upper-bound construction via Lemma 7 can return an ordinary information that is not a function of (X,Y); the lower bound H(M*) still holds, but the matching upper bound is not established. The abstract's universal 'simply given by the entropy of the hypergraph' therefore overstates the scope of Theorem 21. The Heyting-algebra machinery itself is not invalidated, but the headline claim as stated is false for settings such as Slepian-Wolf and any network problem with encoder-side constraints.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces 'hyperconfusions' (downward-closed families of confusable subsets of a finite sample space) as a model of information, and shows that they carry a Heyting-algebra structure with conjunction, disjunction, implication, and negation. It defines several entropy notions for hyperconfusions, proves an 'unconfusing lemma' converting hyperconfusions to ordinary random variables within a logarithmic gap, and proposes a 'coding-logic correspondence': coding problems such as the butterfly network, index coding, and Slepian-Wolf coding are written as logical formulae, and the optimal communication cost is claimed to be the entropy of the corresponding hyperconfusion formula up to a logarithmic gap. The paper also connects the resulting logic to Medvedev logic, defines a coarse entropy for settings with encoder-side constraints, and gives algorithms for computing hyperconfusion operations and entropies.","tokens_in":37370,"tokens_out":7120,"duration_ms":80183,"significance":"If the central claim held in its stated generality, this would be a substantial conceptual unification: it would turn a broad class of zero-error network information problems into a single algebraic/computational procedure, with an explicit Heyting-algebra semantics and a concrete logarithmic-gap guarantee. The paper has real strengths: the entropy definition is a clean convex-corner minimization; the unconfusing lemma (Lemma 7) is stated with an explicit constant and proved via the strong functional representation lemma; the two-bit butterfly example is computed by explicit enumeration and correctly yields the XOR code; and Theorem 22 relating trivial coding tasks to Medvedev logic is a genuinely surprising and interesting result. However, the abstract's unqualified claim that 'the optimal communication cost is simply given by the entropy of the hypergraph' is contradicted by the paper's own Section V-I, where plain entropy H(M*) is explicitly not the correct Slepian-Wolf cost. The scope of Theorem 21 is also narrower than the butterfly-network description requires. These are central, load-bearing issues, though the underlying framework appears salvageable by incorporating coarse","major_comments":[{"comment":"The abstract states that 'the optimal communication cost is simply given by the entropy of the hypergraph (within a logarithmic gap)' and the Introduction repeats this as a general claim. Section V-I explicitly says that in Slepian-Wolf coding, H(M*) is not the correct cost, and that after unconfusing M* = Y→X to an ordinary hat(M*) ⊆ M*, 'we may not have X ⊆ hat(M*), so the encoder may not be able to output hat(M*)'. The paper then introduces a different object, coarse entropy H(M* ↘ X). Thus the headline claim is false for a whole class of settings with encoder-side constraints and is not merely a minor caveat. The abstract and the statement of the coding-logic correspondence need to be qualified to the settings where the unconfusing lemma's output is encoder-computable, or the correspondence must be re-stated in terms of coarse entropy.","section":"Abstract and Section V-I"},{"comment":"Theorem 21 defines H* as the infimum over M ∈ OIs(Ω) satisfying only the decoding constraints X∩M⊆Y and Y∩M⊆X. In the butterfly network the satellite knows both X and Y, so a transmitted ordinary message M must additionally be a function of (X,Y), i.e. X∩Y⊆M. The upper-bound construction via Lemma 7 produces an ordinary hat(M*) with hat(M*)⊆M*, but does not guarantee X∩Y⊆hat(M*). Hence the theorem proves a bound for a relaxed, decoder-only optimization problem, not necessarily for the actual butterfly communication cost. The two-bit example works because M* is already an ordinary information and X∩Y⊆M*, but this is a special case. The theorem needs either an additional encoder-computability constraint in the definition of H* or a separate argument that the unconfusing lemma can be applied in a way that preserves computability from X∩Y.","section":"Section V-C, Theorem 21"},{"comment":"The paper states that other problems with encoder-side constraints 'can also be analyzed similarly' via coarse entropy, but no theorem is proved that gives the Slepian-Wolf optimal cost in terms of H(M* ↘ X) up to a logarithmic gap. Proposition 24 gives an unconfusing lemma for coarse entropy, but the required condition is Y⊆X, and the encoder's ability in Slepian-Wolf is represented by a lower bound on the encoder's knowledge, X⊆M, not by an ordinary inclusion of the message. Without a matching lower bound showing that the coarse entropy is the actual optimum, the central correspondence for Slepian-Wolf and general network coding with encoder constraints remains unsupported. This should be either proved or explicitly stated as an open problem rather than claimed as an instance of the general correspondence.","section":"Section V-I and Section VII"}],"minor_comments":[{"comment":"The fractional max-entropy is written Hϵ(X), using ϵ as a symbol that is conventionally an error probability; this may confuse readers in the error-probability sections. Consider renaming it, e.g. H_f(X).","section":"Definition 5"},{"comment":"The figures draw only maximal confusable sets in some cases but do not state this in the captions. A short caption note saying 'blue circles are maximal confusable sets' would improve readability; Figure 1 currently lacks such a note.","section":"Figure 1 and 2"},{"comment":"The phrase 'supp(X) is not required to be Ω' is important, but the first concrete examples of hyperconfusions with partial support appear only later with event hyperconfusions. An early illustrative example would help.","section":"Definition 2"},{"comment":"The proof of Theorem 22 is somewhat compressed: it asserts that hyp⊩ is a homomorphism and that every Kripke satisfaction relation arises from hyperconfusions. Since Medvedev logic is much less standard than intuitionistic logic, a more detailed verification of the two directions would improve clarity.","section":"Appendix H"}],"recommendation":"major_revision","confidential_remarks":"The paper is by one of the main contributors to the strong functional representation lemma and to prior work on information diagrams; self-citation is present but not disproportionate. The central obstacle is that the paper's advertised 'cost = entropy of the formula' claim is too broad even relative to its own Section V-I, and Theorem 21's upper bound is incomplete for the actual butterfly network with encoder-side information. However, the paper already contains the beginnings of the needed repair (coarse entropy), so I would not reject it. I recommend major revision with a request that the authors either prove the coarse-entropy version of the central theorem or sharply restrict the abstract and theorem statements to settings with no encoder-side constraints."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this paper builds a real framework—hyperconfusions as a model of information, with conjunction, disjunction, and implication forming a Heyting algebra—and proves coding theorems for the butterfly network and related settings. The core machinery is not hand-waving; the unconfusing lemma connects hyperconfusion entropy to ordinary random-variable cost within a logarithmic gap, and the butterfly example is computed explicitly, checking out. The characterization of trivial tasks via Medvedev logic is an elegant and genuinely new connection. This is the kind of paper that could reshape how we think about the algebra of information.\n\nThe soft spot is exactly what the stress-test note says, and it lands. The abstract claims the optimal communication cost is 'simply given by the entropy of the hypergraph' without qualification. But Section V-I states plainly that for Slepian-Wolf coding, H(M*) is not the correct cost, because the encoder may not be able to output the unconfused message. The paper introduces coarse entropy to handle that case, and Theorem 21's proven bound applies only when the requirement is M ⊆ F(...), not when the encoder has additional constraints. That is not a corner case: many network coding problems have encoder-side constraints. So the headline claim, as stated, is too broad. The Heyting-algebra machinery survives, but the scope of the central formula needs to be stated honestly.\n\nOther soft spots are minor in comparison. Implication computation may be exponential, which limits the algorithmic payoff. The paper is long and many proofs are in appendices, but that is not a defect if the proofs are sound—they appear to be. The self-citation to the strong functional representation lemma is legitimate, since that lemma is the right tool and the author's prior work on it is standard.\n\nThis paper deserves a serious referee. It is novel, technically substantial, and likely to influence future work on zero-error coding and logic. But it should not be accepted as is. The authors need to revise the abstract and introduction to restrict the entropy claim to settings without encoder-side constraints and to point to coarse entropy where it applies. That is a substantial but tractable revision. I would not cite it in my own work in the next year, but I would send it to peer review and would suggest bringing it to a reading group if anyone in the group works on network information theory or categorical information.","headline":"A genuinely new logical calculus for zero-error network coding, but the abstract's 'simply entropy' claim needs a scope restriction the paper itself admits in Section V-I.","tokens_in":37811,"tokens_out":1741,"would_cite":false,"duration_ms":22897,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","03B20","94A17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that communication and coding tasks can be translated into intuitionistic-logic formulae over confusion hypergraphs, and that the entropy of the resulting hypergraph gives the optimal communication rate to within a logarit","keywords":["confusion hypergraph","Heyting algebra","intuitionistic logic","network coding","index coding","Slepian-Wolf coding","zero-error coding","hypergraph entropy"],"falsifier":"Compare the formula entropy H((X→Y)∩(Y→X)) with the true zero-error rate for a butterfly network where X and Y are independent bits with unequal probabilities p and 1-p; if the difference exceeds the claimed logarithmic bound, the correspondence is false. Alternatively, exhibit a hyperconfusion X where the minimal entropy among ordinary refinements Y⊆X is more than H(X)+log(H(X)+3.4)+1, refuting the unconfusing lemma.","tokens_in":36910,"feed_emoji":"📡","tokens_out":4969,"duration_ms":43582,"temperature":0.7,"pith_summary":"Most information theory models information as random variables, which only support conjunction. This paper instead models information as confusion hypergraphs—families of mutually confusable outcomes—which form a Heyting algebra, so information can be conjoined, disjoined, and subtracted. Coding requirements such as the butterfly network, index coding, and Slepian-Wolf coding then become logical formulae; evaluating a formula yields the most ambiguous message that solves the task. The paper's central claim is that the entropy of that message equals the optimal communication cost to within a logarithmic gap, turning code design into formula evaluation. For two independent fair bits in the butterfly network, the formula evaluates to the XOR, whose entropy is exactly 1 bit—the known optimum.","feed_headline":"Optimal communication cost is hypergraph entropy","feed_subtitle":"Networks become logical formulae; the formula's hyperconfusion entropy gives the rate to within a log gap.","key_machinery":"The central object is the confusion hypergraph (hyperconfusion): a downward-closed family of subsets of a sample space, where a set is confusable if all its elements can be represented by a single reconstruction. Hyperconfusions form a Heyting algebra with conjunction (intersection), disjunction (union), and implication X→Y = {A : X∩2^A ⊆ Y}; the implication gives the most ambiguous side information needed to decode Y from X. The paper defines an entropy for hyperconfusions as a rate-distortion minimum over confusable sets, and an 'unconfusing lemma' converts a hyperconfusion to an ordinary random variable with at most logarithmic overhead, using the strong functional representation lemma.","core_discovery":"The central claim is that for a communication network, if the requirements can be written as an inclusion M ⊆ F(X_1,...,X_n) in the lattice of downward-closed hyperconfusions, then the largest (most ambiguous) such M is obtained by evaluating the corresponding intuitionistic formula, and its entropy H(F) is the optimal broadcast rate up to an additive logarithmic term. In the butterfly network with two independent fair bits, the formula (X→Y)∩(Y→X) evaluates to the XOR, whose entropy is 1 bit—the known optimum. More generally, the paper presents a 'coding-logic correspondence' analogous to Curry-Howard, in which proofs in Medvedev logic correspond to universally feasible coding tasks.","pith_inferences":["The Heyting structure suggests a general principle: any communication problem whose constraints are order-theoretic (inclusions) can be solved by evaluating the corresponding formula; problems with cost constraints that are not order-theoretic (e.g., requiring determinism or bounded encoding) may need a refined measure such as the coarse entropy introduced for Slepian-Wolf.","The connection with Medvedev logic implies that the set of trivial coding tasks (tasks solvable with no prior information) is exactly the set of theorems of Medvedev logic; this gives a precise logical characterization of 'free' communication.","A testable extension: apply the formula-evaluation method to a new network (e.g., a multi-hop multicast) and compare the predicted entropy with capacity results from linear network coding; a superlogarithmic gap would indicate a missing constraint in the modeling.","The diversity between ordinary information and hyperconfusion resembles the relationship between classical and quantum information (superposition vs. measurement), suggesting that 'deferred measurement' strategies in coding can be formalized through the unconfusing lemma."],"forward_implications":["If correct, optimal codes for a wide class of zero-error networks can be computed mechanically by simplifying a logical formula and evaluating it over hyperconfusions.","The butterfly network's optimal message is exactly the biconditional (X→Y)∩(Y→X), unifying user requirements into a single 'most ambiguous' message.","The framework yields an operational meaning for min-entropy: H∞(M→F) quantifies the negative log success probability when errors are allowed.","The unconfusing lemma implies that any hyperconfusion solution can be converted to a standard random-variable code within O(log H) bits, so the correspondence is not merely abstract.","The same formalism covers index coding, multiple-message networks (erasure, Gray-Wyner), and zero-error joint source-channel coding via confusion ratios."],"fun_headline_variants":["Networks as logic: cost is hypergraph entropy","Hypergraph entropy determines optimal coding cost","From network to formula: optimal rate via entropy","Coding-logic bridge: entropy gives optimal rate","Logical view of networks yields coding optimum"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"Every coding requirement must be expressible as an inclusion M ⊆ F(X1,...,Xn) in the lattice of downward-closed hyperconfusions on a known finite probability space; if a task imposes constraints not of this inclusion form (e.g., requiring the encoder's knowledge to be a subset of the message), the plain entropy formula fails.","fun_headline_variants_meta":{"raw":{"variants":["Networks as logic: cost is hypergraph entropy","Hypergraph entropy determines optimal coding cost","From network to formula: optimal rate via entropy","Coding-logic bridge: entropy gives optimal rate","Logical view of networks yields coding optimum"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000211,"raw_usage":{"total_tokens":1212,"prompt_tokens":664,"completion_tokens":548,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":408,"completion_tokens_details":{"reasoning_tokens":479}},"tokens_in":408,"tokens_out":548,"duration_ms":5548,"temperature":1.0,"reasoning_tokens":479,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T14:10:48.669034+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compare the formula entropy H((X→Y)∩(Y→X)) with the true zero-error rate for a butterfly network where X and Y are independent bits with unequal probabilities p and 1-p; if the difference exceeds the claimed logarithmic bound, the correspondence is false. Alternatively, exhibit a hyperconfusion X where the minimal entropy among ordinary refinements Y⊆X is more than H(X)+log(H(X)+3.4)+1, refuting the unconfusing lemma.","supporting_citations":[],"review_version":1}