Pith. sign in

REVIEW 1 major objections 5 minor 31 references

Quality Control Algorithms for Pattern Counting

T0 review · 1 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that certifying whether pattern counts look random — worst-case exponentially hard — becomes poly(k)-time under quality control, which accepts typical inputs yet rejects every count far from random.

desk verdict The paper's poly(k) quality-control algorithm for pattern counting is a real advance, but the soundness proof as written only covers inputs with distinct values; tied sequences are not handled, and this gap needs a fix before the main theorem is fully established. read the letter →

arxiv 2608.03439 v1 pith:SPFE7AYD submitted 2026-08-04 cs.DS cs.LGmath.COmath.PR

Cassandra Marcussen , Ronitt Rubinfeld , Madhu Sudan This is my paper · ORCID
classification cs.DScs.LGmath.COmath.PR MSC 68W2068Q2505A05
keywords qualitycontrolproblemspermutationpatternspatterncountingsubsequencequasirandomnessjumblednessexponentiallyrobustsublinear-timealgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper's goal is to show that the quality-control formulation of randomness certification — accept most inputs drawn from the target distribution, reject every input whose statistic deviates far from the random baseline — turns an exponential-hardness problem into a polynomial one. For real-valued sequences, worst-case approximate counting of a length-k permutation pattern requires exp(k) queries, yet the paper proves that checking whether a sequence has random-looking counts of a given pattern needs only $O(k^8 \varepsilon^{-5} \log(k/\varepsilon))$ queries and time, independent of the sequence length $n$. For finite-alphabet sequences, the corresponding certification runs in $\mathrm{poly}(mk/(\varepsilon p_{\min}))$ queries. The two new tools are exponentially robust quasirandomness, which guarantees that a poly(k)-sized random sample preserves the global pattern-count signal, and permutation jumbledness, a coarse-grid uniformity condition on a permutation's point set that is checkable in linear time and certifies all short pattern counts without enumerating them. A sympathetic reader would care because this is the first setting in which the quality-control asymmetry provably erases an exponential worst-case lower bound.

What carries the argument

The upper bound is carried by two objects. Exponentially robust quasirandomness (Definition 3.10) is the query-side engine: a sequence $\sigma$ is $(\alpha,\beta,s_0,\ell)$-exponentially robustly quasirandom with respect to $\tau$ if, for every sample size $s \geq s_0$, all but an $\exp(-\alpha)$ fraction of length-$s$ index subsets have counts of length-$\ell$ subpatterns of $\tau$ within $(1\pm\beta)$ of the i.i.d. expectation. A concentration lemma (Lemma 3.12), proved through a high-probability bounded-differences inequality, shows that such robustness at level $\ell$ forces the length-$(\ell+1)$ count on a random sample to concentrate; chaining this from $\ell=1$ to $\ell=k$ makes a single poly($k$)-sized sample certify the global count. Permutation jumbledness (Definition 3.4) is the time-side engine: viewing a permutation $\sigma$ over $[N]$ as the point set $\{(i,\sigma(i))\}$ in $[N]\times[N]$, tile the square into a coarse grid of boxes of side $m = \Theta(\varepsilon N/k^2)$, and call $\sigma$ $(m,\beta)$-jumbled if every box holds $|I_i||I_j|/N \pm \beta m/\sqrt{N}$ points, the fluctuation expected of a random permutation. Jumbledness is checkable in $O(N)$ time, holds for random permutations with high probability, and Lemma 3.6 shows it forces every length-$\leq k$ pattern count into $(1\pm\varepsilon)$ of its i.i.d. value, because the dominant contribution to any count comes from copies spread over $k$ distinct rows and $k$ distinct columns, whose box counts jumbledness pins down. In the finite-alphabet setting, the role of jumbledness is played by a dynamic program (Lemma 4.6) that computes aggregate counts of all length-$\ell$ subpatterns of $P$ in $O(Nk^2)$ time, avoiding any enumeration.

What would settle it

Run the Figure 3 tester on the all-constant sequence $\sigma(i)=0$ for $i\in[n]$, with any length-$k$ pattern $\tau$, $k\geq 2$, and $\varepsilon<1$. Its normalized count is $Q_{\tau,n}=0$, so soundness requires rejection with probability at least $2/3$. The sample consists of $N$ identical values, and the induced permutation depends entirely on how ties are broken: a rule that assigns random distinct ranks yields a uniformly random permutation, which is jumbled with high probability and hence accepted. Measuring the acceptance probability on this input — or on any tied sequence with $Q_{\tau,n}$ far from 1 — over the algorithm's internal randomness and tie-breaking settles whether the soundness guarantee of Theorem 3.1 holds for all inputs as stated.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 3.1: for every non-atomic distribution $p$ over $\mathbb{R}$, every length-$k$ permutation pattern $\tau$, and every $\varepsilon>0$, the $(D,Q_\tau)$-quality control problem — accept sequences drawn from the product distribution $p^{\otimes n}$, reject any sequence whose normalized pattern count $Q_{\tau,n}$ misses 1 by more than $\varepsilon$ — is solvable in $O(k^8 \varepsilon^{-5} \log(k/\varepsilon))$ queries and time, with no dependence on $n$. The contrast is the paper's own worst-case lower bound (Theorem 5.1): approximating the count of a length-$k$ increasing pattern in an arbitrary sequence requires $\Omega_\varepsilon(k^{k+2}/e^{2k})$ queries. The resolution is the completeness/soundness asymmetry of quality control: the tester may reject a small fraction of genuinely random inputs, so it only has to certify a typical sequence, while still being required to catch every deviant one. The paper claims the same template works for finite alphabets (Theorem 4.2, $\widetilde{O}(k^5/(\varepsilon^2 p_{\min}^2))$ queries for patterns over $[m]$ with minimum symbol probability $p_{\min}$) and that any such quality control algorithm must make superlinear queries in $k$: $\Omega(k^{1.5-\delta})$ for every pattern and $\Omega(k^{2-\delta})$ for the increasing pattern, so the polynomial upper bounds cannot be pushed down to linear.

Load-bearing premise

The soundness proof in Section 3.1.3 assumes every input sequence has all-distinct values so it can be treated as a permutation; sequences with tied values, which the problem definition requires the algorithm to reject when their pattern count is far from the random baseline, are never analyzed, so the guarantee could fail exactly there.

Editorial extensions

If this is right

  • Worst-case approximate counting of a length-$k$ permutation pattern requires $\exp(k)$ queries, yet quality control for the same statistic needs only $O(k^8 \varepsilon^{-5} \log(k/\varepsilon))$ queries and time: the first demonstrated case where the quality-control gap converts an exponential worst-case problem into a polynomial one.
  • The certification cost is independent of the data length $n$; the same poly($k$) budget checks sequences of any length, and the testers are nonadaptive.
  • For finite alphabets the same template gives $\mathrm{poly}(mk/(\varepsilon p_{\min}))$ queries, so Boolean or small-alphabet sequences can be certified for growing pattern length $k$ even though worst-case approximate counting needs $\Omega(\varepsilon m^k)$ queries.
  • Superlinear queries in $k$ are provably necessary ($\Omega(k^{1.5-\delta})$ in general, $\Omega(k^{2-\delta})$ for the increasing pattern), so the upper bound is not tight but cannot be substantially improved.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The tie-gap in the soundness proof suggests a bounded repair: the tester should specify a tie-breaking rule for sampled values (for instance, ordering equal values by index) and prove that every tied input with deviant pattern count maps to a non-jumbled tie-broken permutation; until then, Theorem 3.1 is best read as applying to inputs with distinct values, and quality control for sequences with t
  • Permutation jumbledness is a linear-time-checkable condition that certifies all subpattern counts of length at most $k$, so it is a candidate general-purpose randomness certificate: any statistic that can be shown to be forced by coarse-grid uniformity could be certified on a sample without enumeration, not just pattern counts.
  • The two-stage design — exponentially robust quasirandomness to make a small random sample informative, then an efficiently checkable proxy to read the statistic off the sample — should transfer to other statistics with hypergeometric-type concentration, such as motif counts in other random graph models, where worst-case counting is hard but certification may become polynomial.
  • The lower-bound exponent $2 - (b_{\tau,t}+2)/(2t)$ is controlled by the pattern-specific invariant $b_{\tau,t}$ (the minimum number of nonempty intervals left when a consecutive run of $t$ planted ranks is deleted from $\tau$), which suggests the true query complexity of quality control varies pattern by pattern and could be pinned down exactly by computing this invariant.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. The paper introduces and studies quality-control problems for pattern counting over sequences. For real-valued sequences with a non-atomic reference distribution, it defines the permutation-pattern count quality Q_{τ,n} as the normalized number of subsequences whose relative order matches a fixed permutation pattern τ. For finite alphabets it defines the analogous pattern-count quality R_{P,n}. The main algorithmic claims are that quality control for these statistics is solvable in poly(k) time and queries even though worst-case approximate counting of the same statistics requires exp(k) queries. The proof combines a new notion of permutation jumbledness with an exponentially robust quasirandomness argument: a poly(k)-size random subsequence is shown to preserve the relevant global signal, and jumbledness is used to certify subpattern counts on that subsequence in linear time. The paper also proves superlinear lower bounds on the query complexity of quality control for permutation patterns and patterns, and exp(k) worst-case lower bounds for approximate counting, highlighting the separation between worst-case counting and quality control.

Significance. If the main theorem were fully established, this would be a significant contribution: it is the first demonstration that the quality-control framework can turn a statistic with exponential worst-case query complexity into a polynomial, n-independent certification problem. The notion of permutation jumbledness is a useful strengthening of asymptotic permutation quasirandomness, and the exponentially robust quasirandomness machinery is applied carefully to a new setting. The lower bounds, while not closing the gap to the upper bounds, show that the polynomial dependence on k is not an artifact of the framework. The paper is clearly written and the main upper-bound structure is coherent for permutation inputs with distinct entries.

major comments (1)
  1. [Section 3.1.3, proof of Lemma 3.14; Figure 3, Step 1] The soundness proof is not valid for inputs with tied values. Definition 1.2 requires rejection of every x with |Q_{τ,n}(x)-1|>ε, and Definition 1.3 does not exclude ties; indeed, copies require strict inequalities in both directions, so ties can only lower the pattern count. The proof states, 'since p is non-atomic, the queried values are distinct almost surely ... so we treat the input as a permutation σ throughout.' That sentence justifies completeness for inputs drawn from p^{⊗n} but not soundness over all inputs. The algorithm's instruction to 'replace the sampled values by their relative ranks' is undefined when the sample contains equal values. If ties are broken randomly, consider x=(0,0,...,0): for every non-trivial length-k pattern τ, Q_{τ,n}(x)=0, so soundness requires rejection, yet the induced permutation on the N sampled indices is uniformly random under random tie-breaking, hence (m,β)-jumbled with high probability by Lemma 3.5, and the algorithm accepts with probability 1-o(1). If a deterministic tie-breaking rule is intended, it is not specified, and no argument shows that every tied sequence with Q far from 1 induces a non-jumbled permutation after that tie-breaking. This is a load-bearing gap: the soundness guarantee of Theorem 3.1 is not established for the stated domain of all real-valued sequences.
minor comments (5)
  1. [Section 3.2, proof of Lemma 3.19] The proof assumes that any quality-control algorithm rejects every sequence with at least 2 binom(n,k)/k! copies of τ with probability at least 9/10, whereas Definition 1.2 only requires rejection probability 2/3 for inputs with |Q-1|>ε. The resulting displayed gap of 4/5 is therefore not justified; however, a gap of at least 3/5 still suffices for the argument, so the lower bound survives up to constants.
  2. [Theorem 3.1 and Figure 3] The claimed time bound O(k^8 ε^{-5} log(k/ε)) does not account for the cost of sorting the N sampled values to compute relative ranks in Step 1 of the algorithm; sorting adds a factor of log N. The statement should use eO notation or explicitly include the sorting cost.
  3. [Theorems 3.15 and 3.16] The lower-bound statements do not specify the value of ε for which they hold. The construction forces Q≥2, so the bounds should be stated for all ε<1, or for the fixed ε appearing in the quality-control definition.
  4. [Section 1.1, Definition 1.2 and Remark 1.7] The redefinition of o(1) in runtime statements is nonstandard and deserves an explicit remark connecting it to the completeness condition; as written, the quantification over 'every sequence of parameter settings' could be read as allowing completeness error to depend on the algorithm's runtime parameters.
  5. [Figure 3] The algorithm assumes n≥N but the quality-control definition applies for all n; the paper should state the behavior for n<N, for example rejecting after querying all entries.

Circularity Check

0 steps flagged · score 1.0 of 10

No load-bearing circularity; [MRS25] self-citations are framework-level and the central proofs are self-contained.

full rationale

The derivation chain is not circular. The paper imports the quality-control definition and the exponentially robust quasirandomness label from [MRS25], but Definition 1.2, Definition 3.10, Lemma 3.12, and Lemma 3.8 are all stated and proved inside the paper; the appeal to the proof idea of Claim 3.14 of [MRS25] is only an attribution for an induction that the paper itself performs with its own parameters. Permutation jumbledness (Definition 3.4) is a new quantitative condition whose parameters m and beta are set in the proof of Lemma 3.6 to make the count certification go through, not fitted to data. Soundness does not presuppose the target: Lemma 3.8 shows a global deviation forces a sampled deviation via bounded differences, and Lemma 3.6 shows that a jumbled sample cannot have such a deviation. The lower bounds are independent indistinguishability arguments. One non-circular correctness caveat is that Lemma 3.14's soundness proof says "we treat the input as a permutation sigma throughout" after justifying only completeness via non-atomicity; the soundness domain in Definition 1.3 includes tied sequences, so Lemma 3.14's assumption may be a proof gap, but it is not a reduction of the result to its own inputs.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No new physical or mathematical entities are postulated. Permutation jumbledness is a new property, not an entity; it is defined and analyzed within the paper. The framework, definitions, and all parameters are either standard or set by explicit formulas.

assumptions (4)
  • standard math Standard concentration inequalities: Chernoff, hypergeometric tail, Chebyshev, high-probability bounded differences (Proposition 2.4), matroid concentration of [PP14].
    Used throughout Sections 2, 3, and 4 to bound deviations of pattern counts and jumbledness failures; these are standard results invoked without proof.
  • domain assumption Non-atomic distribution p for permutation patterns and finite alphabet with minimum probability p_min for patterns.
    The problem definitions in Sections 1.1 and 4 assume these. For permutation patterns, non-atomicity ensures distinct values almost surely, which the completeness proof uses; for patterns, p_min governs the query bounds.
  • domain assumption Query access model with random access to sequence entries.
    Definition 1.1; the algorithms and lower bounds are stated in this model.
  • ad hoc to paper The redefined o(1) convention in Definition 1.2 and Remark 1.7.
    The paper defines o(1) as a quantity that approaches 0 whenever the runtime bound approaches infinity, rather than as error decaying with n. This is necessary for the claimed n-independent query bounds but is a nonstandard completeness convention.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quality Control Algorithms for Pattern Counting." pith.science (2026). https://pith.science/paper/SPFE7AYD

@misc{pith2026260803439,
  author       = {Pith},
  title        = {Pith review of: Quality Control Algorithms for Pattern Counting},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SPFE7AYD}},
  note         = {Machine review of arXiv:2608.03439}
}
abstract

In recent work, Marcussen, Rubinfeld, and Sudan introduced the notion of quality control problems, which aim to capture the task of determining if a given input is truly random. Formally, their goal is to accept typical inputs from the specified distribution while rejecting every input whose value of a specified statistic is far from the distributional baseline. This captures the empirical practice of using specified statistics as a proxy for the quality of randomness. Empirical algorithms, however, have not exploited the asymmetry in the definition of quality control problems, which require soundness guarantees in the worst-case while only seeking average-case completeness. Their work abstracted a problem definition emphasizing this asymmetry and used it to give efficient quality control algorithms for assessing the randomness of graphs. In this work, we introduce and study quality control problems over sequences, where the goal is to distinguish a sequence of i.i.d. characters from sequences where some specified pattern appears too often (or too infrequently) as a subsequence. We consider this problem in both the finite-alphabet setting and for real-valued sequences. We refer to the former setting as the pattern counting problem. In the latter case, the natural notion of a pattern is to consider the relative ordering of the characters in the subsequence, and we refer to this as the permutation pattern counting problem. Algorithms to approximately count (permutation) patterns of length $k$ in a worst-case sequence of length $n$ can provably require exponential in $k$ queries into the sequence. In contrast, we show that by taking advantage of the asymmetry in the definition of quality control, we give algorithms that run in poly$(k)$ time to solve these problems. We also prove that any quality control algorithm (over some natural distributions) requires superlinear queries in $k$.

Figures

Figures reproduced from arXiv: 2608.03439 by the authors.

Figure 1
Figure 1. A random permutation σ : [N] → [N] is jumbled (Definition 3.4) with high probability, meaning in a partition of [N] × [N] into m-by-m squares, there are roughly m2/N points (i, σ(i)). Suppose we want to count the occurrences of the length-k increasing pattern. As this figure portrays, look at any sequence of k increasing blocks. Most occurrences of the pattern will occur in these sequences of increasing blocks, and … view at source ↗
Figure 2
Figure 2. Quality control algorithm for verifying whether a permutation pattern [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
Figure 3
Figure 3. Algorithm for quality control of permutation pattern counts in a permutation. Exponen [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: The process of generating a sequence according to the distribution [PITH_FULL_IMAGE:figures/full_fig_p030_4.png]
Figure 5
Figure 5. Figure 5: The process of generating a sequence according to the distribution [PITH_FULL_IMAGE:figures/full_fig_p031_5.png]
Figure 6
Figure 6. Figure 6: This algorithm uses dynamic programming to count the number of occurrences of patterns [PITH_FULL_IMAGE:figures/full_fig_p039_6.png]
Figure 7
Figure 7. Figure 7: Algorithm for quality control of pattern counts in a sequence in [ [PITH_FULL_IMAGE:figures/full_fig_p046_7.png]
Figure 8
Figure 8. Figure 8: Outline of the construction of the instances considered for the worst-case approximation [PITH_FULL_IMAGE:figures/full_fig_p050_8.png]
Figure 9
Figure 9. Figure 9: Construction of sequences (S) with zero copies of P = P1P2P3P4P5P6 and sequences (T) with (1 ± ε) [PITH_FULL_IMAGE:figures/full_fig_p053_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 16 canonical work pages

  1. [1]

    Surveys in combinatorics , volume=

    On the method of bounded differences , author=. Surveys in combinatorics , volume=. 1989 , publisher=

    1989

  2. [2]

    The Electronic Journal of Combinatorics , pages=

    A Permutation Regularity Lemma , author=. The Electronic Journal of Combinatorics , pages=

    work page

  3. [3]

    North-Holland Mathematics Studies , volume=

    Pseudo-random graphs , author=. North-Holland Mathematics Studies , volume=. 1987 , publisher=

    work page 1987

  4. [4]

    CoRR , volume =

    Cassandra Marcussen and Ronitt Rubinfeld and Madhu Sudan , title =. CoRR , volume =. 2025 , url =. doi:10.48550/ARXIV.2508.16531 , eprinttype =. 2508.16531 , timestamp =

    arXiv doi:10.48550/arxiv.2508.16531 2025

  5. [5]

    Approximate Counting of Permutation Patterns , booktitle =

    Omri Ben. Approximate Counting of Permutation Patterns , booktitle =. 2026 , url =. doi:10.1137/1.9781611978971.210 , timestamp =

    doi:10.1137/1.9781611978971.210 2026

  6. [6]

    , journal =

    Crudele, Gabriel and Dukes, Peter and Noel, Jonathan A. , journal =. Six. doi:10.19086/da.122973 , year =

    work page doi:10.19086/da.122973

  7. [7]

    Combinatorica , volume=

    Quasi-random graphs , author=. Combinatorica , volume=. 1989 , publisher=

    work page 1989

  8. [8]

    Geometric and Functional Analysis , volume=

    Quasirandom permutations are characterized by 4-point densities , author=. Geometric and Functional Analysis , volume=. 2013 , publisher=

    work page 2013

Show all 31 references
  1. [9]

    2024 IEEE International Symposium on Information Theory (ISIT) , pages=

    An extension of McDiarmid's inequality , author=. 2024 IEEE International Symposium on Information Theory (ISIT) , pages=. 2024 , organization=

    2024

  2. [10]

    Mathematical Proceedings of the Cambridge Philosophical Society , volume=

    On some series of functions,(1) , author=. Mathematical Proceedings of the Cambridge Philosophical Society , volume=. 1930 , organization=

    1930

  3. [11]

    Bulletin of the American Mathematical Society , volume=

    Extension of range of functions , author=. Bulletin of the American Mathematical Society , volume=. 1934 , publisher=

    1934

  4. [12]

    Combinatorics, Probability and Computing , volume=

    Concentration of Lipschitz functionals of determinantal and other strong Rayleigh measures , author=. Combinatorics, Probability and Computing , volume=. 2014 , publisher=

    2014

  5. [13]

    Breakthroughs in statistics: Foundations and basic theory , pages=

    A class of statistics with asymptotically normal distribution , author=. Breakthroughs in statistics: Foundations and basic theory , pages=. 1992 , publisher=

    1992

  6. [14]

    Journal of Combinatorics , volume=

    On the asymptotic statistics of the number of occurrences of multiple permutation patterns , author=. Journal of Combinatorics , volume=. 2015 , publisher=

    2015

  7. [15]

    Finding small patterns in permutations in linear time , booktitle =

    Sylvain Guillemot and D. Finding small patterns in permutations in linear time , booktitle =. 2014 , url =. doi:10.1137/1.9781611973402.7 , timestamp =

    2014 doi

  8. [16]

    arXiv preprint arXiv:1310.8378 , year=

    Stanley-Wilf limits are typically exponential , author=. arXiv preprint arXiv:1310.8378 , year=

    arXiv

  9. [17]

    Buss and Anna Lubiw , title =

    Prosenjit Bose and Jonathan F. Buss and Anna Lubiw , title =. Inf. Process. Lett. , volume =. 1998 , url =. doi:10.1016/S0020-0190(97)00209-3 , timestamp =

    1998 doi

  10. [18]

    Faster Exponential Algorithm for Permutation Pattern Matching , booktitle =

    Pawel Gawrychowski and Mateusz Rzepecki , editor =. Faster Exponential Algorithm for Permutation Pattern Matching , booktitle =. 2022 , url =. doi:10.1137/1.9781611977066.21 , timestamp =

    2022 doi

  11. [19]

    Finding and Counting Permutations via CSPs , journal =

    Benjamin Aram Berendsohn and L. Finding and Counting Permutations via CSPs , journal =. 2021 , url =. doi:10.1007/S00453-021-00812-Z , timestamp =

    2021 doi

  12. [20]

    Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs , booktitle =

    Bartlomiej Dudek and Pawel Gawrychowski , editor =. Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs , booktitle =. 2020 , url =. doi:10.4230/LIPICS.ISAAC.2020.23 , timestamp =

    2020 doi

  13. [21]

    William Kuszmaul , title =. Math. Comput. , volume =. 2018 , url =. doi:10.1090/MCOM/3216 , timestamp =

    2018 doi

  14. [22]

    Albert and Robert E

    Michael H. Albert and Robert E. L. Aldred and Mike D. Atkinson and Derek A. Holton , editor =. Algorithms for Pattern Involvement in Permutations , booktitle =. 2001 , url =. doi:10.1007/3-540-45678-3\_31 , timestamp =

    2001 doi

  15. [23]

    2008 , url =

    Shlomo Ahal and Yuri Rabinovich , title =. 2008 , url =. doi:10.1137/S0895480104444776 , timestamp =

    2008 doi

  16. [24]

    Long Paths Make Pattern-Counting Hard, and Deep Trees Make It Harder , booktitle =

    V. Long Paths Make Pattern-Counting Hard, and Deep Trees Make It Harder , booktitle =. 2021 , url =. doi:10.4230/LIPICS.IPEC.2021.22 , timestamp =

    2021 doi

  17. [25]

    Journal of Number Theory , volume=

    Quasirandom arithmetic permutations , author=. Journal of Number Theory , volume=. 2005 , publisher=

    2005

  18. [26]

    Journal of Combinatorial Theory, Series B , volume=

    Limits of permutation sequences , author=. Journal of Combinatorial Theory, Series B , volume=. 2013 , publisher=

    2013

  19. [27]

    Journal of Combinatorial Theory, Series B , volume=

    Finitely forcible graphons and permutons , author=. Journal of Combinatorial Theory, Series B , volume=. 2015 , publisher=

    2015

  20. [28]

    Random Structures & Algorithms , volume=

    Characterization of quasirandom permutations by a pattern sum , author=. Random Structures & Algorithms , volume=. 2020 , publisher=

    2020

  21. [29]

    Combinatorics, Probability and Computing , volume=

    Lower bound on the size of a quasirandom forcing set of permutations , author=. Combinatorics, Probability and Computing , volume=. 2022 , publisher=

    2022

  22. [30]

    arXiv preprint arXiv:2407.06869 , year=

    Forcing quasirandomness with 4-point permutations , author=. arXiv preprint arXiv:2407.06869 , year=

    arXiv

  23. [31]

    arXiv preprint arXiv:2601.05166 , year=

    Inapproximability of Counting Permutation Patterns , author=. arXiv preprint arXiv:2601.05166 , year=

    arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.