REVIEW 1 major objections 5 minor 14 references
Permutation patterns in streams
T0 review · 1 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Streaming permutation pattern matching splits into three space regimes: k log n, root-n, and n bits.
desk verdict Worthwhile new streaming PPM paper, but Lemma 4.7 has a one-line offset bug that currently breaks the lower bound for 3142/2143. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (1)
- [Lemma 4.7, §4.1] 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.
minor comments (5)
- [Theorem 1.5 and Abstract] 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.
- [Lemma 4.6] 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.
- [Lemma 4.7] In Lemma 4.7, the line 'Let g1(S) = b1b2 . . . b2n' should read g1(T), since the block is defined in terms of T.
- [Lemma 3.2] 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).
- [§5.2 heading] 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.
Circularity Check
No significant circularity: the paper's bounds derive from external benchmarks (Disjointness, LIS) and self-contained constructions, not from their own conclusions.
full rationale
The central claims are produced by standard external tools rather than by defining the target quantities in terms of themselves. Theorem 1.2's upper bound explicitly uses the classical longest-increasing-subsequence algorithm (Section 3: 'we use the well-known longest increasing subsequence algorithm [Sch61, Knu73, Fre75]'), and its lower bound is a direct communication-complexity adversary argument using Davenport-Schinzel sequences. Theorems 1.3 and 1.4 reduce from Disjointness, whose communication complexity is cited to the external textbook Kushilevitz and Nisan (Section 2.2: 'To prove our lower bounds, we will use tools from Communication Complexity [Yao79, Lov90, KN97, RY20]'). The pattern-classification step is an ordinary symmetry reduction: Lemma 2.3 and Observation 2.4 use complement and reverse, with the seven concrete size-4 patterns explicitly listed as covering all others; this is not a self-citation or a renaming of the result. The Section 5 algorithms are proved correct in place via invariants and counting arguments, relying on the permutation property of the stream. The only self-references in the paper are contextual: the author's own Master's thesis [Ber19] is mentioned in the acknowledgments, and [BKM21] is cited for known non-streaming PPM results; neither is load-bearing for any streaming bound. The note about a possible offset inconsistency in Lemma 4.7 is, if correct, an internal proof bug in a reduction, not a circular step, so it does not affect the circularity score. In sum, no fitted parameter is renamed as a prediction, no input is defined in terms of the output, and no load-bearing argument reduces to a self-citation.
Assumptions & free parameters
assumptions (4)
- standard math DCC(Disj_n) = n+1 (deterministic communication complexity of disjointness)
- standard math Davenport-Schinzel sequence bound: a DS sequence of order 2 using m symbols has length at most 2m-1
- domain assumption The streaming algorithm is modeled as a deterministic state machine; space is the log of the number of states; the algorithm may hard-code n (non-uniform)
- domain assumption The input stream is a permutation of [n] (for PPM) or a sequence of distinct values from [n] (for SequencePPM)
Cite this review
Pith. "Pith review of Permutation patterns in streams." pith.science (2026). https://pith.science/paper/Y2HRQ4ST
@misc{pith2026250711291,
author = {Pith},
title = {Pith review of: Permutation patterns in streams},
year = {2026},
howpublished = {\url{https://pith.science/paper/Y2HRQ4ST}},
note = {Machine review of arXiv:2507.11291}
}
abstract
Permutation patterns and pattern avoidance are central, well-studied concepts in combinatorics and computer science. Given two permutations $\tau$ and $\pi$, the pattern matching problem (PPM) asks whether $\tau$ contains $\pi$. This problem arises in various contexts in computer science and statistics and has been studied extensively in exact-, parameterized-, approximate-, property-testing- and other formulations. In this paper, we study pattern matching in a streaming setting, when the input $\tau$ is revealed sequentially, one element at a time. There is extensive work on the space complexity of various statistics in streams of integers. The novelty of our setting is that the input stream is a permutation, which allows inferring some information about future inputs. Our algorithms crucially take advantage of this fact, while existing lower bound techniques become difficult to apply. We show that the complexity of the problem changes dramatically depending on the pattern $\pi$. The space requirement is: $\Theta(k\log{n})$ for the monotone patterns $\pi = 12\dots k$, or $\pi = k\dots21$, $O(\sqrt{n\log{n}})$ for $\pi \in \{312,132\}$, $O(\sqrt{n} \log n)$ for $\pi \in \{231,213\}$, and $\widetilde{\Theta}_{\pi}(n)$ for all other $\pi$. If $\tau$ is an arbitrary sequence of integers (not necessary a permutation), we show that the complexity is $\widetilde{\Theta}_{\pi}(n)$ in all except the first (monotone) cases.
Reference graph
Works this paper leans on
-
[1]
[pat] The International Conference on Permutation Patterns. Accessed: 2025/07/01. URL:https://permutationpatterns.com. [Raz90] Alexander A. Razborov. On the distributional complexity of disjontness. In Mike Paterson, editor,Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, UK, July 16-20, 1990, Proce...
-
[7]
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs
[DG20] Bart lomiej Dudek and Pawe l Gawrychowski. Counting 4-patterns in permuta- tions is equivalent to counting 4-cycles in graphs, 2020.arXiv:2010.00348. [EL21] Chaim Even-Zohar and Calvin Leng. Counting small permutation patterns. In D´ aniel Marx, editor,Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference,...
work page Pith review arXiv 2020
-
[8]
On the strength of comparisons in property testing.Inf
[Fis04] Eldar Fischer. On the strength of comparisons in property testing.Inf. Comput., 189(1):107–116, 2004.doi:10.1016/J.IC.2003.09.003. [Fre75] Michael L. Fredman. On computing the length of longest increasing subsequences.Discrete Mathematics, 11(1):29–35,
-
[1979]
doi: 10.1145/800135.804414. [Zha24] Xiaojin Zhang. Improved algorithm for permutation testing.Theor. Comput. Sci., 986:114316, 2024.doi:10.1016/J.TCS.2023.114316. 23
-
[1990]
[NRRS19] Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, and Christian Sohler. Testing for forbidden order patterns in an array.Random Structures & Algorithms, 55(2):402–426, 2019.doi:10.1002/rsa.20840. [NV24] Ilan Newman and Nithin Varma. Strongly Sublinear Algorithms for Testing Pattern Freeness.TheoretiCS, January
-
[1998]
[BC18] Omri Ben-Eliezer and Cl´ ement L
doi:10.1016/ S0020-0190(97)00209-3. [BC18] Omri Ben-Eliezer and Cl´ ement L. Canonne. Improved bounds for testing forbidden order patterns. In Artur Czumaj, editor,Proceedings of the Twenty- Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2093–2112. SIAM,
-
[2000]
[BBL98] Prosenjit Bose, Jonathan F
doi:10.1016/B978-044482537-7/50002-4. [BBL98] Prosenjit Bose, Jonathan F. Buss, and Anna Lubiw. Pattern matching for permutations.Inf. Process. Lett., 65(5):277–283,
-
[2002]
Association for Computing Machinery. doi:10.1145/ 509907.509964. [AR08] Shlomo Ahal and Yuri Rabinovich. On complexity of the subpattern problem. SIAM Journal on Discrete Mathematics, 22(2):629–649,
Show all 14 references
-
[2014]
Society for Industrial and Applied Mathematics. doi:10. 1137/1.9781611973402.7. 21 [GR22] Pawel Gawrychowski and Mateusz Rzepecki. Faster exponential algorithm for permutation pattern matching. In Karl Bringmann and Timothy M. Chan, editors,5th Symposium on Simplicity in Algor...
-
[2018]
[BEL W22] Omri Ben-Eliezer, Shoham Letzter, and Erik Waingarten
doi:10.1137/1.9781611975031.137. [BEL W22] Omri Ben-Eliezer, Shoham Letzter, and Erik Waingarten. Finding Monotone Patterns in Sublinear Time, Adaptively. In Miko laj Boja´ nczyk, Emanuela 6Thedisjointnessproblem in the proof needs to be replaced by theunique disjointness prob...
-
[2020]
Schensted
[Sch61] C. Schensted. Longest increasing and decreasing subsequences.Canadian Journal of Mathematics, 13:179–191, 1961.doi:10.4153/cjm-1961-015-3. [Vat14] Vincent Vatter. Permutation classes, 2014.arXiv:1409.5159. [Yao79] Andrew Chi-Chih Yao. Some complexity questions related ...
1961 arXiv
-
[2021]
[BKTW21] ´Edouard Bonnet, Eun Jung Kim, St´ ephan Thomass´ e, and R´ emi Watrigant
doi:10.1007/s00453-021-00812-z. [BKTW21] ´Edouard Bonnet, Eun Jung Kim, St´ ephan Thomass´ e, and R´ emi Watrigant. Twin-width I: tractable FO model checking.ACM Journal of the ACM (JACM), 69(1):1–46, 2021.doi:10.1145/3486655. [BMS] Omri Ben-Eliezer, Slobodan Mitrovic, and Pra...
2021
-
[2022]
doi: 10.4230/LIPIcs.ICALP.2022.17
Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik. doi: 10.4230/LIPIcs.ICALP.2022.17. [Ber19] Benjamin Aram Berendsohn. Complexity of permutation pattern match- ing. Master’s thesis, Freie Universit¨ at Berlin,
2022 doi
-
[2024]
doi:10.46298/theoretics.24
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.