{"id":"044c2f43-df2a-4ec3-8f56-1f97c7506da2","arxiv_id":"2507.11291","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Streaming permutation pattern matching needs Θ(k log n) bits for monotone patterns, about sqrt(n) bits for four length-3 patterns, and linear bits for all larger non-monotone patterns.","lead":"Researchers map how much memory a one-pass algorithm needs to detect ordered patterns in a stream of numbers. The cost depends sharply on the pattern: some patterns need almost no memory, others require storing the whole stream.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.7's Disj-reduction for patterns 3142 and 2143 is internally inconsistent: g1 is defined with offset 4(n−i), but the proof uses 4(i−1); with the stated definition, τ contains 3142 for S={3}, T={2}, n=4 even though S∩T=∅, so Theorem 1.4 is unproven for these two patterns as written.","rationale":"The reader's weakest_assumption focused on the sublinear size-3 algorithms depending on the permutation promise; that is a genuine boundary of the model but not a flaw in the paper's internal argument. The more load-bearing issue is in the lower-bound machinery: Lemma 4.7, which supplies the Disj-hardness for the size-4 patterns 3142 and 2143, is internally inconsistent. The printed definition of g1 uses offset 4(n−i), while the proof text explicitly uses 4(i−1) in two places and the forward construction requires the block of b-values to match the offset of a_i and c_i. With the printed offset, the claimed iff fails: I constructed a concrete n=4 instance with S∩T=∅ where the stream still contains 3142, so the reduction is false as written. This matters because Theorem 1.4 (the Ω(n) lower bound for all non-monotone patterns of size ≥4) reduces to the set of seven pattern lemmas; if 3142 and 2143 are not covered, the paper's headline trichotomy has a gap. I am not claiming the theorem is false: the intended construction very likely uses 4(i−1), and with that fix the lemma appears sound for both 3142 and 2143. But the manuscript as submitted does not state a correct reduction, and a reader cannot verify the central theorem without guessing the intended offset. The rest of the paper — the monotone-patterns result, the size-3 sublinear algorithms, the SequencePPM lower bound, and the other four size-4 base reductions — appears coherent, and the open questions are honestly labeled. However, because the lower bound for two of the seven base cases rests on an apparent typo that invalidates the proof as written, the appropriate decision is conditional acceptance: the author should correct the offset and re-verify Lemma 4.7, ideally with an automated exhaustive check for small n.","tokens_in":19073,"tokens_out":33665,"duration_ms":320936,"concrete_test":"Implement the construction of Lemma 4.7 exactly as printed, and run an exhaustive brute-force PPM check for n=4 and all S,T⊆[4] for π=3142 and π=2143; the instance S={3}, T={2} already violates the claimed equivalence (τ contains 3142 although S∩T=∅). Then redo the same exhaustive check after replacing the offset 4(n−i) by 4(i−1) in the definition of g1, for n up to 6, and verify that the equivalence with S∩T≠∅ holds for all S,T. If the corrected construction passes, Lemma 4.7 is salvageable by a one-line fix; if it does not, the lower bound for 3142 and 2143 requires a genuinely new proof.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Lemma 4.7, the definition sets (b_{2i−1}, b_{2i}) = (4(n−i)+1, 4(n−i)+4) for i∈T, while a_i and c_i use offset 4(i−1). The forward direction claims (a_i, b_{2i−1}, b_{2i}, c_i) is an occurrence of π, which requires the b-pair to lie in the same value range as a_i and c_i; this only holds when i = (n+1)/2, not for general i. The converse direction even more explicitly assumes the matching offset: it says 'This means τ(i2) = 4(i−1)+1 and τ(i3) = 4(i−1)+4', which contradicts the printed definition. With the offset as printed, the reduction is false: for n=4, π=3142, S={3}, T={2} (which are disjoint), the constructed τ = 2,6,11,14,16,13,9,12,8,5,4,1,3,7,10,15 contains the subsequence 11,9,12,10 at indices 3,7,8,14, which is order-isomorphic to 3142. Hence the iff property fails. Since 3142 and 2143 are two of the seven base patterns whose complement/reverse orbits cover all non-monotone size-4 permutations, Theorem 1.4 — the Θ̃(n) lower bound for every non-monotone pattern of size at least 4 — is unsupported for these two patterns as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies streaming permutation pattern matching (PPM), where the text is a permutation of [n] revealed one value at a time, and asks for the minimum space needed to decide whether the text contains a fixed pattern π. The main results are: Θ(k log n) space for monotone patterns; O(√(n log n)) or O(√n log n) space for the four non-monotone length-3 patterns 312, 132, 213, 231; and Θ̃_π(n) space for all other non-monotone patterns. For the sequence variant, where the input is an arbitrary sequence of distinct values from [n], the paper proves Θ̃_π(n) lower bounds for every non-monotone pattern. The upper bounds are based on a modified LIS algorithm and two bespoke √n-space algorithms for size-3 patterns; the lower bounds are based on reductions from set disjointness, with a separate reduction for each of seven base patterns that cover all non-monotone length-4 patterns under complement and reversal.","tokens_in":19473,"tokens_out":33976,"duration_ms":375548,"significance":"If the results stand, the paper gives a nearly complete space-complexity classification for streaming permutation pattern matching and a striking separation between permutation streams and arbitrary distinct-value streams. The algorithmic ideas, especially the counting of unseen values in intervals to obtain sublinear space for 312/132 and 213/231, are novel and well developed. The paper is also careful to state the non-uniform model, to extend lower bounds to multi-pass and randomized/nondeterministic algorithms, and to discuss why standard two-party communication lower bounds cannot give non-trivial bounds for the length-3 cases. These are genuine strengths. However, the central lower-bound classification for all non-monotone patterns of length at least four rests on Lemma 4.7, and that lemma has a concrete indexing error that invalidates the reduction as printed.","major_comments":[{"comment":"The reduction for π=3142 and π=2143 is internally inconsistent. In the displayed definition, (b_{2i−1}, b_{2i}) uses the offset 4(n−i), whereas a_i and c_i in f1(S) and f2(S) use the offset 4(i−1). The forward direction therefore does not hold as printed: (a_i, b_{2i−1}, b_{2i}, c_i) is an occurrence only when 4(i−1) equals 4(n−i), i.e., i=(n+1)/2; and the converse explicitly assumes τ(i2)=4(i−1)+1 and τ(i3)=4(i−1)+4, contradicting the printed block values 4(n−i)+1 and 4(n−i)+4. Concretely, for π=3142, n=4, S={3}, T={2}, the constructed τ is (2,6,11,14,16,13,9,12,8,5,4,1,3,7,10,15), and the subsequence (11,9,12,10) at indices (3,7,8,14) is order-isomorphic to 3142 although S∩T=∅. Since 3142 and 2143 are two of the seven base patterns used to cover all non-monotone length-4 patterns by complement/reversal, Theorem 1.4 is not established for the patterns 3142, 2413, 2143, and 3412 as written. This is more than a typo: replacing 4(n−i) with 4(i−1) in the definition creates many additional increasing pairs in g1(T), so the converse of the reduction fails; the indexing of the reduction needs a substantive repair.","section":"Lemma 4.7, §4.1"}],"minor_comments":[{"comment":"The statement of Theorem 1.5 gives O(√n log n) for both {312,132} and {231,213}, but the algorithm in §5.1 uses k=⌊√(n log n)⌋ and achieves O(√(n log n)) for 312/132, matching the abstract; the theorem statement should be corrected to reflect this difference.","section":"Theorem 1.5 and Abstract"},{"comment":"In the proof of Lemma 4.6, the text says 'We claim that τ contains 4231 if and only if S∩T≠∅', but the statement and the surrounding argument concern the pattern 4312; the claim should be corrected to 4312.","section":"Lemma 4.6"},{"comment":"In Lemma 4.7, the line 'Let g1(S) = b1b2 . . . b2n' should read g1(T), since the block is defined in terms of T.","section":"Lemma 4.7"},{"comment":"In Lemma 3.2, ρ is first defined as an increasing sequence of length k−2, but later the proof refers to sequences ρ=r1...r_{k−1} and σ=s1...s_{k−1}; the length notation should be made consistent (the counting with k−3 matches length k−2).","section":"Lemma 3.2"},{"comment":"The heading of §5.2 reads 'An algorithm for 213-PPM', while the text states that the algorithm is for 231-PPM (from which 213 follows by complementation); the heading should be aligned with the text.","section":"§5.2 heading"}],"recommendation":"major_revision","confidential_remarks":"The flaw in Lemma 4.7 is localized and I expect that a corrected indexing (for example, applying a reversal bijection to one player's set so that a_i and b-block offsets align) can restore Theorem 1.4 without changing the rest of the paper. The remaining proofs are generally careful, and the algorithmic sections are a substantial contribution, so I would not reject the paper on the basis of this error. I would ask the authors to repair Lemma 4.7 and to check its implications for Theorem 1.4 carefully."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a solid, genuinely new paper, and the streaming space-complexity map for PPM is worth having. But the stress-test note is correct: Lemma 4.7 as printed is broken. The b-pair definition uses offset 4(n−i), while the proof uses 4(i−1). With the printed definition the reduction fails—the counterexample works: n=4, π=3142, S={3}, T={2} gives a τ containing 3142 despite disjoint sets. So Theorem 1.4 is currently unproven for 3142, 2143 and their orbits. The fix is a one-line change (replace n−i by i−1), and with that the proof reads consistently. That makes this a typo with theorem-level consequences in the writeup, not a conceptual gap.\n\nCredit where due: the paper is the first to treat PPM in the streaming model under the permutation promise, and the separation between permutation streams and arbitrary distinct-integer streams is a real insight. The Θ(k log n) monotone-pattern bounds are clean. The 312 algorithm is neat, especially the disjoint-interval invariant. The 213 algorithm is much more intricate; I did not find a concrete error in it, but it is the part a referee should check hardest. The Section 5.3 observation that one-way communication cannot prove an ω(1) lower bound for length-3 patterns is a useful structural remark. The remaining gap for size-3 patterns is honestly labeled as a conjecture.\n\nThe rest of the lower-bound machinery, including Lemma 4.5, checks out. Citation pattern is unremarkable; self-citations are contextual.\n\nVerdict: send to referees. After the Lemma 4.7 fix and a careful pass over Section 5.2, this should be accepted. Your reader's soundness score of 8 was a bit generous given the bug, but the damage is local and easily repaired.","headline":"Worthwhile new streaming PPM paper, but Lemma 4.7 has a one-line offset bug that currently breaks the lower bound for 3142/2143.","tokens_in":19931,"tokens_out":11178,"would_cite":true,"duration_ms":116065,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","05A05","68W32"],"pacs":[],"model":"deepseek-v4-flash","headline":"Streaming permutation pattern matching splits into three space regimes: k log n, root-n, and n bits.","keywords":["permutation patterns","streaming algorithms","space complexity","pattern matching","communication complexity","sublinear space","permutation streams"],"falsifier":"A single concrete counterexample would settle the upper-bound claims: exhibit a permutation of $[n]$ on which the 312-algorithm or the 231-algorithm stores more than $C\\sqrt{n}\\log n$ bits of state before reporting (for example, more than $n/k$ pairwise-disjoint interval pairs in $D$), violating Theorem 1.5. For the lower-bound side, the decisive test would be to construct a streaming algorithm using $o(n)$ bits for any non-monotone pattern of length four, which Theorem 1.4 rules out.","tokens_in":18907,"feed_emoji":"🧩","tokens_out":12546,"duration_ms":125309,"temperature":0.7,"pith_summary":"This paper asks how much memory a streaming algorithm needs to decide whether a permutation of $[n]$, revealed one value at a time, contains a fixed pattern $\\pi$. It establishes a trichotomy: monotone patterns are cheap, with space $\\Theta(k \\log n)$; each of the four non-monotone patterns of size three can be decided in sublinear space, about $\\sqrt{n}\\log n$ bits; and every other non-monotone pattern forces $\\widetilde{\\Theta}_\\pi(n)$ bits, linear up to polylog factors. If the stream is instead an arbitrary sequence of distinct values, the paper shows all non-monotone patterns require linear space, which isolates the permutation assumption as the source of the sublinear upper bounds. The value of the result is that the combinatorial fact \"every value appears exactly once\" becomes algorithmic leverage, and the open gap for the four small patterns is a concrete, attackable conjecture.","feed_headline":"Pattern search in permutation streams costs log n, root-n, or n bits","feed_subtitle":"Monotone patterns need k log n bits, four size-3 patterns need root-n bits, and all others need linear space.","key_machinery":"The proofs run on two kinds of machinery. Lower bounds come from reductions from two-party disjointness: for each non-monotone pattern, one builds the stream from two sets $S$ and $T$ (split between the two players) so that an occurrence of $\\pi$ exists exactly when $S\\cap T$ is nonempty, transferring the $n+1$-bit communication lower bound to space. Upper bounds for the four size-3 patterns exploit the permutation guarantee directly. The 312-algorithm (and by complement, 132) keeps the running maximum $h$, the set $A$ of seen values in the top $k$ positions below $h$, and a collection $D$ of decreasing pairs whose value intervals $[b,a]$ are pairwise disjoint; disjointness bounds $|D|\\le n/k$ and yields $O(k + (n/k)\\log n) = O(\\sqrt{n}\\log n)$ space, while completeness uses the fact that any value missing from $A$ inside that window has not yet appeared, so it must arrive later. The 231-algorithm (and by complement, 213) partitions the stream into strips of about $\\sqrt{n}$ points and stores per-strip extreme points and counters of how many points fall in a vertical range; after the stream ends, a counter below the total number of values in the range shows that some point must have occurred in an earlier strip, again because every value occurs exactly once.","core_discovery":"On its own terms, the paper's central claim is a classification of streaming space complexity for permutation pattern matching. For $\\pi$-PPM$_n$, the space is $\\Theta(k \\log n)$ for the monotone patterns $12\\dots k$ and $k\\dots 21$, $O(\\sqrt{n}\\log n)$ bits for each of $312$, $132$, $213$, and $231$ (with the abstract reporting the slightly stronger $O(\\sqrt{n\\log n})$ for $312$ and $132$), and $\\widetilde{\\Theta}_\\pi(n)$ for every non-monotone pattern of length at least four. For $\\pi$-SequencePPM$_n$, where the stream is a sequence of distinct values from $[n]$ rather than a permutation, the space is $\\Theta(k \\log n)$ for monotone patterns and $\\widetilde{\\Theta}_\\pi(n)$ for all non-monotone patterns. The lower bounds extend to $p$-pass algorithms with $\\Omega(n/p)$ bits and hold for randomized and nondeterministic streaming algorithms; the sublinear size-3 upper bounds come with no matching lower bound, and the paper conjectures that $\\widetilde{\\Theta}(\\sqrt{n})$ is the true answer for those four patterns.","pith_inferences":["The trick of treating non-appearance as information — a value not yet seen must still arrive — is not limited to these four patterns; a similar counting argument may yield sublinear-space algorithms for other permutation statistics (e.g., testing pattern freeness or approximating pattern counts) in the permutation-stream model, bypassing the known $\\Omega(n)$ inversion-counting barrier.","The one-bit one-way communication bound for all size-$\\le 3$ patterns suggests that proving the conjectured $\\sqrt{n}$ lower bound will require going beyond the disjointness-reduction framework used here; a natural test case is to seek lower bounds against restricted stream models (e.g., algorithms that store only counts and extremes).","An empirical probe of the conjecture is straightforward: run the two algorithms on random permutations of increasing $n$ and record the maximum number of stored pairs or counters; observing super-$\\sqrt{n}$ growth would point to a flaw in the space analysis, while flat growth would lend weight to the conjecture."],"forward_implications":["Monotone patterns can be recognized in a stream with only $\\Theta(k \\log n)$ bits, so detecting an increasing or decreasing run of length $k$ costs essentially the same as the classic longest-increasing-subsequence algorithm.","For the four size-3 patterns, streaming PPM is solvable in $O(\\sqrt{n}\\log n)$ bits, which separates the permutation model from the sequence-of-distinct-values model, where the same patterns require $\\Omega(n)$ bits.","For every non-monotone pattern of length at least four, any deterministic streaming algorithm needs $\\Omega_\\pi(n)$ bits, and this survives $p$ passes with a $\\Omega(n/p)$ bound, as well as randomization or nondeterminism.","If the conjecture that the $\\sqrt{n}$ bounds are tight is correct, streaming permutation pattern matching has exactly three regimes: $\\Theta(\\log n)$, $\\widetilde{\\Theta}(\\sqrt{n})$, and $\\widetilde{\\Theta}(n)$.","The size-3 detection algorithms differ in reporting power: the 312-algorithm finds and outputs an occurrence, while the 231-algorithm decides existence without necessarily locating the occurrence."],"supporting_citations":[{"why":"Supplies the longest-increasing-subsequence algorithm whose early-stopping variant gives the $O(k \\log n)$ upper bound for monotone patterns.","marker":"[Sch61]"},{"why":"Davenport-Schinzel sequences bound the state sequence in the $\\Omega(\\log n)$ lower bound for monotone patterns.","marker":"[AS00]"},{"why":"Provides the disjointness communication-complexity lower bound ($DCC(Disj_n)=n+1$) that all the linear-space lower bounds reduce from.","marker":"[KN97]"}],"fun_headline_variants":["Space for permutation patterns in streams: k log n, sqrt n, or n","Streaming pattern matching: monotone cheap, others need sqrt n or linear","Pattern type decides streaming space: from k log n to n","Only monotone patterns stream cheaply; others need sqrt n or n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The sublinear algorithms for $312$, $132$, $213$, and $231$ assume the input is exactly a permutation of $[n]$, so every value not yet seen is guaranteed to come later; without that guarantee the paper's own Theorem 1.3 shows the same patterns need $\\Omega(n)$ bits, so this assumption carries the entire sublinear upper bound.","fun_headline_variants_meta":{"raw":{"variants":["Space for permutation patterns in streams: k log n, sqrt n, or n","Streaming pattern matching: monotone cheap, others need sqrt n or linear","Pattern type decides streaming space: from k log n to n","Only monotone patterns stream cheaply; others need sqrt n or n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00041,"raw_usage":{"total_tokens":2200,"prompt_tokens":1094,"completion_tokens":1106,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":710,"completion_tokens_details":{"reasoning_tokens":1026}},"tokens_in":710,"tokens_out":1106,"duration_ms":12386,"temperature":1.0,"reasoning_tokens":1026,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:25:04.258505+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A single concrete counterexample would settle the upper-bound claims: exhibit a permutation of $[n]$ on which the 312-algorithm or the 231-algorithm stores more than $C\\sqrt{n}\\log n$ bits of state before reporting (for example, more than $n/k$ pairwise-disjoint interval pairs in $D$), violating Theorem 1.5. For the lower-bound side, the decisive test would be to construct a streaming algorithm using $o(n)$ bits for any non-monotone pattern of length four, which Theorem 1.4 rules out.","supporting_citations":[],"review_version":1}