{"id":"dae315d8-cc7a-43c4-8c8e-e721d850d2cf","arxiv_id":"2507.13994","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Topological heapsort generalizes to antimatroids, yielding optimal running time and O(log|P|) comparisons for antimatroid-constrained sorting.","lead":"This paper proves that a generalized topological heapsort solves restricted sorting problems for antimatroids in optimal time and with an optimal number of comparisons. The result covers partial orders, monotone precedence formulas, chordal graph elimination orders, and vertex search orders.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Appendix C chordal CDS may be superlinear: clique-tree contractions on a star of cliques cost Θ(k^2) on a graph with O(k) edges, so the advertised optimal PEO sorting is not established.","rationale":"The reader identified the chordal-graph clique-tree CDS as the weakest assumption; this stress-test agrees and makes the concern concrete. The star-of-cliques example shows the per-contraction cost in Appendix C is proportional to the current tree degree, not to |K(x)|, so the claimed O(m+n) total is not justified by the text. This does not invalidate Theorem 5 or the general comparison-optimal construction: the auxiliary partial order proof and the bottleneck/merge argument appear sound, and the precedence-formula and ERC CDSs are more straightforward. The paper should either replace Appendix C with a correct linear-time simplicial-vertex-deletion data structure (or cite and adapt one precisely), or remove the chordal PEO application from the abstract. Since the flaw is localized and likely fixable, conditional acceptance remains the right verdict; the reader's CONDITIONAL verdict is unchanged.","tokens_in":23829,"tokens_out":35787,"duration_ms":460388,"concrete_test":"Implement Appendix C's CDS exactly, with explicit contractions of non-maximal clique-tree nodes, and run it on the star chordal graph with vertices {a,b,c1,...,ck} and edges {a,b}∪{a,ci} under the PEO b,c1,c2,...,ck. Count total clique-tree edge updates (or total CPU operations). If the count is Θ(k^2) while the graph has O(k) edges, the O(m+n) total-time claim fails; if the count is O(k), my analysis is wrong. Analytically, the series k+(k-1)+...+1 is the expected count if each contraction processes the current degree.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 9's applications require an efficient CDS with ttotal(C)=O(input size). For chordal graphs, Section 4.4/Appendix C claims a clique-tree CDS with total O(m+n), asserting that 'all necessary updates can be done in |K(x)| time.' That bound is false for the described contraction procedure. Take the chordal graph with vertices {a,b,c1,...,ck} and edges {a,b}∪{a,ci}. Its maximal cliques are {a,b} and {a,ci}; the natural clique tree is a star centered at x0={a,b} with leaves xi={a,ci}. The valid PEO b,c1,c2,...,ck triggers: delete b from x0, leaving K(x0)={a}, which is contained in every leaf; contracting x0 into x1 requires rewiring the other k-1 leaves to x1, costing Θ(k) although |K(x0)|=1. Then delete c1: K(x1)={a} is contained in all remaining leaves, so x1 contracts into x2, again costing Θ(k-1). Repeating gives Θ(k^2) clique-tree edge updates for a graph with O(k) edges and O(k) vertices. Thus the CDS is not linear as written, and the advertised optimal algorithm for perfect-elimination-order sorting is unsupported. The general Theorem 9 and other CDS implementations (precedence formulas, ERCs) appear unaffected; this is an application-level, but advertised, gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24095,"tokens_out":32461,"duration_ms":353426,"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":[{"comment":"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.","section":"Section 4.4 / Appendix C"},{"comment":"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.","section":"Section 5.4 / Theorem 18"}],"minor_comments":[{"comment":"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.","section":"Section 5.2"},{"comment":"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.","section":"Section 6.3"},{"comment":"In the clique tree definition, \"the path between x1 and x2\" should be \"the path between x1 and x3.\"","section":"Appendix C"},{"comment":"Typo: \"an animatroid\" should be \"an antimatroid.\"","section":"Section 4"},{"comment":"\"An CDSC\" should be \"A CDS C\" or \"The CDS C.\"","section":"Section 4.1"},{"comment":"The behavior of exp-search on an empty sequence (i > k) should be stated explicitly; the current definition leaves the case ambiguous.","section":"Algorithm 2"}],"recommendation":"major_revision","confidential_remarks":"The paper has a strong and elegant core (Theorem 5 and the CDS framework), and Theorem 9 is likely fixable with a revised merge analysis. The chordal graph application, however, needs a genuinely linear-time implementation or should be withdrawn. The Section 6.3 non-antimatroid argument also needs correction. I would recommend major revision rather than rejection because the central conceptual contributions are defensible and the issues, while load-bearing for advertised claims, appear addressable within the scope of the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result is real. Theorem 5's transcript-to-partial-order argument and Theorem 9's bottleneck/merging scheme extend topological heapsort from DAGs to all antimatroids, and the O(log |P(A)|) comparison bound matches the information-theoretic lower bound. The precedence-formula and ERC implementations are straightforward and correct, and the paper is honest about where the method fails (greedoids, order-sensitive systems).\n\nThe soft spot is Section 4.4 and Appendix C. The clique-tree CDS for chordal graphs is not linear as written. The star-of-cliques example checks out: contracting the center into a leaf rewires every remaining leaf, and repeating gives Θ(k^2) work on a graph with O(k) edges. So the advertised optimal algorithm for PEO sorting is not established. This is an application-level gap, not a flaw in the meta-theorem—Theorem 9's other instantiations stand—but it is a gap in a headline application. A second, minor issue: Section 5.2 says the restriction operation surjectively maps P(A|Γ) to P(A). It is the reverse: restriction maps P(A) onto P(A|Γ). The inequality |P(A|Γ)| ≤ |P(A)| is true, so the argument survives, but the sentence is backwards.\n\nThe central proof of Theorem 5 appears correct on inspection. I found no circularity, no fitted parameters, and no suspicious citation pattern; the Haeupler et al. working-set heap is legitimate black-box prior art. The limitation discussion is refreshingly candid.\n\nThis deserves a serious referee. I would send it out. The referee should push for a corrected or carefully reworked chordal CDS, and for a fix to the surjectivity sentence. The central theorem is likely right and the paper extends an important line of work; with the chordal details resolved it would be a strong theory result. For a reading group, the transcript trick is worth discussing, but the chordal section should be read with suspicion until revised.","headline":"Genuinely new and largely sound: antimatroid generalization of topological heapsort with optimal comparisons; chordal CDS gap needs work.","tokens_in":24629,"tokens_out":4122,"would_cite":true,"duration_ms":49113,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Sorting with a hint is optimal when the allowed orders form an antimatroid.","keywords":["antimatroid","restricted sorting","topological heapsort","working-set heap","monotone precedence systems","perfect elimination orderings","information-theoretic bound","candidate data structure"],"falsifier":"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.","tokens_in":23612,"feed_emoji":"🔀","tokens_out":6027,"duration_ms":61290,"temperature":0.7,"pith_summary":"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.","feed_headline":"Antimatroid sorting matches the information-theoretic limit","feed_subtitle":"Topological heapsort sorts any antimatroid with optimal comparisons and runtime.","key_machinery":"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)$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the topological heapsort algorithm and working-set heap whose queue-time bound (Lemma 4) the paper generalizes to antimatroids.","marker":"[18]"},{"why":"Establishes the information-theoretic bound for $T$-sorting and shows it is not always tight; the paper's optimality result shows tightness for antimatroids.","marker":"[12]"},{"why":"Provides the antimatroid axioms and the trace-restriction facts the paper uses for subsets.","marker":"[2]"},{"why":"Shows ERC sets describe exactly the permutations of antimatroids, grounding the Optimality Theory application.","marker":"[34]"},{"why":"Proves universal optimality of Dijkstra with working-set heaps; the paper connects this to vertex search antimatroids and rederives it.","marker":"[16]"},{"why":"Gives the clique tree construction and properties used by the chordal graph candidate data structure.","marker":"[8]"}],"fun_headline_variants":["Optimal sorting for any antimatroid in record time","Antimatroid sorting hits info-theoretic bound","Sorting with hints: optimal for antimatroids","Topological heapsort generalized to all antimatroids","Antimatroid sorting: optimal comparisons, optimal time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Optimal sorting for any antimatroid in record time","Antimatroid sorting hits info-theoretic bound","Sorting with hints: optimal for antimatroids","Topological heapsort generalized to all antimatroids","Antimatroid sorting: optimal comparisons, optimal time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0002,"raw_usage":{"total_tokens":1392,"prompt_tokens":979,"completion_tokens":413,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":595,"completion_tokens_details":{"reasoning_tokens":334}},"tokens_in":595,"tokens_out":413,"duration_ms":4765,"temperature":1.0,"reasoning_tokens":334,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:14:25.309272+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the antimatroid axioms and the trace-restriction facts the paper uses for subsets."},{"cited_title":"OT grammars, beyond partial orders: ERC sets and antimatroids","cited_arxiv_id":null,"evidence_quote":"Shows ERC sets describe exactly the permutations of antimatroids, grounding the Optimality Theory application."},{"cited_title":"Chandran, L","cited_arxiv_id":null,"evidence_quote":"Gives the clique tree construction and properties used by the chordal graph candidate data structure."}],"review_version":1}