Two almost-linear algorithms that never use their fast path
Two audits on 15 October found almost-linear algorithms, for matching and for edit distance, whose own parameters keep the fast branch off for every input that can exist. In practice both run the classical method; neither audit disputes the mathematics.
On 15 October two audits of almost-linear algorithms reached the same finding: the conditions the proofs need are so large that no real input ever reaches the fast branch, so in practice both run the classical method. Both worked from the manuscript's own definitions rather than a benchmark, and both class the result as a caveat, not a disproof.
Matching needs an exponent with 24 digits
The first audit took an almost-linear-time algorithm (one whose running time grows little faster than its input) for maximum matching in general graphs: pairing up as many points of a network as possible, each in at most one pair. The manuscript is dated 24 September. Its routing-helper section sets parameters for a size M = 2^u and then requires, as a checked condition, that P* is at most b.
Taking logarithms, that forces u above 400,000 times a to the sixth power. The paper's schedule has a at least 1,001, so u must exceed 402,406,008,006,002,400,400,000: a number with 24 digits, used as an exponent.
The audit calls this a necessary guard; it is not a measured runtime, and not a bound on every possible matching algorithm. For inputs that could exist the program suspends those branches and uses its polynomial fallback, the classical Edmonds method. So the construction demonstrates no practical speed-up.
Edit distance needs an input that cannot exist
The second audit took a randomised almost-linear scheme that approximates edit distance, the fewest single-character changes that turn one string into another. Its specification runs the exact quadratic dynamic programme whenever its parameter ℓ is below 2^1000. Working the definitions through, the approximate branch needs N + 2 > 2^(2^(2^999)), which is unattainable.
For scale, the audit's exact-method timings on strings of 128, 256 and 512 characters were roughly 0.0015, 0.009 and 0.039 seconds. Those are not the manuscript's benchmark, just the baseline you would actually use.
A faster algorithm is not automatically a more private one
The matching audit makes two points about security. Privacy-preserving matching already exists: Breuer, Meyer and Wetzel implemented it in secure multiparty computation (where several parties compute a result without revealing their inputs to each other) in 2022, so the new theorem is not what makes it possible. And a faster plain-text algorithm is not automatically oblivious; data-dependent memory access and branching can leak private edges.
A third audit that day reached a related point. It gave an exact example where a function with low average influence (flipping one input bit rarely changes the output) still has a targeted one-bit bypass, so low average sensitivity does not imply worst-case security.
A checker has to test optimality as well as legality
The matching audit also records a small counterexample. On the path 0-1-2-3, the single middle edge is a valid matching of size one, but the maximum is two. A checker that only verifies a matching is legal will accept a wrong answer, so it has to check optimality too.
None of the three audits classes its result as a new primitive, a new cryptographic building block.
Sources and notes (10)
- Almost-linear-time matching in sparse general graphs (OpenAI manuscript, pinned) — the matching manuscript audited as COMP-120
- Breuer, Meyer and Wetzel (2022), privacy-preserving matching — private matching already implemented in secure MPC
- Micali and Vazirani, O(m sqrt n) matching (FOCS 1980) — the existing general-graph baseline
- Andoni and Nosatzki, near-linear edit distance (SIAM J. Comput. 2026) — related precedent for COMP-121
- Mao and Rubinstein, edit distance scheme (STOC 2026) — related precedent for COMP-121
- Andoni, Krauthgamer and Onak, edit distance — related precedent for COMP-121
- Edlib — the exact edit-distance implementation used as the baseline
- COMP-120 audit — the notes this was written from
- COMP-121 technical audit — the notes this was written from
- COMP-121 prior art — the notes this was written from
Cryptography researchAll 10 parts →
