Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Coding-Logic Correspondence: Turning Information and Communication Networks into Logical Formulae via Hypergraph Heyting Algebra

T0 review · 3 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read 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

desk verdict 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. read the letter →

arxiv 2512.21112 v2 pith:4TBOTY3C submitted 2025-12-24 cs.IT math.ITmath.LO

Cheuk Ting Li This is my paper · ORCID
classification cs.ITmath.ITmath.LO MSC 94A1503B2094A17
keywords confusionhypergraphHeytingalgebraintuitionisticlogicnetworkcodingindexSlepian-Wolfzero-errorentropy
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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

3 major / 4 minor

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.

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 (3)
  1. [Abstract and Section V-I] 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.
  2. [Section V-C, Theorem 21] 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.
  3. [Section V-I and Section VII] 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.
minor comments (4)
  1. [Definition 5] 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).
  2. [Figure 1 and 2] 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.
  3. [Definition 2] 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.
  4. [Appendix H] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the butterfly computation is derived from definitions and a cited external lemma, with only a scope limitation in Section V-I.

full rationale

Checked the claimed derivation chain. The central butterfly claim (Theorem 21) does not reduce to its inputs: H(M*) is defined by the independent rate-distortion-like minimization in Definition 3; M* = (X->Y) ∩ (Y->X) is not fitted but is the universal most-ambiguous hyperconfusion satisfying the two decodability inclusions; the lower bound H(M*) <= H* follows from monotonicity and the implication adjunction, and the upper bound comes from the unconfusing lemma. The unconfusing lemma (Lemma 7) is proved using the strong functional representation lemma [32,74,33]; although [74] and [33] are authored by the same researcher, the lemma is an external published coding theorem with stated assumptions and is used as a proof ingredient, not as an assumption of the target result. The two-bit XOR computation is obtained by explicit enumeration of the hyperconfusions, not by fitting. The Heyting-algebra/Medvedev-logic characterization (Theorem 22) is proved by a homomorphism to the dual Heyting algebra, not imported. The only caveat worth flagging is scope, not circularity: Section V-I explicitly says that for Slepian-Wolf coding H(M*) is not the correct cost and that converting M* to an ordinary message may break X ⊆ hat(M*), so the plain hypergraph-entropy formula is not universal. That limitation contradicts the abstract's 'simply given by the entropy' phrasing but does not make the butterfly derivation circular. No fitted parameter is renamed as a prediction, and no load-bearing claim rests on a definitional identity.

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

The central claim does not fit parameters to data. Its main load-bearing inputs are the interpretation of information as hyperconfusions and the logarithmic-gap unconfusing lemma. No free parameters were fitted. The invented entity 'hyperconfusion' is the framework itself.

assumptions (4)
  • domain assumption A piece of information can be fully described by a downward-closed confusion hypergraph over a sample space Ω, and knowing it means receiving a set A ∈ X with ω ∈ A.
    The entire operational semantics of the paper rests on this interpretation; if real coding constraints are not captured by confusable sets, the correspondence fails.
  • standard math The strong functional representation lemma (cited as [32], [33], [74]) provides the logarithmic-gap conversion used in the unconfusing lemma.
    Invoked in Appendix C to prove Lemmas 7 and 24; the gap constants come from this theorem.
  • domain assumption The probability space is finite and the distribution p is known; conditioning and independence of hyperconfusions are defined via maximal confusable sets.
    All coding theorems are for finite zero-error settings; infinite/countable settings appear only in the Medvedev-logic characterization.
  • standard math Medvedev logic and the logic of infinite problems correctly characterize the logical formulae that always evaluate to the top hyperconfusion.
    Used as an external known result in Theorem 22, proved via the Kripke-frame duality argument in Appendix H.
invented entities (1)
  • Hyperconfusion (confusion hypergraph)
    purpose: Generalized model of information as a downward-closed family of confusable subsets, replacing random variables/partitions and supporting conjunction, disjunction, and implication.
    It is a new mathematical object introduced to make the coding-logic correspondence work; operational evidence is internal to the paper via optimality theorems, not an independently observable prediction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Coding-Logic Correspondence: Turning Information and Communication Networks into Logical Formulae via Hypergraph Heyting Algebra." pith.science (2026). https://pith.science/paper/4TBOTY3C

@misc{pith2026251221112,
  author       = {Pith},
  title        = {Pith review of: Coding-Logic Correspondence: Turning Information and Communication Networks into Logical Formulae via Hypergraph Heyting Algebra},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4TBOTY3C}},
  note         = {Machine review of arXiv:2512.21112}
}
read the original abstract

We propose using confusion hypergraph (hyperconfusion) as a model of information. In contrast to the conventional approach using random variables, we can now perform conjunction, disjunction and implication of information, forming a Heyting algebra. Using the connection between Heyting algebra and intuitionistic logic, we can express the requirements of a communication network (e.g., network coding, index coding, Slepian-Wolf coding) as a logical formula, allowing us to use the hypergraph Heyting algebra to directly compute the optimal coding scheme. The optimal communication cost is simply given by the entropy of the hypergraph (within a logarithmic gap). This gives a surprising correspondence between coding settings and logical formulae, similar to the Curry-Howard correspondence between computer programs and proofs.

Figures

Figures reproduced from arXiv: 2512.21112 by the authors.

Figure 1
Figure 1. Correspondence between coding setting (e.g., butterfly network) and logical formula. The optimal code can be computed via confusion hypergraphs. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. The hyperconfusion U = sing(Ω) over Ω = {0, 1}, its embeddings X, Y in Ω2 , and the operations X ∩ Y = U ⊗ U, X ∪ Y and X → Y. The blue circles are maximal confusable sets (no strict supersets are confusable). A. Conjunction and Product of Information Given two hyperconfusions X, Y, their conjunction is X ∩ Y, where a set A is confusable if and only if it is confusable in both X and Y. Intuitively, X ∩ Y is the know… view at source ↗
Figure 1
Figure 1. Consider the singleton hyperconfusion U = {∅, {0}, {1}} over the uniform probability space over {0, 1}, and its 2-fold product (Definition 9), giving an i.i.d. hyperconfusion sequence X, Y over the sample space {0, 1} 2 = {00, 01, 10, 11}, as in (3). X and Y correspond to the information of the first and second bit, respectively. Direct computation yields X → Y = {∅, {00}, {01}, {10}, {11}, {00, 10}, {00, 11}, {01, … view at source ↗
Figures from the paper (1 more)
Figure 3
Figure 3. Figure 3: Hasse diagram of the hyperconfusions generated by [PITH_FULL_IMAGE:figures/full_fig_p019_3.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Non-Probabilistic Game-Theoretic Information Theory Which Subsumes Probabilistic Channel Coding

    cs.IT 2026-04 unverdicted novelty 8.0 of 10

    A game-theoretic information theory with dynamic hedging and nonconvex downward-closed cones subsumes probabilistic channel coding theorems and adversarial settings.

Reference graph

Works this paper leans on

75 extracted references · 2 linked inside Pith · cited by 1 Pith paper

  1. [1]

    On the amount of information,

    K. T. Hu, “On the amount of information,”Theory of Probability & Its Applications, vol. 7, no. 4, pp. 439–447, 1962

    1962

  2. [2]

    T. M. Cover and J. A. Thomas,Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). USA: Wiley-Interscience, 2006

    2006

  3. [3]

    A new outlook on Shannon’s information measures,

    R. W. Yeung, “A new outlook on Shannon’s information measures,”IEEE Transactions on Information Theory, vol. 37, no. 3, pp. 466–474, 1991

    1991

  4. [4]

    An introduction to partition logic,

    D. Ellerman, “An introduction to partition logic,”Logic Journal of IGPL, vol. 22, no. 1, pp. 94–125, 2014

    2014

  5. [5]

    Logical information theory: new logical foundations for information theory,

    ——, “Logical information theory: new logical foundations for information theory,”Logic Journal of the IGPL, vol. 25, no. 5, pp. 806–835, 2017

    2017

  6. [6]

    Logical entropy: Introduction to classical and quantum logical information theory,

    ——, “Logical entropy: Introduction to classical and quantum logical information theory,”Entropy, vol. 20, no. 9, p. 679, 2018. 27

    2018

  7. [7]

    A logarithmic decomposition for information,

    K. J. Down and P. A. Mediano, “A logarithmic decomposition for information,” in2023 IEEE International Symposium on Information Theory (ISIT). IEEE, 2023, pp. 150–155

    2023

  8. [8]

    A Poisson decomposition for information and the information-event diagram,

    C. T. Li, “A Poisson decomposition for information and the information-event diagram,”IEEE Transactions on Information Theory, vol. 71, no. 7, pp. 4939–4952, 2025

    2025

Show all 75 references
  1. [9]

    On the capacity of uniform hypergraphs,

    J. Korner and K. Marton, “On the capacity of uniform hypergraphs,”IEEE Transactions on Information Theory, vol. 36, no. 1, pp. 153–156, 1990

    1990

  2. [10]

    Entanglement-assisted zero-error communication,

    S. Adei, “Entanglement-assisted zero-error communication,” 2023

    2023

  3. [11]

    Die formalen regeln der intuitionistischen logik,

    A. Heyting, “Die formalen regeln der intuitionistischen logik,”Sitzungsbericht PreuBische Akademie der Wissenschaften Berlin, physikalisch- mathematische Klasse II, pp. 42–56, 1930

    1930

  4. [12]

    Esakia,Heyting Algebras: Duality Theory, ser

    L. Esakia,Heyting Algebras: Duality Theory, ser. Trends in Logic, G. Bezhanishvili and W. H. Holliday, Eds. Springer, 2019, vol. 50

    2019

  5. [13]

    Finite problems,

    Y . T. Medvedev, “Finite problems,”Soviet Mathematics - Doklady, vol. 3, no. 1, pp. 227–230, 1962, english translation of the Russian article in Doklady Akademii Nauk SSSR, 142:5, 1015-1018, 1962

    1962

  6. [14]

    Intermediate logics and factors of the Medvedev lattice,

    A. Sorbi and S. A. Terwijn, “Intermediate logics and factors of the Medvedev lattice,”Annals of Pure and Applied Logic, vol. 155, no. 2, 2008

    2008

  7. [15]

    Network information flow,

    R. Ahlswede, N. Cai, S.-Y . R. Li, and R. W. Yeung, “Network information flow,”IEEE Transactions on Information Theory, vol. 46, no. 4, pp. 1204–1216, 2000

    2000

  8. [16]

    R. W. Yeung,Information theory and network coding. Springer Science & Business Media, 2008

    2008

  9. [17]

    Über die bausteine der mathematischen logik,

    M. Schönfinkel, “Über die bausteine der mathematischen logik,”Mathematische Annalen, vol. 92, no. 3, pp. 305–316, 1924

    1924

  10. [18]

    H. B. Curry and R. Feys,Combinatory Logic. Amsterdam: North-Holland Publishing Company, 1958, vol. 1

    1958

  11. [19]

    I. M. Copi, C. Cohen, and K. McMahon,Introduction to logic. Routledge, 2016

    2016

  12. [20]

    Linear network coding,

    S.-Y . Li, R. W. Yeung, and N. Cai, “Linear network coding,”IEEE Transactions on Information Theory, vol. 49, no. 2, pp. 371–381, 2003

    2003

  13. [21]

    Informed-source coding-on-demand (ISCOD) over broadcast channels,

    Y . Birk and T. Kol, “Informed-source coding-on-demand (ISCOD) over broadcast channels,” inProceedings. IEEE INFOCOM’98, the Conference on Computer Communications, vol. 3. IEEE, 1998, pp. 1257–1264

    1998

  14. [22]

    Index coding with side information,

    Z. Bar-Yossef, Y . Birk, T. Jayram, and T. Kol, “Index coding with side information,”IEEE Transactions on Information Theory, vol. 57, no. 3, pp. 1479–1494, 2011

    2011

  15. [23]

    On the index coding problem and its relation to network coding and matroid theory,

    S. El Rouayheb, A. Sprintson, and C. Georghiades, “On the index coding problem and its relation to network coding and matroid theory,”IEEE Transactions on Information Theory, vol. 56, no. 7, pp. 3187–3195, 2010

    2010

  16. [24]

    Noiseless coding of correlated information sources,

    D. Slepian and J. K. Wolf, “Noiseless coding of correlated information sources,”IEEE Trans. Inf. Theory, vol. 19, no. 4, pp. 471–480, Jul. 1973

    1973

  17. [25]

    Source coding for a simple network,

    R. Gray and A. Wyner, “Source coding for a simple network,”Bell System Technical Journal, vol. 53, no. 9, pp. 1681–1721, 1974

    1974

  18. [26]

    The formulae-as-types notion of construction,

    W. A. Howard, “The formulae-as-types notion of construction,” inTo H.B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, J. P. Seldin and J. R. Hindley, Eds. Academic Press, 1980, pp. 479–490

    1980

  19. [27]

    A. S. Troelstra and D. van Dalen,Constructivism in Mathematics: An Introduction, ser. Studies in Logic and the Foundations of Mathematics. Amsterdam, Netherlands: North-Holland, 1988, vol. 1

    1988

  20. [28]

    New bounds for perfect hashing via information theory,

    J. Korner and K. Marton, “New bounds for perfect hashing via information theory,”European Journal of Combinatorics, vol. 9, no. 6, pp. 523–530, 1988

    1988

  21. [29]

    Graph entropy: a survey,

    G. Simonyi, “Graph entropy: a survey,”Combinatorial Optimization, vol. 20, pp. 399–441, 1995

    1995

  22. [30]

    Coding of an information source having ambiguous alphabet and the entropy of graphs,

    J. Korner, “Coding of an information source having ambiguous alphabet and the entropy of graphs,” in6th Prague conference on Information Theory, etc.Academia, Prague, 1971, pp. 411–425

    1971

  23. [31]

    A method for the construction of minimum-redundancy codes,

    D. A. Huffman, “A method for the construction of minimum-redundancy codes,”Proceedings of the IRE, vol. 40, no. 9, pp. 1098–1101, 1952

    1952

  24. [32]

    Strong functional representation lemma and applications to coding theorems,

    C. T. Li and A. El Gamal, “Strong functional representation lemma and applications to coding theorems,”IEEE Transactions on Information Theory, vol. 64, no. 11, pp. 6967–6978, Nov 2018

    2018

  25. [33]

    Discrete layered entropy, conditional compression and a tighter strong functional representation lemma,

    C. T. Li, “Discrete layered entropy, conditional compression and a tighter strong functional representation lemma,” in2025 IEEE International Symposium on Information Theory (ISIT), 2025

    2025

  26. [34]

    The zero error capacity of a noisy channel,

    C. Shannon, “The zero error capacity of a noisy channel,”IRE transactions on information theory, vol. 2, no. 3, pp. 8–19, 1956

    1956

  27. [35]

    The Shannon capacity of a graph and the independence numbers of its powers,

    N. Alon and E. Lubetzky, “The Shannon capacity of a graph and the independence numbers of its powers,”IEEE Transactions on Information Theory, vol. 52, no. 5, pp. 2172–2176, 2006

    2006

  28. [36]

    Zero error capacity under list decoding,

    P. Elias, “Zero error capacity under list decoding,”IEEE Transactions on Information Theory, vol. 34, no. 5, pp. 1070–1074, 1988

    1988

  29. [37]

    A formulae-as-type notion of control,

    T. G. Griffin, “A formulae-as-type notion of control,” inProceedings of the 17th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ser. POPL ’90. ACM, 1990, pp. 47–58

    1990

  30. [38]

    Logic of infinite problems and Kripke models on atomic semilattices of sets,

    D. P. Skvortsov, “Logic of infinite problems and Kripke models on atomic semilattices of sets,” inDoklady Akademii Nauk, vol. 245, no. 4. Russian Academy of Sciences, 1979, pp. 798–801

    1979

  31. [39]

    Common information is far less than mutual information,

    P. Gács and J. Körner, “Common information is far less than mutual information,”Problems of Control and Information Theory, vol. 2, no. 2, pp. 149–162, 1973

    1973

  32. [40]

    Information lattices and subgroup lattices: Isomorphisms and approximations,

    H. Li and E. K. Chong, “Information lattices and subgroup lattices: Isomorphisms and approximations,” inProceedings of the 45th Annual Allerton Conference on Communication, Control and Computing, Monticello, Illinois, 2007

    2007

  33. [41]

    Possible generalization of Boltzmann-Gibbs statistics,

    C. Tsallis, “Possible generalization of Boltzmann-Gibbs statistics,”Journal of statistical physics, vol. 52, pp. 479–487, 1988

    1988

  34. [42]

    The common information of two dependent random variables,

    A. D. Wyner, “The common information of two dependent random variables,”IEEE Transactions on Information Theory, vol. 21, no. 2, pp. 163–179, 1975

    1975

  35. [43]

    Exact common information,

    G. R. Kumar, C. T. Li, and A. El Gamal, “Exact common information,” inProc. IEEE Int. Symp. Inf. Theory, June 2014, pp. 161–165

    2014

  36. [44]

    Extended Gray–Wyner system with complementary causal side information,

    C. T. Li and A. El Gamal, “Extended Gray–Wyner system with complementary causal side information,”IEEE Transactions on Information Theory, vol. 64, no. 8, pp. 5862–5878, 2017

    2017

  37. [45]

    An inequality on guessing and its application to sequential decoding,

    E. Arikan, “An inequality on guessing and its application to sequential decoding,”IEEE Transactions on Information Theory, vol. 42, no. 1, pp. 99–105, 1996

    1996

  38. [46]

    Encoding tasks and rényi entropy,

    C. Bunte and A. Lapidoth, “Encoding tasks and rényi entropy,”IEEE Transactions on Information Theory, vol. 60, no. 9, pp. 5065–5076, 2014

    2014

  39. [47]

    Semantic information,

    Y . Bar-Hillel and R. Carnap, “Semantic information,”The British journal for the philosophy of science, vol. 4, no. 14, pp. 147–157, 1953

    1953

  40. [48]

    Towards a unification of logic and information theory,

    L. A. Lastras, B. Trager, J. Lenchner, W. Szpankowski, C. W. Wu, M. Squillante, and A. Gray, “Towards a unification of logic and information theory,” arXiv preprint arXiv:2301.10414, 2023

    2023 arXiv

  41. [49]

    Eijck and A

    J. Eijck and A. Visser,Logic and information flow. MIT Press, 1994

    1994

  42. [50]

    On the logic of information flow,

    J. Barwise, D. Gabbay, and C. Hartonas, “On the logic of information flow,”Logic Journal of IGPL, vol. 3, no. 1, pp. 7–49, 1995

    1995

  43. [51]

    J. R. Munkres,Elements of algebraic topology. CRC press, 2018

    2018

  44. [52]

    Symmetric heyting relation algebras with applications to hypergraphs,

    J. G. Stell, “Symmetric heyting relation algebras with applications to hypergraphs,”Journal of Logical and Algebraic Methods in Programming, vol. 84, no. 3, pp. 440–455, 2015

    2015

  45. [53]

    Berger,Rate Distortion Theory: A Mathematical Basis for Data Compression

    T. Berger,Rate Distortion Theory: A Mathematical Basis for Data Compression. Prentice-Hall, NJ, USA, 1971

    1971

  46. [54]

    Relaxations of vertex packing,

    M. Grötschel, L. Lovász, and A. Schrijver, “Relaxations of vertex packing,”Journal of Combinatorial Theory, Series B, vol. 40, no. 3, pp. 330–343, 1986

    1986

  47. [55]

    Entropy splitting for antiblocking corners and perfect graphs,

    I. Csiszár, J. Körner, L. Lovász, K. Marton, and G. Simonyi, “Entropy splitting for antiblocking corners and perfect graphs,”Combinatorica, vol. 10, no. 1, pp. 27–40, 1990

    1990

  48. [56]

    On measures of entropy and information,

    A. Rényi, “On measures of entropy and information,” inProceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics. The Regents of the University of California, 1961. 28

    1961

  49. [57]

    Transmission of information,

    R. V . Hartley, “Transmission of information,”Bell System technical journal, vol. 7, no. 3, pp. 535–563, 1928

    1928

  50. [58]

    Esakia duals of regular Heyting algebras,

    G. Grilletti and D. E. Quadrellaro, “Esakia duals of regular Heyting algebras,”Algebra Universalis, vol. 85, no. 5, p. Article 5, 2024

    2024

  51. [59]

    M. A. Nielsen and I. L. Chuang,Quantum computation and quantum information. Cambridge university press, 2010

    2010

  52. [60]

    A propositional calculus with denumerable matrix,

    M. Dummett, “A propositional calculus with denumerable matrix,”The Journal of Symbolic Logic, vol. 24, no. 2, pp. 97–106, 1959

    1959

  53. [61]

    Polynomial codes over certain finite fields,

    I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,”Journal of the Society for Industrial and Applied Mathematics, vol. 8, no. 2, pp. 300–304, 1960

    1960

  54. [62]

    Eine unableitbarkeitsbeweismethode für den intuitionistischen aussagenkalkül,

    G. Kreisel and H. Putnam, “Eine unableitbarkeitsbeweismethode für den intuitionistischen aussagenkalkül,”Archiv für mathematische Logik und Grundlagenforschung, vol. 3, no. 3, pp. 74–78, 1957

    1957

  55. [63]

    Some results on intermediate constructive logics,

    P. Miglioli, U. Moscato, M. Ornaghi, S. Quazza, and G. Usberti, “Some results on intermediate constructive logics,”Notre Dame Journal of Formal Logic, vol. 30, no. 4, pp. 543–562, 1989

    1989

  56. [64]

    An intermediate logic contained in Medvedev’s logic with disjunction property,

    Z. Chen, “An intermediate logic contained in Medvedev’s logic with disjunction property,”arXiv preprint arXiv:2502.17242, 2025

    2025 arXiv

  57. [65]

    Aubin and H

    J.-P. Aubin and H. Frankowska,Set-Valued Analysis, 1st ed., ser. Modern Birkhäuser Classics. Birkhäuser Boston, MA, 2009

    2009

  58. [66]

    Relative capacity and dimension of graphs,

    J. Körner and K. Marton, “Relative capacity and dimension of graphs,”Discrete Mathematics, vol. 235, no. 1-3, pp. 307–315, 2001

    2001

  59. [67]

    Graph information ratio,

    L. Wang and O. Shayevitz, “Graph information ratio,”SIAM Journal on Discrete Mathematics, vol. 31, no. 4, pp. 2703–2734, 2017

    2017

  60. [68]

    Computation of channel capacity and rate-distortion functions,

    R. Blahut, “Computation of channel capacity and rate-distortion functions,”IEEE Transactions on Information Theory, vol. 18, no. 4, pp. 460–473, 1972

    1972

  61. [69]

    An algorithm for computing the capacity of arbitrary discrete memoryless channels,

    S. Arimoto, “An algorithm for computing the capacity of arbitrary discrete memoryless channels,”IEEE Transactions on Information Theory, vol. 18, no. 1, pp. 14–20, 1972

    1972

  62. [70]

    The theory of representation for Boolean algebras,

    M. H. Stone, “The theory of representation for Boolean algebras,”Transactions of the American Mathematical Society, vol. 40, no. 1, pp. 37–111, 1936

    1936

  63. [71]

    On join-dense subsets of certain families of aggregation functions,

    R. Halaš, J. Pócs, and J. Pócsová, “On join-dense subsets of certain families of aggregation functions,”Mathematics, vol. 11, no. 1, p. 14, 2022

    2022

  64. [72]

    P. R. Halmos,Lectures on Boolean algebras. Courier Dover Publications, 2018

    2018

  65. [73]

    Join-prime elements in semidistributive lattices,

    H. Gaskill and J. Nation, “Join-prime elements in semidistributive lattices,”Algebra Universalis, vol. 12, no. 1, pp. 352–359, 1981

    1981

  66. [74]

    Channel simulation: Theory and applications to lossy compression and differential privacy,

    C. T. Li, “Channel simulation: Theory and applications to lossy compression and differential privacy,”Foundations and Trends® in Communications and Information Theory, vol. 21, no. 6, pp. 847–1106, 2024. [Online]. Available: http://dx.doi.org/10.1561/0100000141

    2024 doi

  67. [75]

    The proof theory and semantics of intuitionistic modal logic,

    A. K. Simpson, “The proof theory and semantics of intuitionistic modal logic,” Ph.D. dissertation, College of Science and Engineering, University of Edinburgh, 1994

    1994

Pith tools

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