Pith. sign in

REVIEW 2 major objections 6 minor 39 references

Optimal antimatroid sorting

T0 review · 2 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Sorting with a hint is optimal when the allowed orders form an antimatroid.

desk verdict Genuinely new and largely sound: antimatroid generalization of topological heapsort with optimal comparisons; chordal CDS gap needs work. read the letter →

arxiv 2507.13994 v1 pith:LXXFO5IZ submitted 2025-07-18 cs.DS

Benjamin Aram Berendsohn This is my paper
classification cs.DS
keywords antimatroidrestrictedsortingtopologicalheapsortworking-setheapmonotoneprecedencesystemsperfecteliminationorderingsinformation-theoreticboundcandidatedatastructure
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 studies comparison-based sorting when, instead of an arbitrary set of elements, the input comes with a hint: a set $T$ of possible total orders, and the true order is guaranteed to lie in $T$. The information-theoretic lower bound says at least $\log|T|$ comparisons are needed. The paper claims that if $T$ is the set of permutations of an antimatroid—a structure generalizing partial orders, definable by monotone precedence rules—then this bound is tight: a generalization of topological heapsort sorts using $O(\log|T|)$ comparisons and running time $O(t_{\text{total}}(C)+\log|T|)$, where $t_{\text{total}}(C)$ is the total cost of a candidate data structure that reports which elements may come next. This matters because it turns "sorting with hints" into a data-structure problem for a broad class of constraint sets, and it yields optimal algorithms for sorting under precedence formulas, elementary ranking conditions from Optimality Theory, vertex-search orders of rooted graphs, and perfect elimination orders of chordal graphs.

What carries the argument

The key objects are monotone precedence systems (MPSs), which characterize antimatroids: each element $x$ has a monotone boolean function $p_x$ on subsets of the other elements, and a word is allowed if each letter $x$ occurs only once its predecessors satisfy $p_x$. The candidate data structure $C$ reports, after a sequence of removals, which elements newly became available; its total time $t_{\text{total}}(C)$ is the tuning parameter. The argument's engine is the layer sequence: layers are computed by repeatedly taking currently available elements, and the theorem that $|P(A)|\ge 2^{n-k}$ for $k$ layers, which yields the bottleneck subsequence. The merge step uses exponential search (repeated doubling) to locate each element of one sorted sequence within the other, and the proof that the comparisons are optimal counts the insertion positions as distinct permutations in $P(A)$.

What would settle it

Construct an antimatroid with an efficient-looking candidate data structure whose total update time over a valid sequence is actually superlinear, and the corresponding optimal running-time claim in Theorem 9 fails. Concretely, the clique tree implementation in Appendix C should be stress-tested on chordal graphs: if any sequence of simplicial-vertex deletions forces more than $O(m+n)$ total work, the perfect-elimination-ordering application collapses. Conversely, if the rotation-language construction of Section 6.1—shown to be a greedoid but not an antimatroid—could be shown to satisfy the antimatroid axioms, the central claim would be false, since that language has $2^{n-1}$ permutations yet topological heapsort needs $\Theta(n \log n)$ comparisons there.

Watch

Extended reading notes

Core claim

The central claim is Theorem 9: given a candidate data structure $C$ for an antimatroid $A$ on alphabet $\Sigma$ and an oracle for a total order $\pi\in P(A)$, the set $\Sigma$ can be sorted in $O(t_{\text{total}}(C)+\log|P(A)|)$ time using $O(\log|P(A)|)$ comparisons. The proof has three stages. First, for any monotone precedence system, the layer sequence partitions $\Sigma$, and the number of layers bounds $|P(A)|$ from below; the few "bottleneck" elements (unique in their layer) appear in the same order in every allowed permutation, giving a long pre-sorted subsequence $\beta$. Second, the remaining elements are sorted by topological heapsort on the trace antimatroid, with a candidate data structure that simulates the original one. Third, the two sorted sequences are merged with exponential search; the antimatroid axioms guarantee that whenever the next element of one sequence is not available, the other must be smaller, so no comparisons are wasted. The comparison count matches the information-theoretic bound because the possible insertion positions of the merged elements form at least $\log|P(A)|$ distinguishable permutations.

Load-bearing premise

Topological heapsort is optimal only if a candidate data structure exists whose total work for one initialization plus a valid sequence of updates is linear in the input size; the implementations for precedence formulas, ERCs, and vertex search are given, but the chordal-graph case relies on a clique tree data structure whose correctness is only summarized, and the working-set heap is assumed as a black box.

Editorial extensions

If this is right

  • If Theorem 9 holds, the information-theoretic lower bound is tight for every antimatroid: sorting under antimatroid constraints uses $O(\log|P(A)|)$ comparisons.
  • Optimal algorithms follow immediately for each antimatroid representation with an efficient candidate data structure: monotone precedence formulas, ERC sets (linguistic Optimality Theory rankings), vertex search orders of connected rooted graphs, and perfect elimination orders of chordal graphs.
  • For chordal graphs, the perfect-elimination-ordering sorting problem is solved with $O(m+n+\log|P(A)|)$ time and $O(\log|P(A)|)$ comparisons, since $|P(A)|\ge 2^{n-1}$, so even the unmodified algorithm is comparison-optimal.
  • Dijkstra's algorithm with a working-set heap is universally optimal for the distance-ordering problem, because the distance orderings of a graph are exactly the permutations of its vertex search antimatroid.

Reading between the lines

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

  • The reduction to candidate data structures suggests that for any constraint family whose permutation sets form an antimatroid, the search for an optimal sorting algorithm reduces to designing a linear-total-time availability data structure; this reframes many restricted sorting problems as data-structure problems.
  • The bottleneck/layer decomposition gives a structural handle on antimatroids—the number of non-bottleneck elements is at most $2\log|P(A)|$—that might transfer to other algorithmic problems on antimatroids and greedoids, such as enumeration or random generation of permutations.
  • The exponential-search merge in Section 5.3 resembles multiway merging with lookahead; one could test whether a similar analysis applies to other restricted sorting settings where the available-set structure is monotone but not order-insensitive.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 6 minor

Summary. The paper studies the restricted sorting problem where the set of possible total orders is the set of permutations of an antimatroid. It proves that a direct generalization of topological heapsort has optimal queue time O(n + log|T|) for antimatroids (Theorem 5), and that a three-phase algorithm—bottleneck sequence, sorting the remainder, and merging—achieves optimal O(log|T|) comparisons given an efficient candidate data structure (Theorem 9). Efficient candidate data structures are claimed for precedence formulas, ERC sets, vertex search antimatroids, and chordal graph perfect elimination orders. The paper also presents negative results showing that greedoids, non-monotone precedence systems, and order-sensitive monotone precedence systems do not admit the same optimality guarantees.

Significance. The main conceptual contributions are significant: Theorem 5 extends the working-set heap analysis of topological heapsort from partial orders to the full class of antimatroids via an auxiliary partial order, and Theorem 9, if correct, shows that the information-theoretic bound is tight for antimatroid sorting. The candidate-data-structure framework cleanly separates the algorithmic core from representation-specific issues, and the paper is explicit about its use of the working-set heap as a black box. The negative results in Section 6 are useful boundary mapping. However, two load-bearing issues—the chordal graph candidate data structure and the comparison bound for the merge step—need to be resolved before the advertised consequences are established.

major comments (2)
  1. [Section 4.4 / Appendix C] The clique-tree candidate data structure is not linear time as described. In the contraction step, merging a clique K(x) into a neighbor K(y) requires reattaching all other incident edges of x. On the chordal graph with vertices a,b,c1,...,ck and edges {a,b} ∪ {a,ci}, the maximal cliques are {a,b} and {a,ci}, and the natural clique tree is a star centered at x0={a,b}. Under the valid PEO b,c1,...,ck, deleting b leaves K(x0)={a}, which is contained in every leaf; contracting x0 into x1 requires rewiring the other k−1 leaves to x1, costing Θ(k). The same happens after each ci is deleted, giving Θ(k^2) total time on a graph with O(k) edges. This contradicts the assertion in Appendix C that "all necessary updates can be done in |K(x)| time" and the claimed O(m+n) total. Consequently, the claim in Section 4.4 that perfect-elimination-order sorting for chordal graphs is solved in optimal time is unsupported.
  2. [Section 5.4 / Theorem 18] The proof of Theorem 9 does not establish the claimed O(log|P(A)|) comparison bound. Theorem 18 bounds the merge step by O(|Δ| + log|R|) comparisons, but in the application of Theorem 9 we have Δ equal to the bottleneck sequence, and |Δ| can be as large as n even when log|P(A)| = 0 (e.g., a single chain, where every element is a bottleneck and Γ is empty). The text in Section 5.4 instead uses a comparison bound of O(log|P(A)| + |Γ| + log|R|) without proof, which does not follow from Theorem 18. The needed statement is a sharper analysis of Algorithm 2 showing O(|Γ| + log|R|) comparisons: if-branches with i*_j > i_j consume Γ-elements and are therefore at most |Γ| in number, while zero-length searches contribute no comparisons. Until such an analysis is provided, Theorem 9 is not proven. Relatedly, Equation (1) and Lemma 20 use log(i*_j − i_j), which is undefined when i*_j = i_j; the cases should be separated or i*_j − i_j + 1 used.
minor comments (6)
  1. [Section 5.2] The justification for |P(A|Γ)| ≤ |P(A)| says "the restriction operation surjectively maps P(A|Γ) to P(A);" the direction is reversed. The correct statement is that restriction maps P(A) onto P(A|Γ), which still implies the inequality.
  2. [Section 6.3] The claim that "all elements are available at the start" for the OSMPS example is incorrect: in the set T, only elements of the first block can appear first. The subsequent conclusion that every antimatroid containing T contains every permutation therefore does not follow as written; the non-antimatroid property needs a different justification.
  3. [Appendix C] In the clique tree definition, "the path between x1 and x2" should be "the path between x1 and x3."
  4. [Section 4] Typo: "an animatroid" should be "an antimatroid."
  5. [Section 4.1] "An CDSC" should be "A CDS C" or "The CDS C."
  6. [Algorithm 2] The behavior of exp-search on an empty sequence (i > k) should be stated explicitly; the current definition leaves the case ambiguous.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the antimatroid-sorting analysis reduces to an external partial-order lemma and independent counting arguments, not to its own inputs.

full rationale

The paper's central derivation chain is self-contained. Theorem 5 bounds the queue time of Algorithm 1 by constructing an auxiliary partial order P from the algorithm's own transcript; the argument that P(SP) is a subset of P(S) and that the two transcripts coincide is an explicit proof, not an assumption equivalent to the conclusion. The only imported running-time fact is Lemma 4, taken from Haeupler et al. [18] as an external prior result; it is not self-citational (the present author is not among [18]'s authors) and it is used as a black box with stated hypotheses. The comparison-optimality proof (Theorem 9) reduces to information-theoretic counting (Lemma 12, Corollary 14), bounded-subset sorting (Lemma 17), and a merge bound (Lemma 20); none of these reintroduce the target bound by construction, and no parameter is fitted to the output it claims to predict. The chordal-graph application (Section 4.4, Appendix C) is the least supported part: the statement 'All necessary updates can be done in |K(x)| time' is asserted rather than fully proved, and a reviewer could worry about superlinear contraction cost on a star of cliques; that is a correctness or rigor gap in one application, not an equivalence between an input and a predicted quantity. The score is therefore 0.

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

The central claim rests on standard antimatroid theory and on the existence of a working-set heap from prior work. No numerical parameters are fitted; no new physical entities are postulated.

assumptions (5)
  • standard math A full antimatroid is exactly the set of prefixes of permutations of a monotone precedence system.
    Proved in Appendix A (Proposition 24); used to define Algorithm 1 and the layer sequence.
  • domain assumption There exists a priority queue with the weak working-set property, giving O(1+log w(x)) extract-min time.
    Assumed from Haeupler et al. [18]; Lemma 4 and the queue time analysis depend on it.
  • standard math The trace A|Gamma of an antimatroid is itself an antimatroid.
    Cited from Bjorner and Ziegler [2]; used in Section 5.2 to sort subsets.
  • domain assumption Every full permutation of a trace extends to a full permutation of the whole antimatroid, so |P(A|Gamma)| <= |P(A)|.
    Stated in Section 5.2 with a directionally mangled justification ("surjectively maps P(A|Gamma) to P(A)"); the inequality is needed for the comparison budget.
  • standard math For chordal graphs, a clique tree can be built in O(m+n) time and supports the decremental simplicial vertex updates described.
    Used in Section 4.4 and Appendix C; relies on standard clique tree properties and [3,8].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal antimatroid sorting." pith.science (2026). https://pith.science/paper/LXXFO5IZ

@misc{pith2026250713994,
  author       = {Pith},
  title        = {Pith review of: Optimal antimatroid sorting},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LXXFO5IZ}},
  note         = {Machine review of arXiv:2507.13994}
}
abstract

The classical comparison-based sorting problem asks us to find the underlying total order of a given set of elements, where we can only access the elements via comparisons. In this paper, we study a restricted version, where, as a hint, a set $T$ of possible total orders is given, usually in some compressed form. Recently, an algorithm called topological heapsort with optimal running time was found for the case where $T$ is the set of topological orderings of a given directed acyclic graph, or, equivalently, $T$ is the set of linear extensions of a given partial order [Haeupler et al. 2024]. We show that a simple generalization of topological heapsort is applicable to a much broader class of restricted sorting problems, where $T$ corresponds to a given antimatroid. As a consequence, we obtain optimal algorithms for the following restricted sorting problems, where the allowed total orders are restricted by: a given set of monotone precedence formulas; the perfect elimination orders of a given chordal graph; or the possible vertex search orders of a given connected rooted graph.

Figures

Figures reproduced from arXiv: 2507.13994 by the authors.

Figure 2
Figure 2. Visualization of permutations in the set U. The permutation π is obtained by inserting each dj in the rightmost possible position. that any µ ′ j may be empty). Finally, let U = {µ ′ 0µ1µ ′ 1µ2µ ′ 2 . . . µℓµ ′ ℓ | µj ∈ Mj for j ∈ ℓ}. See [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

39 extracted references · 24 canonical work pages

  1. [1]

    An almost optimal algorithm for unbounded searching

    Jon Louis Bentley and Andrew Chi-Chih Yao. An almost optimal algorithm for unbounded searching. Information Processing Letters , 5(3):82–87, August 1976. https://doi.org/10.1016/0020-0190(76)90071-5 doi:10.1016/0020-0190(76)90071-5

    work page doi:10.1016/0020-0190(76)90071-5 1976

  2. [2]

    Anders Björner and Günter M. Ziegler. Introduction to Greedoids . In Neil White, editor, Matroid Applications , volume 40 of Encyclopedia of Mathematics and Its Applications . Cambridge University Press, 1992. https://doi.org/10.1017/CBO9780511662041.009 doi:10.1017/CBO9780511662041.009

    work page doi:10.1017/cbo9780511662041.009 1992

  3. [3]

    Jean R. S. Blair and Barry Peyton. An introduction to chordal graphs and clique trees. In Alan George, John R. Gilbert, and Joseph W.R. Liu, editors, Graph Theory and Sparse Matrix Computation , pages 1--29. Springer New York, 1993. https://doi.org/10.1007/978-1-4613-8369-7_1 doi:10.1007/978-1-4613-8369-7_1

    work page doi:10.1007/978-1-4613-8369-7_1 1993

  4. [4]

    G. R. Brightwell, S. Felsner, and W. T. Trotter. Balancing pairs and the cross product conjecture. Order , 12(4):327–349, 1995. https://doi.org/10.1007/bf01110378 doi:10.1007/bf01110378

    doi:10.1007/bf01110378 1995

  5. [5]

    Brightwell

    Graham R. Brightwell. Balanced pairs in partial orders. Discret. Math. , 201(1-3):25--52, 1999. https://doi.org/10.1016/S0012-365X(98)00311-2 doi:10.1016/S0012-365X(98)00311-2

    doi:10.1016/s0012-365x(98)00311-2 1999

  6. [6]

    Brown and Robert Endre Tarjan

    Mark R. Brown and Robert Endre Tarjan. A fast merging algorithm. J. ACM , 26(2):211--226, 1979. https://doi.org/10.1145/322123.322127 doi:10.1145/322123.322127

    work page arXiv 1979

  7. [7]

    e l Joret, Rapha \

    Jean Cardinal, Samuel Fiorini, Gwena \" e l Joret, Rapha \" e l M. Jungers, and J. Ian Munro. Sorting under partial information (without the ellipsoid algorithm). In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 , pages 359--368. ACM , 2010. https://doi.or...

    arXiv 2010

  8. [8]

    Chandran, L

    L.S. Chandran, L. Ibarra, F. Ruskey, and J. Sawada. Generating and characterizing the perfect elimination orderings of a chordal graph. Theoretical Computer Science , 307(2):303--317, 2003. Random Generation of Combinatorial Objects and Bijective Combinatorics. https://doi.org/10.1016/S0304-3975(03)00221-4 doi:10.1016/S0304-3975(03)00221-4

    work page doi:10.1016/s0304-3975(03)00221-4 2003

Show all 39 references
  1. [9]

    A circuit set characterization of antimatroids

    Brenda L Dietrich. A circuit set characterization of antimatroids. Journal of Combinatorial Theory, Series B , 43(3):314--321, 1987. https://doi.org/10.1016/0095-8956(87)90007-4 doi:10.1016/0095-8956(87)90007-4

    1987 doi

  2. [10]

    R. P. Dilworth. Lattices with unique irreducible decompositions. Annals of Mathematics , 41(4):771--777, 1940. https://doi.org/10.1007/978-1-4899-3558-8_10 doi:10.1007/978-1-4899-3558-8_10

    1940 doi

  3. [11]

    Antimatroids and balanced pairs

    David Eppstein. Antimatroids and balanced pairs. Order , 31(1):81--99, 2014. https://doi.org/10.1007/S11083-013-9289-1 doi:10.1007/S11083-013-9289-1

    2014 doi

  4. [12]

    Michael L. Fredman. How good is the information theory bound in sorting? Theoretical Computer Science , 1(4):355--361, 1976. https://doi.org/10.1016/0304-3975(76)90078-5 doi:10.1016/0304-3975(76)90078-5

    1976 doi

  5. [13]

    The pairing heap: A new form of self-adjusting heap

    Michael L Fredman, Robert Sedgewick, Daniel D Sleator, and Robert E Tarjan. The pairing heap: A new form of self-adjusting heap . Algorithmica , 1(1-4):111--129, 1986

    1986

  6. [14]

    Fredman and Dan E

    Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences , 47(3):424--436, December 1993. https://doi.org/10.1016/0022-0000(93)90040-4 doi:10.1016/0022-0000(93)90040-4

    1993 doi

  7. [15]

    Nebel, Benjamin Smith, and Sebastian Wild

    William Cawley Gelling, Markus E. Nebel, Benjamin Smith, and Sebastian Wild. Multiway powersort. In Gonzalo Navarro and Julian Shun, editors, Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2023, Florence, Italy, January 22-23, 2023 , pages 190--2...

    2023 doi

  8. [17]

    Fast and simple sorting using partial information, 2024

    Bernhard Haeupler, Richard Hladík, John Iacono, Vaclav Rozhon, Robert Tarjan, and Jakub Tětek. Fast and simple sorting using partial information, 2024. https://arxiv.org/abs/2404.04552v1 arXiv:2404.04552v1

    2024 arXiv

  9. [18]

    Tarjan, and Jakub Tětek

    Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhoň, Robert E. Tarjan, and Jakub Tětek. Fast and simple sorting using partial information. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3953--3973, 2025. https://doi.org/10....

    2025 doi

  10. [19]

    D eterministic sorting in O(n n) time and linear space

    Yijie Han. D eterministic sorting in O(n n) time and linear space . Journal of Algorithms , 50(1):96--105, January 2004. https://doi.org/10.1016/j.jalgor.2003.09.001 doi:10.1016/j.jalgor.2003.09.001

    2004 doi

  11. [20]

    Yijie Han and M. Thorup. Integer sorting in O( n n ) expected time and linear space . In Proceedings of the 43 rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’02) , pages 135--144. IEEE Comput. Soc, 2002. https://doi.org/10.1109/SFCS.2002.1181890 doi:10.1109/...

    2002 arXiv

  12. [21]

    Hwang and Shen Lin

    Frank K. Hwang and Shen Lin. A simple algorithm for merging two disjoint linearly-ordered sets. SIAM J. Comput. , 1(1):31--39, 1972. https://doi.org/10.1137/0201004 doi:10.1137/0201004

    1972 doi

  13. [22]

    Arthur B. Kahn. Topological sorting of large networks. Commun. ACM , 5(11):558--562, 1962. https://doi.org/10.1145/368996.369025 doi:10.1145/368996.369025

    1962

  14. [23]

    Entropy and sorting

    Jeff Kahn and Jeong Han Kim. Entropy and sorting. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC ’92 , STOC ’92, page 178–187. ACM Press, 1992. https://doi.org/10.1145/129712.129731 doi:10.1145/129712.129731

    1992

  15. [24]

    Kirkpatrick and Raimund Seidel

    David G. Kirkpatrick and Raimund Seidel. The ultimate planar convex hull algorithm? SIAM J. Comput. , 15(1):287--299, 1986. https://doi.org/10.1137/0215021 doi:10.1137/0215021

    1986 doi

  16. [25]

    S. S. Kislitsyn. A finite partially ordered set and its corresponding set of permutations. Mathematical Notes of the Academy of Sciences of the USSR , 4(5):798–801, November 1968. https://doi.org/10.1007/bf01111312 doi:10.1007/bf01111312

    1968 doi

  17. [26]

    Finding and counting small induced subgraphs efficiently

    Ton Kloks, Dieter Kratsch, and Haiko M \" u ller. Finding and counting small induced subgraphs efficiently. Inf. Process. Lett. , 74(3-4):115--121, 2000. https://doi.org/10.1016/S0020-0190(00)00047-8 doi:10.1016/S0020-0190(00)00047-8

    doi

  18. [27]

    Donald E. Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms . Addison-Wesley, 1968

    1968

  19. [28]

    Donald E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching . Addison-Wesley, 1973

    1973

  20. [29]

    Korte and L

    B. Korte and L. Lov \'a sz. Mathematical structures underlying greedy algorithms. In Ferenc G \'e cseg, editor, Fundamentals of Computation Theory , pages 205--209, Berlin, Heidelberg, 1981. Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-10854-8_22 doi:10.1007/3-540...

    1981 doi

  21. [30]

    Greedoids - a structural framework for the greedy algorithm

    Bernhard Korte and László Lovász. Greedoids - a structural framework for the greedy algorithm. In William R. Pulleyblank, editor, Progress in Combinatorial Optimization , pages 221--243. Elsevier, 1984. https://doi.org/10.1016/b978-0-12-566780-7.50019-2 doi:10.1016/b978-0-12-5...

    1984 doi

  22. [31]

    Greedoids

    Bernhard Korte, Rainer Schrader, and László Lovász. Greedoids . Springer Berlin Heidelberg, 1991. https://doi.org/10.1007/978-3-642-58191-5 doi:10.1007/978-3-642-58191-5

    1991 doi

  23. [32]

    Soulignac, and Jayme Luiz Szwarcfiter

    Min Chih Lin, Francisco J. Soulignac, and Jayme Luiz Szwarcfiter. Arboricity, h-index, and dynamic algorithms. Theor. Comput. Sci. , 426:75--90, 2012. https://doi.org/10.1016/J.TCS.2011.12.006 doi:10.1016/J.TCS.2011.12.006

    2012 doi

  24. [33]

    The information-theoretic bound is good for merging

    Nathan Linial. The information-theoretic bound is good for merging. SIAM J. Comput. , 13(4):795--801, 1984. https://doi.org/10.1137/0213049 doi:10.1137/0213049

    1984 doi

  25. [34]

    OT grammars, beyond partial orders: ERC sets and antimatroids

    Nazarré Merchant and Jason Riggle. OT grammars, beyond partial orders: ERC sets and antimatroids . Natural Language &amp; Linguistic Theory , 34(1):241–269, August 2015. https://doi.org/10.1007/s11049-015-9297-5 doi:10.1007/s11049-015-9297-5

    2015 doi

  26. [36]

    Optimality theory: Constraint interaction in generative grammar

    Alan Prince and Paul Smolensky. Optimality theory: Constraint interaction in generative grammar. In John J. McCarthy, editor, Optimality Theory in Phonology , chapter 1, pages 1--71. John Wiley & Sons, Ltd, 2004. https://doi.org/10.1002/9780470756171.ch1 doi:10.1002/9780470756171.ch1

    2004 doi

  27. [37]

    Neil Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width . J. Algorithms , 7(3):309--322, 1986. https://doi.org/10.1016/0196-6774(86)90023-4 doi:10.1016/0196-6774(86)90023-4

    1986 doi

  28. [38]

    Simple universally optimal dijkstra, 2025

    Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann. Simple universally optimal dijkstra, 2025. URL: https://arxiv.org/abs/2504.17327, https://arxiv.org/abs/2504.17327 arXiv:2504.17327

    2025

  29. [39]

    Simpler optimal sorting from a directed acyclic graph

    Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann. Simpler optimal sorting from a directed acyclic graph. In 2025 Symposium on Simplicity in Algorithms (SOSA) , pages 350--355. Society for Industrial and Applied Mathematics, January 2025. https://doi.org/10.1137/1.978161...

    2025 doi

  30. [40]

    Tight bounds for sorting under partial information

    Ivor van der Hoog and Daniel Rutschmann. Tight bounds for sorting under partial information. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024 , pages 2243--2252. IEEE , 2024. https://doi.org/10.1109/FOCS61266.20...

    2024

  31. [41]

    J. W. J. Williams. Algorithm 232: Heapsort. Communications of the ACM , 7(6):347--348, 1964

    1964

Pith tools

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