{"id":"2f259e25-dadf-4680-9382-22294bd7eb12","arxiv_id":"2508.16531","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"Introduces quality control problems and proves that checking whether a graph has the right k-clique count for G_{n,p} takes p^{-Theta(k)} queries, superpolynomially faster than worst-case testing.","lead":"This paper defines a new class of algorithmic problems called quality control: certify that a specific input behaves like a sample from a target distribution with respect to a given statistic, while rejecting adversarial inputs that deviate from it. For random graphs, it proves that certifying the k-clique count is dramatically cheaper than prior worst-case tests, p^{-O(k)} queries versus p^{-Omega(k^2)}.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Concentration Lemma 3.6 has a concrete proof gap: the bounded-difference constants are off by a factor of 2 and the q-bound uses an unstated lower bound on s; this is the load-bearing step for the p^{-O(k)} upper bound.","rationale":"The paper's central claim is the p^{-O(k)} quality-control bound for k-clique counts, and the proof chain runs through Lemma 3.6. The reader identified Lemma 3.6 as the most fragile premise, focusing on parameter alignment and the compressed verification of condition (8). My stress-test finds a more concrete defect: Claim 3.9 is applied as though |S△S'| equals the Hamming distance of the sampled tuples, but for multisets it is at least twice that distance. This invalidates the stated c_i and weakens the concentration exponent by a factor of four. The proof also imports a lower bound on s involving alpha_{k-1} that is not part of Lemma 3.6's assumptions, so the 'verification' of (8) is not actually derived from the lemma's hypotheses. Both issues are located in the exact step that produces the p^{-O(k)} query upper bound. I do not believe they are fatal: choosing c_i = 2ell(1+gamma)E_{s,ell-1} and a slightly larger s_ell should restore the argument, and the asymptotic p^{-O(k)} form would survive. But the proof as written is not complete, so the paper should not be accepted without a corrected concentration lemma. This is consistent with the reader's CONDITIONAL verdict; I partially agree with the reader's weakest-assumption analysis because I identify a specific algebraic error rather than only a parameter-alignment risk. I would keep the verdict CONDITIONAL rather than moving to REJECT, since the gap appears fixable and the rest of the architecture (inductive lemma, jumbledness-based runtime, lower bounds) does not seem to contain an equally severe flaw.","tokens_in":65630,"tokens_out":30684,"duration_ms":300755,"concrete_test":"Independently re-derive Lemma 3.6 from Corollary 2.19 using the corrected c_i = 2ell(1+gamma)E_{s,ell-1} and only the stated assumption exp(-beta s) <= p^{(ell+2 choose 2)}. Then instantiate k=3, ell=2, epsilon=0.1, p=10^{-2} with s = s_2 from Equation (4) and check whether the final probability bound 4^{ell+1}exp(-alpha_ell s) from Lemma 3.7 still holds. If the exponential term degrades to exp(-alpha_ell s / 2), then Lemma 3.7 fails as written and the sample-size schedule must be enlarged (which would preserve p^{-O(k)} only after reproving the parameter alignment in Definition 3.4 and Equation (4)).","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 3.6 is called the technical core of the upper bound for Theorem 3.1. Its proof applies Corollary 2.19 with bounded-difference constants c_i = ell(1+gamma)E_{s,ell-1}. But Claim 3.9 bounds |f_ell(S) - f_ell(S')| by |S△S'| · ell(1+gamma)E_{s,ell-1}, where S,S' are multisets. If the corresponding tuples differ in t positions, |S△S'| is at least 2t (each replaced vertex contributes one old and one new copy), so the per-coordinate Lipschitz constant should be at least 2ell(1+gamma)E_{s,ell-1}, not ell(1+gamma)E_{s,ell-1}. This doubles every c_i, quadrupling sum c_i^2 and weakening the exponential term from exp(-gamma^2 s p^{2ell-2}/2048) to exp(-gamma^2 s p^{2ell-2}/8192). The instantiation in Lemma 3.7 uses the original 2048 constant to absorb this term into 4^{ell+1}exp(-alpha_ell s), since alpha_ell = p^{2ell-2}epsilon^2/(4096 ell^2); with the corrected constant the exponent becomes alpha_ell s / 2, which is not <= alpha_ell s, so the claimed bound does not follow as written.\n\nSeparately, the proof verifies condition (8) by asserting q <= 4^ell exp(-beta s) <= 4^ell exp(-alpha_{k-1} s) and then using 'since s >= 1/alpha_{k-1} ln(...)'. But Lemma 3.6 assumes only exp(-beta s) <= p^{(ell+2 choose 2)} with beta arbitrary; it does not assume s >= 1/alpha_{k-1}..., and beta is not related to alpha_{k-1}. Thus the proof uses an extra condition not present in the lemma statement. For the specific s_ell in Lemma 3.7 the condition can likely be verified directly, but the lemma as stated is not proved. These are correctness gaps in the exact step that yields the p^{-O(k)} query bound; they are likely repairable by setting c_i = 2ell(1+gamma)E_{s,ell-1} and inflating s_ell by a constant, but until repaired Theorem 3.1 Part (1) is not established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a new class of problems called Quality Control problems: given a distribution D and a quality function ρ that is near 1 with high probability on D, accept typical inputs from D and reject adversarially chosen inputs with ρ far from 1. The authors argue that this intermediate objective can be much easier than testing membership in D or approximating ρ on worst-case inputs. As a case study, they consider graph inputs with D=G_{n,p}, N=binom(n,2), and ρ_k the normalized k-clique count. Their central result (Theorem 1.2, formalized as Theorem 3.1) asserts that the (G_{n,p}, ρ_k)-quality control problem is solvable with p^{-O(k)} adjacency-matrix queries and time (when n is at least p^{-Ω(k)}), and that any algorithm requires p^{-Ω(k)} queries. This yields a superpolynomial gap relative to the p^{-Ω(k^2)} worst-case estimation lower bounds. The proof is based on a sampled multiset of vertices, a notion of 'exponentially robust quasirandomness' (ERQ), and an inductive scheme that uses a concentration lemma (Lemma 3.6) built on a recent bounded-difference inequality of Combes. The paper also extends the results to general motifs H, where the exponent becomes O(Δ(H)), and to other random graph models. A separate final section sharpens the triangle case to Θ(1/p) with adjacency-list access.","tokens_in":66182,"tokens_out":58232,"duration_ms":562838,"significance":"If the technical gaps identified below are repaired, this is a substantial contribution. The paper identifies a clean, apparently new problem class, and the main phenomenon — that quality control can be genuinely easier than both distribution testing and worst-case property estimation — is interesting and well illustrated by the clique-counting gap. The composability/filtering observation (running a quality-control algorithm for an unrelated parameter as a preconditioner) is elegant and likely to be reused. The proof framework is ambitious: it combines a high-probability bounded-difference inequality, a local-to-global quasirandomness notion, and efficient counting in jumbled graphs. The supporting material (triangle case, general motifs, other random graph models, Sum-NC0 parameters) strengthens the case that the framework is robust. However, the current manuscript contains load-bearing proof gaps in the concentration lemma and in the general lower-bound construction; these affect the central claims as written, even though they appear repairable with additional constant bookkeeping.","major_comments":[{"comment":"The bounded-difference constant in the McDiarmid application is off by a factor of 2. Claim 3.9 bounds |f_ℓ(S)-f_ℓ(S')| by |S△S'| · ℓ(1+γ)E_{s,ℓ-1}. For two ordered multisets differing in t coordinates, |S△S'| is generally 2t (one old copy removed and one new copy added per changed coordinate). Thus the per-coordinate Lipschitz constant in Corollary 2.19 should be 2ℓ(1+γ)E_{s,ℓ-1}, not ℓ(1+γ)E_{s,ℓ-1}. Doubling c_i quadruples Σc_i^2 and, following the written derivation, changes the final exponent from γ²s p^{2ℓ-2}/(2048ℓ²) to γ²s p^{2ℓ-2}/(8192ℓ²), which is only α_ℓ s/2 and cannot be absorbed into 4^{ℓ+1}exp(-α_ℓ s) in Lemma 3.7. I note that a tighter accounting of E_{s,ℓ}/E_{s,ℓ-1} gives considerably more slack (essentially /512ℓ² instead of /8192ℓ²), so the result is likely repairable, but the proof as written is not correct.","section":"§3.1.1, Claim 3.9 and Lemma 3.6"},{"comment":"The proof of Lemma 3.6 verifies the condition q ≤ min{...} by asserting q ≤ 4^ℓ exp(-βs) ≤ 4^ℓ exp(-α_{k-1}s) and then using 'since s ≥ 1/α_{k-1} ln(...)'. But Lemma 3.6 assumes only exp(-βs) ≤ p^{C(ℓ+2,2)}; it does not assume β ≥ α_{k-1}, nor does it state the lower bound on s. The proof therefore uses an extra condition that is absent from the lemma statement. The instantiated use in Lemma 3.7 may satisfy the additional condition, but the lemma as stated is not proved. The lemma should either be strengthened with the needed hypotheses or the proof should be reorganized so that the verification is done directly from the stated assumption.","section":"§3.1.1, verification of condition (8)"},{"comment":"The statement of Lemma 4.11 requires ℓ ≥ 2^{2C(k,2)+1} n p^{Δ/2}, but the proof derives E[C_H(G')] ≥ μ_H ℓ / (2^{C(k,2)+2} n p^Δ) and concludes that ℓ ≥ 2^{C(k,2)+3} p^Δ n suffices for ρ_H(G') ≥ 1.9. These thresholds differ by p^{Δ/2}. As written, the proof establishes separation only for ℓ ≈ n p^Δ, yielding a p^{-Δ} lower bound, whereas Theorem 4.8 and the proof of Theorem 4.1(3) use ℓ ≈ n p^{Δ/2}. For motifs such as stars, the dense-region construction with ℓ = n p^{Δ/2} does not appear to increase the induced motif count by the needed constant factor, so the claimed p^{-Δ/2} lower bound is not supported by the argument. This needs to be reconciled: either the lemma should state ℓ ≥ n p^Δ, or the proof must account for additional contributions (e.g., copies of H entirely inside the planted region) that justify the p^{Δ/2} threshold.","section":"§4.2, Lemma 4.11"}],"minor_comments":[{"comment":"The prose says G' is 'equal to G on S×S and equal to T otherwise', while the display formula says the opposite: pairs with both endpoints outside S use G, and pairs with at least one endpoint in S use T. The formula is the one used in the indistinguishability proof, so the prose should be corrected.","section":"Definition 4.9"},{"comment":"The displayed statement of Lemma 3.6 gives the second exponential term as exp(-γ² s p^{2ℓ-2}/2048), while the proof concludes with exp(-γ² s p^{2ℓ-2}/(2048·ℓ²)). The missing ℓ² in the statement is confusing and should be fixed, since Lemma 3.7 relies on the version with ℓ².","section":"Lemma 3.6 statement vs proof"},{"comment":"The lower-bound theorem is stated for all p ≥ ω(n^{-2/(k-1)}), but the proof in Section 4.2 requires n ≥ p^{-Ω(k)} (e.g., n₀(x)=x^{2Δ} in Theorem 4.8). The statement should include the same n ≥ p^{-c k} condition used elsewhere, or the proof should be modified to cover the stated range.","section":"Theorem 3.15"},{"comment":"Theorem 1.3 is stated in the introduction but no proof or proof sketch is provided for the global polynomial-time algorithm. It should either be proved explicitly or derived from Section 3.3/Proposition 2.8.","section":"Theorem 1.3"}],"recommendation":"major_revision","confidential_remarks":"The paper's central idea is strong and likely of interest to the intended audience, but the current version has two load-bearing proof gaps: the factor-of-2 issue in the concentration lemma and the mismatch in the lower-bound construction between the statement and the proof. Both appear fixable with careful constant reworking, so I would not reject. I would ask the authors to repair these points and to add a short proof of Theorem 1.3 before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The quality-control formulation is genuinely new, and the exponent separation is the real news: for k-clique counts in G_{n,p}, p^{-O(k)} versus p^{-Omega(k^2)} for worst-case estimation is a crisp statement, and the generalization to p^{-Theta(Delta(H))} for general motifs is natural. The high-level architecture--inductive quasirandomness, planted-region indistinguishability lower bounds, and composition of QC filters--is well thought out, and the lower-bound footprint looks reasonable.\n\nBut the stress-test note lands. The load-bearing Concentration Lemma 3.6 has a proof gap. Claim 3.9 bounds |f_l(S)-f_l(S')| by |S Delta S'| * l(1+gamma)E_{s,l-1}. When two multisets differ in t coordinates, the symmetric difference has size 2t, so the per-coordinate Lipschitz constant should be 2l(1+gamma)E_{s,l-1}, not l(1+gamma)E_{s,l-1}. The proof sets c_i to the smaller value, which doubles the bounded difference and quadruples sum c_i^2, weakening the exponential term from exp(-gamma^2 s p^{2l-2}/2048) to roughly exp(-gamma^2 s p^{2l-2}/8192). That breaks the instantiation in Lemma 3.7, where the current constants need the original 2048 to absorb the term into exp(-alpha_l s). With the corrected constant the exponent is alpha_l s/2, which is not <= alpha_l s. The second issue--the q-bound verification uses s >= 1/alpha_{k-1} ln(...), a condition not stated in Lemma 3.6--is also real. Both look repairable: double the c_i and inflate s_l by a constant, or state the extra lower bound on s explicitly. But until that repair is written down, Theorem 3.1(1) is not proved as written.\n\nThe other soft spots are proportionate. The lower-bound section has some statement/proof inconsistencies (Definition 4.9, Lemma 4.11, Theorem 3.16 soundness wording), but they read as drafting issues rather than fatal flaws. The literature review is fair; the paper leans heavily on external results [Com24, CFZ14, ERS20a] and says so clearly, and the self-citations in that context do not bother me.\n\nWho this is for: anyone working on sublinear algorithms, property testing, or average-case complexity. The conceptual contribution is worth engaging with even before the proof is patched, because the QC class is a good framing and the separation is the kind of thing that will be cited once fixed.\n\nRecommendation: send it out for peer review. The gaps are concrete, checkable, and likely repairable; the referee should be told to focus on Lemma 3.6 first.","headline":"New problem class with a sharp-looking p^{-O(k)} vs p^{-Omega(k^2)} separation, but the load-bearing Concentration Lemma 3.6 has a concrete factor-of-two gap that currently blocks Theorem 3.1.","tokens_in":66849,"tokens_out":3396,"would_cite":true,"duration_ms":36965,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"A new 'quality control' framework accepts graphs whose k-clique count matches G_{n,p} using p^{-O(k)} adjacency-matrix queries, sharply beating the p^{-Ω(k^2)} worst-case cost of approximating the count.","keywords":["quality control","sublinear algorithms","random graphs","clique counting","motif counting","exponentially robust quasirandomness","graph jumbledness","property testing"],"falsifier":"Recompute the step in the proof of Lemma 3.6 where exp(-α_{ℓ-1}s_ℓ) ≤ p^{(ℓ+2 choose 2)} is asserted 'for large enough n, and by definition of s', together with the three q-bounds required by Corollary 2.19: q ≤ min{δ/(2 max f), δ/(4Ef), 1/2}. A numerical counterexample at the threshold n≈p^{-c2 k} would break the concentration lemma and with it the p^{-O(k)} query and time bounds.","tokens_in":65441,"feed_emoji":"🔍","tokens_out":9067,"duration_ms":92921,"temperature":0.7,"pith_summary":"This paper identifies a new class of algorithmic problems it calls quality control: given a distribution D and a quality function ρ that is near 1 on most D-samples, accept inputs drawn from D and reject adversarially designed inputs with ρ far from 1, using sublinear queries to a single input. As its central case study, it asks whether a graph's k-clique count matches what G_{n,p} would predict, and answers that one random sample of about p^{-O(k)} vertices settles the question in both queries and time, provided n is at least p^{-ck}. That is sharply faster than the p^{-Ω(k^2)} cost of approximating k-clique counts on worst-case graphs, so the weakened goal — certify the conclusion rather than test the distribution — buys real efficiency. The same technique extends to any fixed motif H with exponent Δ(H), to triangles with matching Θ(1/p) bounds, and to other random graph models with concentrated small-subgraph counts. If the main theorem is right, average-case-style algorithms can be guarded by fast per-instance filters that reject inputs whose relevant statistic deviates from the model.","feed_headline":"Clique checks cost p^{-O(k)} queries, not p^{-Ω(k^2)}","feed_subtitle":"New quality-control framework certifies that a graph matches G_{n,p}'s clique count by sampling a tiny vertex multiset.","key_machinery":"The load-bearing object is 'exponentially robust quasirandomness': a graph is (ε, α, s0)-exponentially robustly quasirandom for ℓ-cliques if, for every sample size s≥s0, a random s-vertex multiset has ℓ-clique count within (1±ε) of the G_{n,p} expectation except with probability at most 4^{ℓ+1} e^{-αs}. The algorithm samples s≈p^{-O(k)} vertices once and counts ℓ-cliques for ℓ=1..k. A concentration lemma, proved with a strengthened bounded-difference concentration inequality whose difference constants need hold only on a high-probability 'good' event, shows the sampled count reveals the global ℓ-clique count whenever (ℓ−1)-clique counts are themselves concentrated in samples; an inductive le","core_discovery":"The paper's central claim is Theorem 3.1: for every constant k, there are constants c1,c2,c3 such that the (G_{n,p}, ρ_k)-quality control problem — accept graphs whose k-clique count is within a constant factor of expectation, reject graphs whose normalized count is far — is solvable in O(p^{-c1 k}) adjacency-matrix queries and time when n≥p^{-c2 k}, and no algorithm using o(p^{-c2 k}) queries can solve it. This contrasts with the p^{-Ω(k^2)} worst-case query complexity of approximating the k-clique count itself. The paper extends the p^{-O(Δ(H))} query/time bound to counting any fixed induced motif H, proves tight Θ(1/p) bounds for triangles with adjacency-list access, and generalizes the q","pith_inferences":["Inference: the framework suggests a general design principle — wrap any average-case algorithm in a quality-control gate whose cost is set by the concentration of the statistic being checked, not by worst-case complexity; this could apply to planted-structure detection whenever the planted region changes a concentrated statistic.","Inference: the linear-versus-quadratic gap in the exponent comes from testing a normalized count against its expectation rather than approximating it; the same machinery might transfer to parameters like chromatic number or diameter only if they admit an analogous density-increment recursion, which the paper leaves open.","Inference: the runtime transfer to non-G_{n,p} models stalls because jumbledness testing is tailored to Erdős–Rényi subgraphs; an efficiently verifiable pseudorandomness notion adapted to stochastic block models or random regular graphs would likely give the same p^{-O(Δ(H))} runtime there — a testable extension.","Inference: accepted graphs inherit exponentially robust quasirandomness, so the single stored multiset could plausibly serve as a near-uniform k-clique sampler; the concentration estimates here are exactly what such a sampler would need, and the paper flags sampling as an open direction."],"forward_implications":["For constant k, a graph can be certified to have a G_{n,p}-like k-clique count in p^{-O(k)} adjacency-matrix queries and time whenever n≥p^{-ck}; the same input would cost p^{-Ω(k^2)} queries under worst-case approximation requirements.","For any fixed motif H, quality control costs p^{-O(Δ(H))} queries and time and requires p^{-Ω(Δ(H))} queries, so the exponent in 1/p is the maximum degree of the motif rather than its number of vertices or edges.","For triangle counts with adjacency-list and degree access, the complexity is Θ̃(1/p), a quadratic improvement over the p^{-3} worst-case triangle-approximation bound.","Quality-control filters compose: running cheap filters for arboricity, edge count, or jumbledness before the motif check preserves completeness and soundness, which is what brings the runtime down to p^{-O(k)} instead of p^{-O(k^2)}.","The query bounds extend to any random-graph distribution with concentrated small-motif counts, giving p^{-O(k)} query complexity for stochastic block models and random regular graphs as well."],"supporting_citations":[{"why":"Supplies the strengthened bounded-difference concentration inequality used to prove the concentration lemma that carries the p^{-O(k)} query bound.","marker":"[Com24]"},{"why":"Defines graph jumbledness, the efficiently verifiable pseudorandomness property used to speed up counting on the sampled subgraph.","marker":"[Tho87]"},{"why":"Provides the fast approximate subgraph-counting algorithm for jumbled graphs used to convert the query-efficient algorithm into a time-efficient one.","marker":"[CFZ14]"},{"why":"Gives the worst-case sublinear k-clique and low-arboricity counting algorithms whose p^{-Ω(k^2)} complexity is the baseline the quality-control result is compared against, and is also used in the triangle upper bound.","marker":"[ERS20a]"},{"why":"Establishes the worst-case lower bound for estimating k-clique counts near the G_{n,p} expectation, the contrast that makes the superpolynomial speedup meaningful.","marker":"[ERS20b]"},{"why":"Supplies the sublinear arboricity estimation routine used as a filter in the triangle quality-control algorithm.","marker":"[EMR22]"},{"why":"Used to reject graphs with too few or too many edges in the triangle-counting algorithm via average-degree estimation.","marker":"[Fei06]"},{"why":"Provides the high-probability bound on the arboricity of G_{n,p} used in the completeness proof for the triangle algorithm.","marker":"[GPS18]"},{"why":"Authority for concentration of subgraph counts in Erdős–Rényi graphs, the distributional fact on which completeness rests.","marker":"[Jan90, JOR04]"}],"fun_headline_variants":["Quality control beats testing: clique count in p^{-O(k)} queries","Clique QC on G(n,p): p^{-O(k)} queries, not p^{-Ω(k^2)}","Sublinear QC: verify clique count in p^{-O(k)} queries","Random graph trust: p^{-O(k)} clique quality check","QC reduces clique test cost to p^{-O(k)} queries"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The upper bound rests on the concentration lemma: once all smaller clique counts concentrate on random samples, the k-clique count in one random multiset of s≈p^{-O(k)} vertices concentrates tightly around its global value; the lemma's sample-size schedule must satisfy three error bounds simultaneously, and if those parameters fail to align, the p^{-O(k)} query and time claims collapse.","fun_headline_variants_meta":{"raw":{"variants":["Quality control beats testing: clique count in p^{-O(k)} queries","Clique QC on G(n,p): p^{-O(k)} queries, not p^{-Ω(k^2)}","Sublinear QC: verify clique count in p^{-O(k)} queries","Random graph trust: p^{-O(k)} clique quality check","QC reduces clique test cost to p^{-O(k)} queries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000696,"raw_usage":{"total_tokens":3133,"prompt_tokens":1041,"completion_tokens":2092,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":785,"completion_tokens_details":{"reasoning_tokens":2001}},"tokens_in":785,"tokens_out":2092,"duration_ms":21692,"temperature":1.0,"reasoning_tokens":2001,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T17:19:02.207679+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute the step in the proof of Lemma 3.6 where exp(-α_{ℓ-1}s_ℓ) ≤ p^{(ℓ+2 choose 2)} is asserted 'for large enough n, and by definition of s', together with the three q-bounds required by Corollary 2.19: q ≤ min{δ/(2 max f), δ/(4Ef), 1/2}. A numerical counterexample at the threshold n≈p^{-c2 k} would break the concentration lemma and with it the p^{-O(k)} query and time bounds.","supporting_citations":[],"review_version":1}