{"id":"ba03a81c-8265-45f1-ac0d-b59b4591f84f","arxiv_id":"1908.02518","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Ripser computes Vietoris-Rips persistence barcodes without constructing the coboundary matrix, using apparent and emergent pairs to shortcut the reduction, and outperforms prior software in time and memory.","lead":"This paper presents Ripser, a fast C++ program for computing Vietoris-Rips persistence barcodes, shape summaries of point-cloud data that show which features persist across scales. Instead of building and storing the full coboundary matrix, Ripser recomputes columns on demand and uses apparent pairs to skip most of the work, making it much faster and lighter than earlier tools.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Dimension-1 zero-pair shortcut depends on distinct pairwise distances (Thm. 3.10); tied distances can make zero pairs non-apparent, so the 'most columns never reduced' efficiency claim is unquantified for tied inputs.","rationale":"I read the paper as a methods/software contribution whose central claim is exact and efficient VR persistence computation via implicit reduction plus apparent/emergent-pair shortcuts. The correctness core is solid: Lemmas 3.3, 3.5, and 3.8 are elementary and the open-source implementation is widely used. The weakest point is not correctness but the scope of the efficiency claim. Theorem 3.10 is the only result that guarantees dimension-1 zero pairs cost nothing, and it explicitly assumes distinct pairwise distances. Real inputs often have ties (grid data, symmetric point sets, discrete metrics), and the paper neither analyzes this case nor benchmarks it. The reader's conditional verdict already identifies exactly this assumption, and I agree. I would not strengthen to reject, because the algorithm is correct and the generic-case performance is convincingly demonstrated; I would keep the conditional recommendation, asking for tied-distance benchmarks and a discussion of whether zero pairs remain emergent. No ad hominem or theatrical framing is intended; the concern is a precise scope limitation.","tokens_in":33185,"tokens_out":21100,"duration_ms":238840,"concrete_test":"Run Ripser on synthetic metric spaces with tied distances (e.g., k x k integer grids with Euclidean distance, or complete graphs with duplicated edge weights) and compare Tables 2 and 3 with and without the apparent/emergent shortcuts: count dimension-1 zero-persistence pairs that are non-apparent and non-emergent, and measure runtime and memory. If nonzero counts appear for tied inputs and the speedup shrinks markedly, the efficiency claim needs a tied-data qualification.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claim is that Ripser computes exact Vietoris-Rips barcodes with far less time and memory because most columns are never reduced. For dimension 1, the theoretical support for skipping zero-persistence pairs is Theorem 3.10: under distinct pairwise distances, zero pairs are exactly apparent pairs. Its proof uses the distinctness assumption twice: the edge E is the unique facet of F attaining diam(F), and every other edge of the cofacet tau has smaller diameter. If pairwise distances tie, a zero pair (E,F) can fail to be apparent, because E need not be the youngest facet of F or F need not be the oldest cofacet of E; in principle it can also fail to be emergent, so the emergent-pair shortcut would construct the full coboundary column. The paper does not report benchmarks on tied metric data, so the abstract's unqualified claim of substantial improvement is not established for that regime. Correctness is unaffected; this is a gap in the efficiency claim's scope.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents the algorithm underlying the software Ripser for computing Vietoris–Rips persistence barcodes. The main ideas are threefold: the filtration coboundary matrix is represented implicitly and columns are recomputed on demand; the simplexwise lexicographic refinement of the Rips filtration is used with an implicit column-reduction scheme; and the notions of apparent pairs and emergent pairs are introduced so that many zero-persistence columns can be identified and skipped without performing the reduction. The theoretical part proves that apparent pairs form a discrete gradient, that apparent pairs are persistence pairs, and that, under distinct pairwise distances, every zero-persistence pair in dimension 1 is apparent. The experimental part compares Ripser with Dionysus, DIPHA, Gudhi, and Eirene on several datasets, reporting large speedups and memory reductions.","tokens_in":33244,"tokens_out":24262,"duration_ms":280209,"significance":"If the claims hold, this is a practically important contribution: exact Vietoris-Rips barcodes are computed with substantially less memory and time than previous software, and the apparent-pairs construction is of independent theoretical interest as a discrete gradient associated to a simplexwise filtration. The paper's mathematical core is sound: Lemmas 3.3, 3.5, 3.6, and 3.8 are proved carefully, Theorem 3.10 is a genuine structural result under its stated hypothesis, and the counting argument in Section 3.3 is parameter-free. The software and the benchmark harness are publicly available, which strengthens reproducibility. The principal caveat is that the most aggressive dimension-1 shortcut is proved only for metrics with distinct pairwise distances; the experimental claims are not scoped to that assumption, and no tied-distance benchmarks are reported.","major_comments":[{"comment":"The dimension-1 zero-pair shortcut is proved only under the assumption of distinct pairwise distances, and the proof uses this assumption twice: once to make E the unique facet of F attaining diam(F), and once to ensure that every other edge of the cofacet tau has smaller diameter. Under ties, neither step is guaranteed, so a zero-persistence pair of the simplexwise refinement need not be apparent, and in principle it need not be initially emergent either. The sentence in Section 5 stating that \"as predicted by Theorem 3.10, in dimension 1 every zero pair is an apparent pair\" therefore overstates the scope, and Tables 1-3 contain no tied-distance input. Since the abstract's unqualified efficiency claim that \"most columns are never reduced\" rests substantially on this shortcut, please either prove a bound for tied inputs, add benchmarks with tied metrics, or explicitly scope the efficiency claim to the generic case.","section":"Section 3.5, Theorem 3.10"},{"comment":"The experimental section reports no tied-distance datasets, even though the theoretical guarantee for the dimension-1 shortcut is restricted to distinct pairwise distances by Theorem 3.10. Integer-valued and grid-like distance matrices are common in applications of Vietoris-Rips persistence, so the central performance claim should be tested on at least one such input, or the paper should state clearly that the reported speedups are demonstrated only for generic inputs. In addition, the timings in Tables 1 and 3 appear to be single runs with no variance information; the difference between 15.3 s and 15.6 s in the sphere3 row of Table 3 is within typical run-to-run noise and should not be presented as a meaningful ordering.","section":"Section 5, Tables 1 and 3"}],"minor_comments":[{"comment":"The last sentence of the proof, \"Similarly, E must be the oldest cofacet of E in the filtration order,\" appears to contain a copy-and-paste error: it should say that E must be the youngest facet of F.","section":"Section 3.5, proof of Proposition 3.9"},{"comment":"The text says that facets are enumerated \"implemented in the class simplex_coboundary_enumerator\"; this is presumably a typo for the facet/boundary enumerator class, since the cofacet enumerator is described separately.","section":"Section 4"},{"comment":"The caption should state explicitly that each reported timing is a single run and that no confidence intervals or repeated runs are provided, so that small differences in the tables are not over-interpreted.","section":"Section 5, Tables 1 and 3"},{"comment":"The column headers \"non-zero pairs,\" \"non-emergent,\" \"non-shortcut,\" \"non-apparent,\" and \"total pairs\" should be defined in the caption; the current layout makes it difficult to verify the statement that all dimension-1 zero pairs are shortcut pairs.","section":"Section 5, Table 2"}],"recommendation":"major_revision","confidential_remarks":"The mathematical content is sound and the paper is well positioned in the field. The main gap is not correctness but scoping of the efficiency claim: Theorem 3.10 is the theoretical basis for the dimension-1 shortcut and requires distinct pairwise distances, while the abstract and Section 5 present the performance gain without that caveat and without tied-data experiments. I expect a revision that either adds tied-distance benchmarks or qualifies the claims, together with the small presentation fixes, to be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Ulrich's Ripser paper is one of those rare methods papers where the software has already changed practice, and the theory holds up. What's actually new: apparent pairs (Def. 3.2) — a local condition that lets you read off a large fraction of persistence pairs directly from the filtration, without matrix reduction — and the generalization to emergent pairs. He proves these form a discrete gradient (Lemmas 3.3, 3.5, 3.6) and that in dimension 1, under distinct pairwise distances, zero-persistence pairs are exactly apparent pairs (Thm 3.10), which is the efficiency guarantee for the shortcut. The paper is also transparent that special cases of apparent pairs appeared in Kahle, Eirene, Delgado-Friedrichs et al., and Lampret, so the novelty claim is properly scoped. The integration with implicit coboundary representation and clearing/cohomology is clean, and the counting argument in Section 3.3 explains the practical asymmetry between homology and cohomology.\n\nThe soft spots are modest. The stress-test note is right: Theorem 3.10 assumes distinct pairwise distances, used twice in the proof. With tied distances, a zero-persistence pair in dimension 1 may fail to be apparent or even emergent, so the \"most columns never reduced\" claim is only guaranteed for generic inputs. The paper should either state this assumption in the abstract or report experiments on tied data (integer distances, duplicate points). I don't think this is a correctness problem — the algorithm remains correct, and for typical floating-point data from continuous distributions ties are measure-zero — but the efficiency claim as written is slightly broader than the theorem supports.\n\nBenchmarks are single runs with no variance. For a paper whose headline is 'one to two orders of magnitude faster,' a few repeated runs and error bars would be nice, especially for the small gaps (dragon 2.4s vs 2.9s). Not fatal; the Docker reproducibility helps.\n\nCitation pattern is fine: DIPHA/PHAT self-citations are relevant and disclosed, and the independent-discovery discussion is exemplary.\n\nVerdict: this deserves a serious referee and likely acceptance with minor revisions. The paper is mathematically sound, the software is real and widely used, and the theoretical framing of apparent pairs is of independent interest. I'd suggest the editor require a short note on tied-distance behavior, and ask for benchmark variance where feasible.","headline":"Ripser is a genuinely important methods paper: the apparent/emergent pair machinery is clean and proved, and the only real soft spots are the distinct-distances assumption behind the dim-1 shortcut and the single-run benchmarks.","tokens_in":33926,"tokens_out":2084,"would_cite":true,"duration_ms":21310,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["55N31"],"pacs":[],"model":"deepseek-v4-flash","headline":"Ripser computes exact Vietoris–Rips persistence barcodes without storing the filtration coboundary matrix, using apparent pairs to skip most column reductions.","keywords":["persistent homology","Vietoris-Rips complex","persistence barcode","matrix reduction","persistent cohomology","apparent pairs","discrete Morse theory","implicit matrix reduction"],"falsifier":"Run the same Vietoris-Rips computation on a finite metric space with many equal pairwise distances, such as equally spaced points on a line, and on a generic perturbation of it; if the tied case shows many zero-persistence dimension-1 pairs that are not apparent and a corresponding increase in reduced columns, the distinct-distances assumption is the load-bearing condition. A direct test of Theorem 3.10 is to search for any metric space with all pairwise distances distinct whose simplexwise refinement has a zero-persistence pair in dimension 1 that is not apparent; finding one would refute the theorem.","tokens_in":32828,"feed_emoji":"📊","tokens_out":7918,"duration_ms":80959,"temperature":0.7,"pith_summary":"This paper presents the algorithm behind Ripser, a program that computes Vietoris–Rips persistence barcodes exactly. The central claim is that the filtration coboundary matrix, which most persistence software builds and stores explicitly, can be represented implicitly: columns are recomputed on the fly, so memory use is low and most columns are never reduced at all. The key object is the apparent pair, a pair $(\\sigma,\\tau)$ in which $\\sigma$ is the youngest facet of $\\tau$ and $\\tau$ is the oldest cofacet of $\\sigma$; such pairs are already reduced, can be detected locally without matrix operations, and form a discrete gradient. The paper proves that, when all pairwise distances are distinct, every zero-persistence pair in dimension 1 is an apparent pair. Benchmarks against previous implementations show large reductions in both running time and memory.","feed_headline":"Ripser skips most matrix reductions to compute Rips barcodes","feed_subtitle":"Recomputing coboundary columns and reading apparent pairs directly cuts time and memory.","key_machinery":"The load-bearing object is the apparent pair: in a simplexwise filtration, a pair $(\\sigma,\\tau)$ with $\\dim\\tau=\\dim\\sigma+1$ such that $\\sigma$ is the youngest facet of $\\tau$ and $\\tau$ is the oldest cofacet of $\\sigma$. Apparent pairs are persistence pairs, already reduced in the boundary or coboundary matrix, and together they form a discrete gradient. The algorithm wraps this in three supporting devices: the lexicographic refinement of the Vietoris-Rips filtration (order simplices by diameter, then dimension, then reverse colexicographic vertex order), the combinatorial number system (an order-preserving bijection from decreasing vertex tuples to natural numbers that makes facet and cofacet enumeration cheap), and implicit matrix reduction (compute the coboundary of a simplex when needed, keep only the reduction columns for death indices, and store pivots of already reduced columns instead of the reduced matrix). The emergent-pairs shortcut extends the same idea to pairs that become apparent during reduction, so that many coboundary columns are never fully constructed.","core_discovery":"The paper's own claim is that an exact persistence computation for a Vietoris-Rips filtration does not require an explicit filtration coboundary matrix, and that most columns of that matrix are already reduced. Ripser encodes the filtration order and the coboundary operator algorithmically, using the combinatorial number system to index simplices as integers and enumerating cofacets on demand, while storing only the reduction-matrix columns for death indices. Apparent pairs are the conceptual hinge: they are persistence pairs by Lemma 3.3, they constitute a discrete gradient by Lemma 3.5, and they can be read directly from facet and cofacet comparisons. Under the genericity assumption of distinct pairwise distances, Theorem 3.10 shows that in dimension 1 the zero-persistence pairs of the simplexwise refinement coincide exactly with the apparent pairs, so no column corresponding to a zero-persistence pair needs reduction. The combination of implicit reduction, cohomology, clearing, and apparent and emergent shortcuts yields an exact barcode with a far smaller column-reduction workload, which the experiments attribute to a large speedup and memory saving.","pith_inferences":["A natural stress test not performed in the paper is to measure how the shortcut degrades as pairwise distances become tied; Theorem 3.10's condition suggests that tie-breaking order could be engineered to restore the apparent-pairs property.","The apparent-pairs gradient may be useful beyond barcode computation, for example in simplifying Rips complexes by canceling critical cells or in constructing smaller discrete Morse complexes with predictable persistence.","The implicit-coboundary strategy transfers to other algebraic settings, such as cellular filtrations or algebraic discrete Morse theory, wherever an algebraic apparent pair with a unit coefficient can be detected locally; the gain depends on cofacet enumeration being much cheaper than memory access."],"forward_implications":["For any finite metric space with all pairwise distances distinct, the dimension-1 zero-persistence pairs of the lexicographic refinement are exactly the apparent pairs, so the shortcut detects every zero-persistence pair without column reduction.","Because apparent pairs are already reduced, their pivots need not be stored or looked up, so memory use scales with the number of non-apparent columns rather than with the full simplex count.","Computing persistent cohomology with clearing reduces the set of columns to reduce to the death columns plus one essential 0-dimensional column, making the reduction workload roughly proportional to the number of death simplices.","Apparent pairs give a canonical way to turn any total order on the simplices of a complex into a discrete Morse function, connecting the speedup directly to discrete Morse theory.","The same algorithmic representation of the coboundary applies to any filtration whose cofacets can be enumerated and whose filtration order can be compared, so the method is not tied to Vietoris-Rips complexes alone."],"supporting_citations":[{"why":"Establishes the matrix reduction algorithm and Proposition 3.1, which reads persistence pairs from pivots of the reduced filtration boundary matrix; it is the base of all variants.","marker":"[10]"},{"why":"Introduces dualities between persistent homology and cohomology and between absolute and relative cohomology, justifying barcode computation by coboundary reduction.","marker":"[13]"},{"why":"Introduces the clearing or twist optimization that removes inessential birth columns before reduction, a prerequisite for the cohomology speedup.","marker":"[8]"},{"why":"Constructs the lexicographic discrete gradient from a vertex order; the apparent-pairs gradient generalizes this, and Lemma 3.8 identifies the two.","marker":"[24]"},{"why":"Provides discrete Morse theory and the notion of gradient pairs; Lemma 3.5 shows apparent pairs form a discrete gradient.","marker":"[17]"},{"why":"Documents the earlier cohomology-plus-clearing speedup and serves as the state-of-the-art toolbox whose bottleneck motivates implicit representation.","marker":"[5]"},{"why":"Supplies the minimum enclosing radius threshold used by default, above which Vietoris-Rips homology is trivial.","marker":"[21]"},{"why":"Contributed the assembly strategy of skipping simplices in zero-persistence apparent pairs, adopted in Ripser version 1.2.","marker":"[52]"}],"fun_headline_variants":["Ripser: matrix-free Rips barcodes","Apparent pairs slash Rips barcode computation time","Implicit coboundary: Ripser's fast path to barcodes","No explicit matrix, just exact Rips barcodes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The efficiency guarantee rests on the genericity assumption that all pairwise distances are distinct; with ties, zero-persistence pairs in dimension 1 need not be apparent pairs, so more columns must be reduced and the speedup can degrade.","fun_headline_variants_meta":{"raw":{"variants":["Ripser: matrix-free Rips barcodes","Apparent pairs slash Rips barcode computation time","Implicit coboundary: Ripser's fast path to barcodes","No explicit matrix, just exact Rips barcodes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001473,"raw_usage":{"total_tokens":5878,"prompt_tokens":856,"completion_tokens":5022,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":472,"completion_tokens_details":{"reasoning_tokens":4952}},"tokens_in":472,"tokens_out":5022,"duration_ms":38549,"temperature":1.0,"reasoning_tokens":4952,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:41:33.850327+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same Vietoris-Rips computation on a finite metric space with many equal pairwise distances, such as equally spaced points on a line, and on a generic perturbation of it; if the tied case shows many zero-persistence dimension-1 pairs that are not apparent and a corresponding increase in reduced columns, the distinct-distances assumption is the load-bearing condition. A direct test of Theorem 3.10 is to search for any metric space with all pairwise distances distinct whose simplexwise refinement has a zero-persistence pair in dimension 1 that is not apparent; finding one would refute the theorem.","supporting_citations":[{"cited_title":"Cohen-Steiner, H","cited_arxiv_id":null,"evidence_quote":"Establishes the matrix reduction algorithm and Proposition 3.1, which reads persistence pairs from pivots of the reduced filtration boundary matrix; it is the base of all variants."},{"cited_title":"de Silva, D","cited_arxiv_id":null,"evidence_quote":"Introduces dualities between persistent homology and cohomology and between absolute and relative cohomology, justifying barcode computation by coboundary reduction."},{"cited_title":"Chen and M","cited_arxiv_id":null,"evidence_quote":"Introduces the clearing or twist optimization that removes inessential birth columns before reduction, a prerequisite for the cohomology speedup."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Constructs the lexicographic discrete gradient from a vertex order; the apparent-pairs gradient generalizes this, and Lemma 3.8 identifies the two."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides discrete Morse theory and the notion of gradient pairs; Lemma 3.5 shows apparent pairs form a discrete gradient."},{"cited_title":"Bauer, M","cited_arxiv_id":null,"evidence_quote":"Documents the earlier cohomology-plus-clearing speedup and serves as the state-of-the-art toolbox whose bottleneck motivates implicit representation."},{"cited_title":"Henselman-Petrusek","cited_arxiv_id":null,"evidence_quote":"Supplies the minimum enclosing radius threshold used by default, above which Vietoris-Rips homology is trivial."},{"cited_title":"Zhang, M","cited_arxiv_id":null,"evidence_quote":"Contributed the assembly strategy of skipping simplices in zero-persistence apparent pairs, adopted in Ripser version 1.2."}],"review_version":1}