Pith. sign in

REVIEW 4 minor 28 references

Coatom Enumeration in Hypergraph Horn Functions: Rank-Three Representations of Horn Model Posets

T0 review · 0 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read A new construction converts any Horn CNF into a rank-three hypergraph whose coatoms are exactly the maximal models, yielding sharp complexity thresholds for coatom enumeration.

desk verdict A solid, genuinely new representation theorem for Horn model posets that transfers known hardness to coatom enumeration, with a clean threshold classification; worth a serious referee. read the letter →

arxiv 2608.06820 v1 pith:HEXN2AHQ submitted 2026-08-07 math.CO cs.DS

Jianshen Zhu This is my paper · ORCID
classification math.COcs.DS
keywords HornCNFhypergraphfunctioncoatomstoppingsetantikeyoutput-sensitiveenumerationclosuresystemminimal
topics P versus NP
open problems P versus NP
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

The paper proves that every Horn formula can be re-encoded as a rank-at-most-three hypergraph Horn function with only linear blow-up, in such a way that the inclusion order of the models is preserved and every model gets a unique extension to a target model. This makes the maximal models of the original formula correspond one-to-one to the coatoms of the hypergraph closure system, which are the complements of the minimal nonempty stopping sets. The encoding is a bridge that transfers known hardness of maximal Horn model enumeration: unless P=NP, listing all coatoms from the hypergraph incidence representation is not output-polynomial, even when every hyperedge has size two or three and every element occurs at most three times. On the positive side, the paper shows that rank at most two and maximum element frequency at most two both admit output-linear total-time enumeration, so these thresholds are conditionally sharp. The same representation also implies that every finite lattice is isomorphic to the proper-model poset of a rank-three hypergraph Horn function.

What carries the argument

The machinery is a library of hyperedge gadgets that realize Boolean relations through the stopping-set condition $|A\cap S|\neq 1$. A single edge $\{p,q\}$ enforces equality; the implication gadget $\mathrm{Imp}(x,y;q)=\{\{y,q\},\{x,y,q\}\}$ enforces $x\to y$ with $q=y$; and the OR gadget $\mathrm{OR}(a,b;c,q)=\{\{c,q\},\{a,b,c\},\{a,c,q\}\}$ enforces $c=a\lor b$ with $q=c$, each with a unique extension of the private elements. These gadgets are chained into OR-trees for clause premises, capped by a root construction that separates the all-zero assignment, and assembled into $C(\Gamma)$ so that nonempty stopping sets are exactly the false-variable sets of models. The companion reductions use incidence splitting to cap element frequency at three, the apex multigraph whose graphic circuits are the minimal stopping sets when $\Delta(H)\le 2$, and a local four-triple replacement that turns two-element hyperedges into three-element ones.

What would settle it

Take a small Horn CNF such as $\Gamma=(\{a,b\}\to c)\land(\{d\}\to\bot)$, construct $C(\Gamma)$ by the rules of Theorem 3.11, and list all nonempty stopping sets; if any set fails to be a false-variable set of a model of $\Gamma$, or any model's false-variable set fails to extend to a stopping set, the central representation claim is false.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.11: for every normalized Horn CNF $\Gamma$ on variables $X$, one can construct in $O(\|\Gamma\|_{\mathrm{inc}})$ time a normalized hypergraph $C(\Gamma)$ of rank at most three, with $L(C(\Gamma))=O(\|\Gamma\|_{\mathrm{inc}})$, such that every false-variable set of a model of $\Gamma$ extends uniquely to a nonempty stopping set of $C(\Gamma)$, and this correspondence is an inclusion-order isomorphism. Equivalently, the model poset of $\Gamma$ is isomorphic to the proper-model poset of the hypergraph Horn function $\Phi_{C(\Gamma)}$, so maximal models map bijectively to coatoms. The representation transfers the maximal-Horn-model lower bound of Kavvadias, Sideri, and Stavropoulos: enumerating coatoms from a hypergraph incidence list is not in OutputP unless P=NP, even when every hyperedge has size two or three; after incidence splitting, the same lower bound holds with maximum element frequency at most three, and a local replacement makes the hard hypergraphs three-uniform. The paper also proves the matching positive endpoints: rank at most two and maximum element frequency at most two admit output-linear total-time enumeration, with a polynomial-delay, polynomial-space algorithm in the frequency-two case, while coatom extension is NP-complete already for three-uniform hypergraphs in which every element has frequency exactly two.

Load-bearing premise

The sharp frequency-two positive result assumes that the cycle-listing algorithm of Birmelé et al. runs in time linear in the input plus the total length of all listed cycles; if that external fact fails, the frequency-two boundary degrades from output-linear to merely polynomial total time, while the paper's self-contained polynomial-delay bound remains.

Editorial extensions

If this is right

  • Any Horn CNF can be compiled in linear time into a rank-three hypergraph Horn function whose incidence length is linear in the input, so Horn model posets are represented inside hypergraph Horn posets with no output-size blow-up.
  • Listing all coatoms, equivalently all minimal nonempty stopping sets, from the incidence representation is not in OutputP unless P=NP, even for hypergraphs whose edges have size two or three and whose elements have frequency at most three.
  • For rank at most two, coatoms can be listed in output-linear total time after normalization, because the closure system decomposes into equality components.
  • For maximum element frequency at most two, coatoms correspond to graphic circuits of an apex multigraph, giving output-linear total-time enumeration and a polynomial-delay, polynomial-space algorithm.
  • Coatom extension is NP-complete already on three-uniform, exact-frequency-two hypergraphs, while enumerating all coatoms on that same class is output-linear; the same representation also shows every finite lattice is isomorphic to the proper-model poset of a rank-three hypergraph Horn function.

Reading between the lines

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

  • If the representation theorem is applied to any tractable subclass of Horn formulas, it yields a general reduction template: output-polynomial coatom enumeration for the corresponding rank-three hypergraphs would give output-polynomial maximal-model enumeration for that subclass.
  • Because the paper embeds minimal-transversal enumeration into coatom enumeration by a linear, output-bijective reduction, any future output-polynomial algorithm for HH-Coatom-Enum would also settle the long-open question of output-polynomial minimal-transversal enumeration; the converse does not follow.
  • The paper leaves linear three-uniform hypergraphs (Tanner graphs of girth at least six) and (3,3)-regular inputs open, and a plausible next step is to test whether the lower-bound construction can be made girth-preserving, which the current triangle-replacement method cannot do.
  • From the coding-theory side, the frequency-two positive result suggests that variable-node degree exactly two makes stopping-set enumeration structurally graphic; extending to variable-node degree three may require a different combinatorial characterization than graphic circuits.
Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

  1. Claim #1: The central claim is Theorem 3.11: for every normalized Horn CNF $\Gamma$ on variables $X$, one can construct in $O(\|\Gamma\|_{\mathrm{inc}})$ time a normalized hypergraph $C(\Gamma)$ of rank at most three, with $L(C(\Gamma))=O(\|\Gamma\|_{\mathrm{inc}})$, such that every false-variable set of a model of $\Gamma$ extends uniquely to a nonempty stopping set of $C(\Gamma)$, and this correspondence

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 4 minor

Summary. The paper studies the closure systems defined by hypergraph Horn CNFs and the enumeration of their coatoms, equivalently the minimal nonempty stopping sets of the underlying hypergraph. Its central structural result (Theorem 3.11) is a linear-time, linear-size construction C(Γ) of rank at most three from any normalized Horn CNF Γ, such that nonempty stopping sets of C(Γ) are in inclusion-order bijection with the false-variable sets of models of Γ, with all auxiliary coordinates uniquely determined. This is used to transfer the Kavvadias–Sideri–Stavropoulos lower bounds for maximal Horn model enumeration: HH-Coatom-Enum is not in OutputP unless P=NP, even when every hyperedge has size two or three, and the incremental and extension problems are NP-complete under the same restrictions. Incidence splitting and a local three-uniform replacement extend the hardness to maximum element frequency three, while rank-two and frequency-two classes are shown to admit output-linear total-time enumeration (and polynomial delay with polynomial space in the frequency-two case). Constrained extension is NP-complete even for three-uniform hypergraphs of exact frequency two. The paper also contains a linear-size output-bijective reduction from explicit minimal-transversal enumeration as a separate appendix.

Significance. If correct, the main theorem is a genuine structural representation result: it embeds an arbitrary Horn model poset into the proper-model poset of a rank-three hypergraph Horn function with unique extensions, and it turns maximal-model hardness into coatom hardness without changing the output family. The proof is unusually complete: the gadget lemmas are explicit, the uniqueness and inclusion preservation are checked, the incidence counts are given, and the external KSS reduction is reproduced and verified in Appendix A. The positive algorithms are also concrete, with Appendix C giving a self-contained polynomial-delay, polynomial-space implementation for the frequency-two case. The complexity thresholds are sharp and the classification is falsifiable. The only external algorithmic dependency is the output-linear cycle-listing algorithm of Birmelé et al. used in Corollary 5.7; even if that theorem is read as O(m+c) rather than O(m+total cycle length), the stated O(L+Σ|S|) bound follows by expanding each listed cycle, and the DelayP claim is independent of that dependency. I therefore do not regard the stress-test concern as a threat to the central claims.

minor comments (4)
  1. [§3.3, Corollary 3.13 and §5.4, Theorem 5.11] Several mathematical symbols appear as corrupted characters in the typeset text, notably the isomorphism symbol in Corollary 3.13 and the disjoint-union symbol in Eq. (4); these should be cleaned up in the final version.
  2. [§5.3, Corollary 5.7] The paper should state explicitly whether the linear-time guarantee imported from [4] is in terms of number of cycles or total cycle length, and, if the former, add one sentence showing that O(m+c) implies the displayed O(L(H)+Σ(|S|+1)) bound after expanding each cycle.
  3. [§5.4, Theorem 5.11] In Eq. (4), the notation MinStop(H) ¤∪ D(H) would be clearer as a disjoint union with an explicit note that members of MinStop(H) are viewed as subsets of the enlarged ground set; the current symbol is ambiguous.
  4. [Figure 1] The edge labels EEq, EImp, and EOR use an unexplained prefix; if these denote the hyperedge families, they should be defined in the caption or in the surrounding text.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the representation theorem is proven from explicit gadgets, the hardness transfer uses independent external reductions, and the only external cycle-listing dependency is independent rather than self-referential.

full rationale

The central derivation chain in Sections 3–5 is self-contained and does not reduce to its inputs by construction. Lemmas 3.1–3.5 prove the equality, implication, OR, OR-tree, and root gadgets directly from the stopping-set condition; Lemmas 3.6–3.10 then prove the inclusion-order isomorphism of Theorem 3.11 from those gadgets, with linear-size accounting in Lemma 3.10. No parameter is fitted to the output family, and no target object is defined in terms of the theorem being proved. Section 4 transfers the maximal-Horn-model lower bound of Kavvadias–Sideri–Stavropoulos, an independent external theorem whose reduction is reproduced and verified in Appendix A; this is a standard NP-hardness transfer, not a self-citation. Section 5's positive results are proven by explicit algorithms: connected components for rank-two inputs and graphic circuits for frequency-two inputs. The output-linear frequency-two bound in Corollary 5.7 invokes the independent optimal cycle-listing algorithm of Birmelé et al.; that is an external benchmark with stated assumptions, not a self-citation or a fitted-input-as-prediction, and Appendix C supplies a self-contained polynomial-delay implementation for the same class. There are no self-citations, no author-imported uniqueness theorem, and no ansatz smuggled in by citation. The only mild dependence—the Birmelé output-linear claim—is isolated to one positive boundary and does not make any derivation equivalent to its own inputs, so the appropriate finding is no circularity.

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

There are no fitted or hand-chosen numeric parameters; all constants in the complexity bounds are derived by explicit counting. The constructions introduce many auxiliary ground elements (private q's, root r/ρ, terminals t_v, occurrence elements v_A, and fresh elements of the W gadget), but these are fully constructed and proven to behave as specified; they are proof artifacts rather than unverified postulates, so no invented-entity entries are appropriate under the graviton-problem criterion.

assumptions (6)
  • domain assumption Positive One-in-Three 3SAT is NP-complete (Schaefer's theorem).
    Used in Theorem 4.5 via Appendix A to build the hard Horn family Γ_F; classical complexity result.
  • domain assumption Hamiltonian Cycle is NP-complete for planar cubic 3-connected graphs (Garey, Johnson, Tarjan).
    Used in Theorem 5.8 for the exact-frequency-two extension lower bound.
  • domain assumption The optimal cycle-listing algorithm of Birmelé et al. runs in output-linear total time.
    External tool used in Corollary 5.7 to claim output-linear enumeration for the frequency-two class; Appendix C gives an alternative polynomial-delay implementation.
  • standard math Graphic matroid circuits are exactly loops, parallel pairs, and simple cycles.
    Used in Proposition 5.6 to identify minimal stopping sets with graphic circuits of the apex multigraph.
  • standard math Every finite closure system has an implicational basis; every finite lattice is a principal-ideal closure system.
    Used in Corollary 3.13 to state the consequence that every finite lattice embeds as the proper-model poset of a rank-three hypergraph Horn function.
  • domain assumption The OutputP and DelayP conventions match the standard output-sensitive complexity definitions.
    Section 2.3 fixes these conventions; the lower-bound and positive-result statements depend on them.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Coatom Enumeration in Hypergraph Horn Functions: Rank-Three Representations of Horn Model Posets." pith.science (2026). https://pith.science/paper/HEXN2AHQ

@misc{pith2026260806820,
  author       = {Pith},
  title        = {Pith review of: Coatom Enumeration in Hypergraph Horn Functions: Rank-Three Representations of Horn Model Posets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HEXN2AHQ}},
  note         = {Machine review of arXiv:2608.06820}
}
abstract

For a finite hypergraph H, the complements of the models of its associated definite Horn CNF are exactly the stopping sets of H; hence the complements of its coatoms are the inclusion-minimal nonempty stopping sets. We study their output-sensitive enumeration from the hypergraph incidence representation. Our main result is a representation of arbitrary Horn model posets whose incidence size is linear in the incidence length of the normalized Horn input. Given a Horn CNF $\Gamma$, we construct a hypergraph $C(\Gamma)$ of rank at most three whose proper-model poset is inclusion-order isomorphic to the model poset of $\Gamma$; equivalently, each source model has a unique extension to a proper target model. Thus maximal models of $\Gamma$ correspond bijectively to target coatoms. Combining this representation with the maximal-model construction of Kavvadias, Sideri, and Stavropoulos shows that coatom enumeration is not in OutputP unless P=NP, even when all hyperedges have size two or three. Incidence splitting reduces maximum element frequency to three while preserving the stopping-set poset, and a local replacement of two-element hyperedges yields the same lower bound for three-uniform hypergraphs of maximum element frequency at most three. These thresholds are conditionally sharp for arbitrary-order enumeration: rank at most two and maximum element frequency at most two both admit output-linear total-time generation; in the frequency-two case, a polynomial-delay, polynomial-space algorithm is also available. In contrast, coatom extension is NP-complete already for three-uniform hypergraphs of exact element frequency two.

Figures

Figures reproduced from arXiv: 2608.06820 by the authors.

Figure 1
Figure 1. Local stopping-set constructions. Each panel shows the relation on the interface elements [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. The block 𝐵𝑣 for a source element 𝑣 belonging to four hyperedges 𝐴1, . . . , 𝐴4. Each incidence 𝑣 ∈ 𝐴𝑖 is represented by a distinct occurrence element 𝑣𝐴𝑖 contained in the replacement hyperedge 𝐴 ◦ 𝑖 . The dashed attachments indicate this membership and are not hyperedges. The vertices 𝑢1, 𝑢2, 𝑢3 are fresh internal vertices of the subcubic tree 𝑇𝑣, while every solid edge is a two-element hyperedge. These edges force… view at source ↗
Figure 3
Figure 3. The edge of 𝑄H associated with a ground element of frequency two, one, or zero. Hyperedges of H become vertices, while the apex 𝛼 supplies any missing incidence endpoint. 5.3 Frequency at most two The frequency-two case admits a direct graph-theoretic representation. When every ground element belongs to at most two hyperedges, the hyperedges can be viewed as vertices of a multigraph and the ground elements as labele… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 16 canonical work pages

  1. [1]

    Algorithms for𝑘-meet-semidistributive lattices.Theoretical Computer Science, 658:391–398, 2017

    Laurent Beaudou, Arnaud Mary, and Lhouari Nourine. Algorithms for𝑘-meet-semidistributive lattices.Theoretical Computer Science, 658:391–398, 2017. doi: 10.1016/j.tcs.2015.10.029

    work page doi:10.1016/j.tcs.2015.10.029 2017

  2. [2]

    Hypergraph Horn functions.SIAM Journal on Discrete Mathematics, 38(2):1417–1437, 2024

    Kristóf Bérczi, Endre Boros, and Kazuhisa Makino. Hypergraph Horn functions.SIAM Journal on Discrete Mathematics, 38(2):1417–1437, 2024. doi: 10.1137/23M1569162

    doi:10.1137/23m1569162 2024

  3. [3]

    Lattices, closures systems and implication bases: A survey of structural aspects and algorithms.Theoretical Computer Science, 743:93–109, 2018

    Karell Bertet, Christophe Demko, Jean-François Viaud, and Clément Guérin. Lattices, closures systems and implication bases: A survey of structural aspects and algorithms.Theoretical Computer Science, 743:93–109, 2018. doi: 10.1016/j.tcs.2016.11.021

    doi:10.1016/j.tcs.2016.11.021 2018

  4. [4]

    Ferreira, Roberto Grossi, Andrea Marino, Nadia Pisanti, Romeo Rizzi, andGustavoSacomoto

    Étienne Birmelé, Rui A. Ferreira, Roberto Grossi, Andrea Marino, Nadia Pisanti, Romeo Rizzi, andGustavoSacomoto. Optimallistingofcyclesand 𝑠𝑡-pathsinundirectedgraphs. InProceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1884–1896. SIAM, 2013. doi: 10.1137/1.9781611973105.134

    work page doi:10.1137/1.9781611973105.134 2013

  5. [5]

    Dualization in lattices given by implicational bases

    Oscar Defrain and Lhouari Nourine. Dualization in lattices given by implicational bases. Theoretical Computer Science, 814:169–176, 2020. doi: 10.1016/j.tcs.2020.01.028. 28

    work page doi:10.1016/j.tcs.2020.01.028 2020

  6. [6]

    Enumerating the irreducible closed sets of an acyclic implicational base of bounded degree

    Oscar Defrain, Arthur Ohana, and Simon Vilmin. Enumerating the irreducible closed sets of an acyclic implicational base of bounded degree. In36th International Symposium on Algorithms and Computation (ISAAC 2025), volume 359 ofLeibniz International Proceedings in Informatics, pages 24:1–24:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi: ...

    work page doi:10.4230/lipics.isaac.2025.24 2025

  7. [7]

    Keys, antikeys and prime attributes.Annales Universitatis Scientiarum Budapestinensis, Sectio Computatorica, 8:35–52, 1987

    János Demetrovics and Vu Duc Thi. Keys, antikeys and prime attributes.Annales Universitatis Scientiarum Budapestinensis, Sectio Computatorica, 8:35–52, 1987

    work page 1987

  8. [8]

    Emre Telatar, Thomas J

    Changyan Di, David Proietti, I. Emre Telatar, Thomas J. Richardson, and Rüdiger L. Urbanke. Finite-length analysis of low-density parity-check codes on the binary erasure channel.IEEE Transactions on Information Theory, 48(6):1570–1579, 2002. doi: 10.1109/TIT.2002.1003839

    arXiv 2002

Show all 28 references
  1. [9]

    Identifying the minimal transversals of a hypergraph and related problems.SIAM Journal on Computing, 24(6):1278–1304, 1995

    Thomas Eiter and Georg Gottlob. Identifying the minimal transversals of a hypergraph and related problems.SIAM Journal on Computing, 24(6):1278–1304, 1995. doi: 10.1137/ S0097539793250299

    1995

  2. [10]

    Computational aspects of monotone dualization: A brief survey.Discrete Applied Mathematics, 156(11):2035–2049, 2008

    Thomas Eiter, Kazuhisa Makino, and Georg Gottlob. Computational aspects of monotone dualization: A brief survey.Discrete Applied Mathematics, 156(11):2035–2049, 2008. doi: 10.1016/j.dam.2007.04.017

    2008 doi

  3. [11]

    Stopping set elimination by parity-check matrix extension via integer linear programming.IEEE Transactions on Communications, 63(5): 1533–1540, 2015

    Hossein Falsafain and Sayyed Rasoul Mousavi. Stopping set elimination by parity-check matrix extension via integer linear programming.IEEE Transactions on Communications, 63(5): 1533–1540, 2015. doi: 10.1109/TCOMM.2015.2418263

    2015

  4. [12]

    Fredman and Leonid Khachiyan

    Michael L. Fredman and Leonid Khachiyan. On the complexity of dualization of monotone disjunctive normal forms.Journal of Algorithms, 21(3):618–628, 1996. doi: 10.1006/jagm.1996. 0062

    1996 doi

  5. [13]

    Garey, David S

    Michael R. Garey, David S. Johnson, and Robert Endre Tarjan. The planar hamiltonian circuit problem is NP-complete.SIAM Journal on Computing, 5(4):704–714, 1976. doi: 10.1137/ 0205049

    1976

  6. [14]

    Junsheng Han and Paul H. Siegel. Improved upper bounds on stopping redundancy.IEEE Transactions on Information Theory, 53(1):90–104, 2007. doi: 10.1109/TIT.2006.887513

    2007

  7. [15]

    Kavvadias, Martha Sideri, and Elias C

    Dimitris J. Kavvadias, Martha Sideri, and Elias C. Stavropoulos. Generating all maximal models of a Boolean expression.Information Processing Letters, 74(3–4):157–162, 2000. doi: 10.1016/S0020-0190(00)00023-5

    doi

  8. [16]

    Translating between Horn representations and their characteristic models.Journal of Artificial Intelligence Research, 3:349–372, 1995

    Roni Khardon. Translating between Horn representations and their characteristic models.Journal of Artificial Intelligence Research, 3:349–372, 1995. doi: 10.1613/jair.183

    1995 doi

  9. [17]

    Murali Krishnan and Priti Shankar

    K. Murali Krishnan and Priti Shankar. Computing the stopping distance of a tanner graph is NP-hard.IEEE Transactions on Information Theory, 53(6):2278–2280, 2007. doi: 10.1109/TIT. 2007.896864

    2007

  10. [18]

    On the strength of uniqueness quantification in primitive positive formulas

    Victor Lagerkvist and Gustav Nordh. On the strength of uniqueness quantification in primitive positive formulas. In44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), volume 138 ofLeibniz International Proceedings in Informatics (LIPIcs), ...

    2019 doi

  11. [19]

    Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements.Theoretical Computer Science, 969:114030, 2023

    Lhouari Nourine and Simon Vilmin. Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements.Theoretical Computer Science, 969:114030, 2023. doi: 10.1016/j.tcs.2023.114030. 29

    2023

  12. [20]

    Cambridge University Press, Cambridge, 2008

    Tom Richardson and Rüdiger Urbanke.Modern Coding Theory. Cambridge University Press, Cambridge, 2008

    2008

  13. [21]

    An efficient algorithm to find all small-size stopping sets of low-density parity-check matrices.IEEE Transactions on Information Theory, 55(9):4167–4178,

    Eirik Rosnes and Øyvind Ytrehus. An efficient algorithm to find all small-size stopping sets of low-density parity-check matrices.IEEE Transactions on Information Theory, 55(9):4167–4178,

  14. [22]

    an efficient algorithm to find all small-size stopping sets of low-density parity-check matrices

    Eirik Rosnes, Øyvind Ytrehus, Marcel A. Ambroze, and Martin Tomlinson. Addendum to “an efficient algorithm to find all small-size stopping sets of low-density parity-check matrices”.IEEE Transactions on Information Theory, 58(1):164–171, 2012. doi: 10.1109/TIT.2011.2171531

    2012

  15. [23]

    Thecomplexityofsatisfiabilityproblems

    ThomasJ.Schaefer. Thecomplexityofsatisfiabilityproblems. InProceedingsoftheTenthAnnual ACM Symposium on Theory of Computing, pages 216–226. ACM, 1978. doi: 10.1145/800133. 804350

    1978 doi

  16. [24]

    On the stopping distance and the stopping redundancy of codes.IEEE Transactions on Information Theory, 52(3):922–932, 2006

    Moshe Schwartz and Alexander Vardy. On the stopping distance and the stopping redundancy of codes.IEEE Transactions on Information Theory, 52(3):922–932, 2006. doi: 10.1109/TIT.2005. 864441

    2006 doi

  17. [25]

    Investigationonantikeysandminimalkeysofrelationschemesbyhypergraphs

    NguyenHoangSon. Investigationonantikeysandminimalkeysofrelationschemesbyhypergraphs. Annales Universitatis Scientiarum Budapestinensis, Sectio Computatorica, 26:79–89, 2006

    2006

  18. [26]

    Minimal keys and antikeys.Acta Cybernetica, 7(4):361–371, 1986

    Vu Duc Thi. Minimal keys and antikeys.Acta Cybernetica, 7(4):361–371, 1986

    1986

  19. [27]

    Kulkarni, and H

    Chih-Chun Wang, Sanjeev R. Kulkarni, and H. Vincent Poor. Finding all small error-prone substructures in LDPC codes.IEEE Transactions on Information Theory, 55(5):1976–1999, 2009. doi: 10.1109/TIT.2009.2015993. 30

    1976

  20. [2009]

    doi: 10.1109/TIT.2009.2025573

    2009

Pith tools

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