pith. sign in

arxiv: 2601.05166 · v2 · submitted 2026-01-08 · 💻 cs.DS

Inapproximability of Counting Permutation Patterns

Michal Opler This is my paper

Pith reviewed 2026-05-16 15:57 UTC · model grok-4.3

classification 💻 cs.DS
keywords permutation patternscountinginapproximabilityExponential Time Hypothesisfine-grained complexityapproximation algorithmspattern detection
0
0 comments X

The pith

Under ETH, approximating the count of a length-k permutation pattern requires the same runtime as exact counting.

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

The paper shows that approximation does not make counting copies of a fixed length-k permutation pattern in an n-permutation any easier than exact counting, under the Exponential Time Hypothesis. It proves that no algorithm running in time f(k) times n to a power o(k over log k) can return a value within multiplicative factor n to the power (1/2 minus epsilon) times k of the true count. This matches the existing conditional lower bound for exact counting and refutes the conjecture that approximation would allow asymptotically faster algorithms. The bound is nearly tight because an n to the power k/2 approximation is already achievable via the known pattern-detection algorithm that runs in 2 to the O(k squared) times n time. The result implies that the fine-grained hardness barrier for these problems survives the move from exact to approximate solutions.

Core claim

Assuming the Exponential Time Hypothesis, for every ε > 0 there is no algorithm that approximates the number of occurrences of any length-k pattern in an n-permutation to within a multiplicative factor of n^{(1/2 - ε)k} and runs in time f(k) · n^{o(k / log k)}.

What carries the argument

The fine-grained reduction from exact pattern counting to approximate pattern counting that preserves the subexponential dependence on k in the exponent of n.

Load-bearing premise

The Exponential Time Hypothesis holds.

What would settle it

An algorithm that approximates the number of k-pattern copies to within multiplicative factor n^{(1/2 - ε)k} in time f(k) · n^{o(k / log k)} for some ε > 0 and infinitely many k, which would yield a subexponential-time exact counter and refute ETH.

read the original abstract

Detecting and counting copies of permutation patterns are fundamental algorithmic problems, with applications in the analysis of rankings, nonparametric statistics, and property testing tasks such as independence and quasirandomness testing. From an algorithmic perspective, there is a sharp difference in complexity between detecting and counting the copies of a given length-$k$ pattern in a length-$n$ permutation. The former admits a $2^{\mathcal{O}(k^2)} \cdot n$ time algorithm (Guillemot and Marx, 2014) while the latter cannot be solved in time $f(k)\cdot n^{o(k/\log k)}$ unless the Exponential Time Hypothesis (ETH) fails (Berendsohn, Kozma, and Marx, 2021). In fact already for patterns of length 4, exact counting is unlikely to admit near-linear time algorithms under standard fine-grained complexity assumptions (Dudek and Gawrychowski, 2020). Recently, Ben-Eliezer, Mitrovi\'c and Sristava (2026) showed that for patterns of length up to 5, a $(1+\varepsilon)$-approximation of the pattern count can be computed in near-linear time, yielding a separation between exact and approximate counting for small patterns, and conjectured that approximate counting is asymptotically easier than exact counting in general. We strongly refute their conjecture by showing that, under ETH, no algorithm running in time $f(k)\cdot n^{o(k/\log k)}$ can approximate the number of copies of a length-$k$ pattern within a multiplicative factor $n^{(1/2-\varepsilon)k}$. The lower bound on runtime matches the conditional lower bound for exact pattern counting, and the obtained bound on the multiplicative error factor is essentially tight, as an $n^{k/2}$-approximation can be computed in $2^{\mathcal{O}(k^2)}\cdot n$ time using an algorithm for pattern detection.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper proves an ETH-based inapproximability result for counting copies of a length-k permutation pattern in an n-permutation: no f(k)·n^{o(k/log k)}-time algorithm can achieve a multiplicative approximation factor of n^{(1/2-ε)k} for any ε>0. The bound matches the known conditional lower bound for exact counting (Berendsohn-Kozma-Marx) and is shown to be tight because an n^{k/2}-approximation is achievable in 2^{O(k^2)}·n time via the Guillemot-Marx detection algorithm. The proof uses a gap-producing reduction that refutes the conjecture of Ben-Eliezer-Mitrović-Srivastava that approximate counting is asymptotically easier than exact counting.

Significance. If the reduction holds, the result is significant for fine-grained complexity: it demonstrates that approximation does not yield asymptotic improvements for permutation pattern counting under ETH, with the runtime lower bound identical to exact counting and the approximation factor essentially tight against the detection upper bound. The work strengthens the separation between detection and counting, with direct implications for applications in ranking analysis, nonparametric statistics, and property testing. Strengths include the direct reduction from a known hard problem and the parameter-free form of the bounds.

minor comments (2)
  1. [Abstract and §1] In the abstract and introduction, confirm the precise citation details and year for Ben-Eliezer, Mitrović and Srivastava (listed as 2026); ensure consistency with the reference list.
  2. [Proof of main theorem] The reduction overview in the proof sketch should explicitly state how the gap-producing construction avoids introducing extra polynomial factors in n that could weaken the n^{(1/2-ε)k} bound.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and the recommendation to accept. The provided summary accurately captures the main result: an ETH-based inapproximability bound for approximating k-permutation pattern counts that matches the exact-counting lower bound of Berendsohn-Kozma-Marx while remaining tight against the Guillemot-Marx detection algorithm.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation is a standard ETH-based reduction from the exact counting hardness of Berendsohn-Kozma-Marx (2021) to multiplicative approximation hardness. The n^{(1/2-ε)k} gap factor is produced by an explicit gap construction that aligns with the independent n^{k/2} upper bound from the Guillemot-Marx detection algorithm. No step reduces by definition to its own inputs, no fitted parameter is relabeled as a prediction, and no load-bearing claim rests on self-citation chains. The result is externally falsifiable via the ETH assumption and prior independent hardness results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the ETH assumption together with standard reduction techniques from the literature on exact pattern counting.

axioms (1)
  • domain assumption Exponential Time Hypothesis (ETH)
    Standard assumption in fine-grained complexity invoked to derive the conditional runtime lower bound.

pith-pipeline@v0.9.0 · 5649 in / 1120 out tokens · 50643 ms · 2026-05-16T15:57:26.210405+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages · 1 internal anchor

  1. [1]

    Albert, Robert E

    [AAAH01] Michael H. Albert, Robert E. L. Aldred, Mike D. Atkinson, and Derek A. Holton. Algorithms for pattern involvement in permutations. InAlgorithms and Computation, 12th International Symposium, ISAAC 2001, Christchurch, New Zealand, December 19-21, 2001, Proceedings, pages 355–366, 2001.doi:10.1007/3-540-45678-3\_31. [AR08] Shlomo Ahal and Yuri Rabi...

    work page doi:10.1007/3-540-45678-3 2001

  2. [2]

    11 [Ber19] Benjamin Aram Berendsohn

    doi:10.1137/1.9781611978971.210. 11 [Ber19] Benjamin Aram Berendsohn. Complexity of permutation pattern matching. Master’s thesis, Freie Universit¨ at Berlin, Fachbereich Mathematik und Infor- matik,

    work page doi:10.1137/1.9781611978971.210

  3. [3]

    [BKMN16] Karl Bringmann, L´ aszl´ o Kozma, Shay Moran, and N

    doi:10.1007/S00453-021-00812-Z . [BKMN16] Karl Bringmann, L´ aszl´ o Kozma, Shay Moran, and N. S. Narayanaswamy. Hitting set for hypergraphs of low VC-dimension. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 ofLIPIcs, pages 23:1–23:18. Schloss ...

    work page doi:10.1007/s00453-021-00812-z 2016

  4. [4]

    Counting permutation patterns with multidimensional trees

    [BL25] Gal Beniamini and Nir Lavee. Counting permutation patterns with multidimensional trees. In52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, Aarhus, Denmark, July 8-11, 2025, pages 24:1–24:18,

    work page 2025

  5. [5]

    doi:10.4230/LIPIcs.ICALP. 2025.24. [CFK+15] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer,

    work page doi:10.4230/lipics.icalp 2025

  6. [6]

    Stanley-Wilf limits are typically exponential

    doi:10.1007/978-3-319-21275-3. [CP10] Timothy M. Chan and Mihai P˘ atra¸ scu. Counting inversions, offline orthogonal range counting, and related problems. InProceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 161–173, 2010.doi:10.1137/1.9781611973075.15. [DG20] Bartlo...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/978-3-319-21275-3 2010

  7. [7]

    [JK17] V´ ıt Jel´ ınek and Jan Kyncl

    doi:10.1137/1.9781611973402.7. [JK17] V´ ıt Jel´ ınek and Jan Kyncl. Hardness of permutation pattern matching. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 378–396,

    work page doi:10.1137/1.9781611973402.7 2017

  8. [8]

    A Geometric Heuristic for Rectilinear Crossing Minimization

    doi:10.1137/1. 9781611974782.24. [JOP21a] V´ ıt Jel´ ınek, Michal Opler, and Jakub Pek´ arek. Griddings of permutations and hardness of pattern matching. In46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, Tallinn, Estonia, August 23-27, 2021, pages 65:1–65:22, 2021.doi:10.4230/LIPIcs.MFCS.2021.65. 12 [JOP21b] V´ ıt ...

    work page doi:10.1137/1 2021

  9. [9]

    [JX23] Ce Jin and Yinzhan Xu

    doi:10.4230/LIPIcs.IPEC.2021.22. [JX23] Ce Jin and Yinzhan Xu. Removing additive structure in 3SUM-based reductions. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 405–418,

    work page doi:10.4230/lipics.ipec.2021.22 2021

  10. [10]

    [Mar10] D´ aniel Marx

    doi:10.1145/3564246.3585157. [Mar10] D´ aniel Marx. Can you beat treewidth?Theory Comput., 6(1):85–112,

    work page doi:10.1145/3564246.3585157

  11. [11]

    [MT04] Adam Marcus and G´ abor Tardos

    doi:10.4086/ TOC.2010.V006A005. [MT04] Adam Marcus and G´ abor Tardos. Excluded permutation matrices and the Stanley–Wilf conjecture.Journal of Combinatorial Theory, Series A, 107(1):153–160,

    work page 2010

  12. [12]

    1016/J.JCTA.2004.04.002

    doi:10. 1016/J.JCTA.2004.04.002. [Opl22] Michal Opler.Structural and Algorithmic Properties of Permutation Classes. PhD thesis, Charles University, 2022.doi:20.500.11956/179844. 13

    work page 2004