{"id":"043b2963-aab6-4ee3-b81d-eb62aea1badd","arxiv_id":"2608.03439","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Quality-control versions of pattern counting in sequences can be solved in poly(k) time despite worst-case approximate counting requiring exp(k) queries.","lead":"This paper gives fast algorithms that check whether a long sequence of numbers looks random by counting how often small patterns appear. It shows these algorithms can run in polynomial time even though approximating such counts on arbitrary sequences provably needs exponential time.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Soundness fails for tied inputs: Lemma 3.14 assumes a permutation, but the all-equal sequence has Q=0 and random tie-breaking would make the sampled permutation jumbled and accepted.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing concern: the soundness proof in Section 3.1.3 assumes distinct entries and does not handle tied values. My analysis confirms this is not a minor technicality. The definition of quality control demands rejection of every input with |Q_{τ,n}-1|>ε, and the all-equal sequence is a legal input with Q_{τ,n}=0. Since the algorithm's relative-rank step is unspecified under ties, the theorem as stated is unproven. I also checked the possibility that the quantile-function extension of the lower bound to all non-atomic distributions is flawed; for continuous CDFs the quantile function is strictly increasing, so that concern does not land. The jumbledness counting proof in Lemma 3.6 appears internally consistent once one accounts for the forced pattern-matching within selected boxes, and the bounded-difference argument in Lemma 3.12 is plausible with the stated constants. Thus the dominant issue remains the tied-values soundness gap. Because the gap is addressable by defining tie-breaking and proving that all tied far-from-random sequences are rejected, the appropriate verdict is unchanged: CONDITIONAL rather than outright REJECT.","tokens_in":48772,"tokens_out":31639,"duration_ms":306141,"concrete_test":"Run the Algorithm Permutation-Pattern-Count on the constant sequence x=(0,0,...,0), with N=C k^8/ε^5 log(k/ε) as in Theorem 3.1, using random tie-breaking to assign relative ranks to the N sampled values. If Jumbled-Count accepts with probability at least 2/3 (which Lemma 3.5 predicts for a uniformly random permutation), the claimed soundness condition fails because Q_{τ,n}(x)=0. Alternatively, test any proposed deterministic tie-breaking rule on the same input and on sequences with a single block of tied values; if the induced permutation is ever jumbled, the soundness proof is incomplete.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The soundness proof of the main permutation-pattern upper bound (Section 3.1.3, proof of Lemma 3.14) begins: \"since p is non-atomic, the queried values are distinct almost surely... so we treat the input as a permutation σ throughout.\" This only justifies completeness for inputs drawn from p^⊗n. Soundness, however, is quantified over every x with |Q_{τ,n}(x)-1|>ε, and the input domain includes sequences with tied values. Definition 1.3 requires strict inequalities, so ties can drastically lower Q_{τ,n}. The algorithm's Step 1 (\"replace the sampled values by their relative ranks\") is undefined when the sample contains equal values. If ties are broken randomly, consider the constant sequence x=(0,0,...,0): Q_{τ,n}(x)=0 for every non-trivial τ, so soundness requires rejection. But the N sampled values are all equal, and random tie-breaking produces a uniformly random permutation of size N. Lemma 3.5 shows a random permutation is (m,β)-jumbled with high probability, so Jumbled-Count accepts with probability 1-o(1). This directly violates the soundness guarantee. 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. The proof gap is load-bearing: the poly(k) upper bound of Theorem 3.1 is not established for the full soundness requirement.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":49094,"tokens_out":15359,"duration_ms":145572,"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":[{"comment":"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.","section":"Section 3.1.3, proof of Lemma 3.14; Figure 3, Step 1"}],"minor_comments":[{"comment":"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.","section":"Section 3.2, proof of Lemma 3.19"},{"comment":"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.","section":"Theorem 3.1 and Figure 3"},{"comment":"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.","section":"Theorems 3.15 and 3.16"},{"comment":"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.","section":"Section 1.1, Definition 1.2 and Remark 1.7"},{"comment":"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.","section":"Figure 3"}],"recommendation":"major_revision","confidential_remarks":"The soundness gap for tied inputs is real and load-bearing, but it is local: either the input domain must be explicitly restricted to sequences with distinct entries, or the ranking step must be defined on ties and accompanied by a soundness argument for tied inputs. The rest of the analysis appears coherent and substantial. I recommend major revision rather than rejection, since the gap seems repairable within the scope of the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this one. First, the core idea is good: the authors show that quality control for permutation pattern counts can be done in poly(k) queries and time, despite exp(k) worst-case lower bounds for approximate counting. The new permutation jumbledness notion is a genuine contribution, not just a relabeling of prior quasirandomness, and the exponentially robust quasirandomness argument for sequences is built carefully from scratch. For inputs with distinct values, the upper-bound argument holds together: random permutations are jumbled, jumbledness certifies subpattern counts, and a poly(k) sample preserves the global signal. The lower bounds also look solid, with the planted-block construction giving the claimed superlinear query bounds.\n\nSecond, there is a real gap in the soundness proof, and it is exactly where the stress-test note points. Soundness in Definition 1.2 is quantified over every sequence, including those with tied values. The proof of Lemma 3.14 says “since p is non-atomic, the queried values are distinct almost surely ... so we treat the input as a permutation.” That argument covers completeness, but not soundness. The algorithm’s “replace the sampled values by their relative ranks” is undefined under ties, and no tie-breaking rule is specified. The all-equal sequence is a concrete counterexample to the algorithm as written: Q=0, but random tie-breaking makes the sample a uniformly random permutation, which is jumbled and accepted. Rejecting on any observed tie would fix that extreme case, and I suspect the general tie case is also patchable: ties can only lower Q, and making Q far below 1 requires a constant fraction of tied positions, which a poly(k) sample would hit with overwhelming probability. But that argument is not in the paper, and the current proof simply does not apply to the full soundness requirement.\n\nThis is a load-bearing flaw in the write-up, but it is a fixable one. The central machinery is sound for the distinct-value case, and the tie issue seems like an oversight rather than a fundamental obstruction. The paper deserves a serious referee: the contribution is significant, the lower bounds are interesting, and the jumbledness definition will likely be useful beyond this paper. My recommendation is to send it to peer review, with a request that the authors address tied inputs in the soundness proof. If that is done, this becomes a strong paper.","headline":"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.","tokens_in":49577,"tokens_out":14474,"would_cite":false,"duration_ms":126477,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","68Q25","05A05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["quality control problems","permutation patterns","pattern counting","subsequence patterns","quasirandomness","permutation jumbledness","exponentially robust quasirandomness","sublinear-time algorithms"],"falsifier":"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.","tokens_in":48583,"feed_emoji":"🎲","tokens_out":23156,"duration_ms":175624,"temperature":0.7,"pith_summary":"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.","feed_headline":"Cut pattern-count checks from exponential to polynomial queries","feed_subtitle":"Quality control accepts typical inputs and rejects non-random ones, so worst-case exponential bounds no longer apply.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It defines the quality-control problem with worst-case soundness and average-case completeness, and it supplies the exponentially robust quasirandomness idea that the query-side argument adapts from graphs to sequences.","marker":"[MRS25]"},{"why":"It introduces graph jumbledness, the quantitative uniformity notion transplanted here to permutations at the multiplicative-error scale needed for polynomial-size samples.","marker":"[Tho87]"},{"why":"It supplies the permutation quasirandomness notion that the jumbledness definition strengthens from an asymptotic to a polynomial-sample scale.","marker":"[Coo05]"},{"why":"Its high-probability bounded-differences inequality is adapted as the subset-analogue inequality (Proposition 2.4) used in the concentration lemma behind exponentially robust quasirandomness.","marker":"[Com24]"},{"why":"Its concentration inequality for Lipschitz functions over balanced matroids is used to prove the subset bounded-differences inequality on which the sampling lemmas rest.","marker":"[PP14]"},{"why":"It shows that even detecting a single permutation pattern occurrence is NP-hard, motivating why the tester must certify counts via jumbledness rather than by enumeration.","marker":"[BBL98]"}],"fun_headline_variants":["Pattern counting: exponential worst-case bounds bypassed","Quality control makes pattern counting polynomial","Asymmetric testing yields fast pattern checks","Pattern tests: worst-case soundness, average-case speed","Polynomial pattern counting via asymmetry in quality control"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Pattern counting: exponential worst-case bounds bypassed","Quality control makes pattern counting polynomial","Asymmetric testing yields fast pattern checks","Pattern tests: worst-case soundness, average-case speed","Polynomial pattern counting via asymmetry in quality control"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000303,"raw_usage":{"total_tokens":1864,"prompt_tokens":1188,"completion_tokens":676,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":804,"completion_tokens_details":{"reasoning_tokens":608}},"tokens_in":804,"tokens_out":676,"duration_ms":6622,"temperature":1.0,"reasoning_tokens":608,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:53:16.819496+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}