REVIEW 3 major objections 4 minor 1 cited by
Quality control in sublinear time: a case study via random graphs
T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. 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 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
What would settle it
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.
Extended reading notes
Core claim
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
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [§3.1.1, Claim 3.9 and Lemma 3.6] 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.
- [§3.1.1, verification of condition (8)] 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.
- [§4.2, Lemma 4.11] 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.
minor comments (4)
- [Definition 4.9] 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.
- [Lemma 3.6 statement vs proof] 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 ℓ².
- [Theorem 3.15] 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.
- [Theorem 1.3] 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.
Circularity Check
No significant circularity: the main p^{-O(k)} / p^{-O(Delta(H))} bounds are derived from external concentration inequalities, jumbledness, and external fast subgraph counting, not from self-citation or fitted inputs.
full rationale
The load-bearing derivation chain for the k-clique upper bound (Theorem 3.1 / Theorem 1.2) is self-contained against external results: Algorithm Clique-Quality samples a random multiset S of size s* and compares C_ell(S) to the G_{n,p} expectation E_{s*,ell}. The concentration lemma (Lemma 3.6) applies the external strengthened McDiarmid inequality of [Com24] (Corollary 2.19) to f_ell, with the good event Y defined by (ell-1)-clique concentration. No parameter is fitted to the target claim; the sample size s_ell is explicitly chosen to make the exponential terms small, and the completeness argument uses the external concentration of subgraph counts in G_{n,p} (Proposition 2.9 from [Jan90,JOR04]) together with a self-contained induction (Claim 3.14). The runtime upper bound further uses the external fast motif-counting result of [CFZ14] on jumbled graphs, with jumbledness of G_{n,p} verified self-contained in Propositions 2.13-2.16. The lower bound is a standard planted-SBM indistinguishability argument with no circular dependence on the upper bound. The general motif result (Theorem 4.1) is the same argument with density increments defined from the motif H; the density-increment calculation is a computation, not a self-referential reduction. The only potentially self-citational item, reference [MPR+25] (sharing authors Marcussen and Rubinfeld), appears in the bibliography and is not used as a load-bearing premise in the derivation of Theorems 3.1, 4.1, or 5.2. Several other Rubinfeld-authored works are cited only for related-work context and comparisons. A skeptical note about a possible factor-of-two gap in the bounded-difference constants of Lemma 3.6 concerns proof correctness, not circularity: even if the constants need adjustment, that would not make the theorem equivalent to its inputs by construction. Overall, no step reduces to its own inputs by definition or by fitted parameters, so the circularity score is low (1 out of 10).
Assumptions & free parameters
free parameters (7)
- Universal exponent constants c1,c2,c3 (Theorems 1.2, 4.1) =
unspecified; c2 consistent with 1/2, c1 and c3 are slack
- Geometric decay ratio 2/3 in epsilon_ell =
epsilon_ell = epsilon * (2/3)^{k-ell-1}
- Quasirandomness decay alpha_ell =
alpha_2 = epsilon^2 p^2 (2/3)^{2(k-3)} / 128; alpha_ell = p^{2ell-2} epsilon_{ell-1}^2 / (4096 ell^2)
- Constant C = exp(poly(k/epsilon)) in jumbledness test and sample size =
exp(poly(k/epsilon))
- Degree/codegree tolerance delta =
delta = O(p^{2k}/C^2) = p^{2k}/(12 C^2)
- Planted region size ell in lower bounds =
ell = 2^{2*C(k,2)+1} n p^{Delta/2} (motifs); ell = Theta(np) (triangles)
- Dispersion constant 1/100 in Prop 2.9 =
1/100 (adjustable)
assumptions (7)
- standard math Strengthened McDiarmid inequality with high-probability bounded differences (Theorem 2.18 of [Com24]; adapted as Corollary 2.19)
- standard math Concentration of labeled induced subgraph counts in G_{n,p} (Prop 2.9, attributed to [Jan90, JOR04], proved in Appendix D)
- domain assumption Efficient approximate subgraph counting in (p,beta)-jumbled graphs (Prop 2.8, Proposition 9.8 of [CFZ14])
- standard math Jumbledness of G_{n,p} and its subgraphs via degree/codegree conditions (Props 2.7, 2.13, 2.15, Cor 2.14)
- domain assumption Regime assumption n >= p^{-c k} (equivalently p >= omega(n^{-2/(k-1)})) for clique-count concentration
- domain assumption Arboricity bound alpha(G) <= 2np w.h.p. for G ~ G_{n,p} (Prop 2.11 and Cor 2.12 from [GPS18])
- standard math Concentration of motif counts in the planted / stochastic-block-model NO distribution (Prop D.2)
invented entities (3)
-
Quality control problem class (D,rho)
independent evidence
-
Exponentially robust quasirandomness (ERQ)
independent evidence
-
Density increment r_ell(H)
independent evidence
Cite this review
Pith. "Pith review of Quality control in sublinear time: a case study via random graphs." pith.science (2026). https://pith.science/paper/JLW7ONX2
@misc{pith2026250816531,
author = {Pith},
title = {Pith review of: Quality control in sublinear time: a case study via random graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/JLW7ONX2}},
note = {Machine review of arXiv:2508.16531}
}
abstract
Many algorithms are designed to work well on average over inputs. When running such an algorithm on an arbitrary input, we must ask: Can we trust the algorithm on this input? We identify a new class of algorithmic problems addressing this, which we call "Quality Control Problems." These problems are specified by a (positive, real-valued) "quality function" $\rho$ and a distribution $D$ such that, with high probability, a sample drawn from $D$ is "high quality," meaning its $\rho$-value is near $1$. The goal is to accept inputs $x \sim D$ and reject potentially adversarially generated inputs $x$ with $\rho(x)$ far from $1$. The objective of quality control is thus weaker than either component problem: testing for "$\rho(x) \approx 1$" or testing if $x \sim D$, and offers the possibility of more efficient algorithms. In this work, we consider the sublinear version of the quality control problem, where $D \in \Delta(\{0,1\}^N)$ and the goal is to solve the $(D ,\rho)$-quality problem with $o(N)$ queries and time. As a case study, we consider random graphs, i.e., $D = G_{n,p}$ (and $N = \binom{n}2$), and the $k$-clique count function $\rho_k := C_k(G)/\mathbb{E}_{G' \sim G_{n,p}}[C_k(G')]$, where $C_k(G)$ is the number of $k$-cliques in $G$. Testing if $G \sim G_{n,p}$ with one sample, let alone with sublinear query access to the sample, is of course impossible. Testing if $\rho_k(G)\approx 1$ requires $p^{-\Omega(k^2)}$ samples. In contrast, we show that the quality control problem for $G_{n,p}$ (with $n \geq p^{-ck}$ for some constant $c$) with respect to $\rho_k$ can be tested with $p^{-O(k)}$ queries and time, showing quality control is provably superpolynomially more efficient in this setting. More generally, for a motif $H$ of maximum degree $\Delta(H)$, the respective quality control problem can be solved with $p^{-O(\Delta(H))}$ queries and running time.
Forward citations
Cited by 1 Pith paper
-
Graph k-Coloring in Average Sublinear Time
The exact average-case complexity of k-coloring random k-colorable graphs is Θ(nk) for every k ≤ n^{1/37}.
Reference graph
Works this paper leans on
-
[1]
IfC 3(G)< t, then with probability at least1−γ, the algorithm outputs a number btthat is less thant
-
[2]
The algorithm performs adjacency list, adjacency matrix, and degree queries
Ift∈[C 3(G)/4, C3(G)], then with probability at least1−γ, the algorithm outputs a number btthat is in the range(1±δ)C 3(G). The algorithm performs adjacency list, adjacency matrix, and degree queries. The expected query complexity and runtime of the algorithm are: O min n·(α ′)2 t , n C3(G)1/3 + m·α ′ t · C3(G) t ·poly (log(n/γ),1/δ). Lemma A.8(Corollary ...
-
[3]
If Algorithm A rejects, then reject
Run Algorithm A (from Lemma A.2) with (arboricity bound) parameterα= 2np. If Algorithm A rejects, then reject
-
[4]
If Algorithm B rejects, then reject
Run Algorithm B (from Corollary A.5). If Algorithm B rejects, then reject
-
[5]
If the output btis< t, then reject
Run Algorithm C (from Lemma A.7) with parametersα ′ = 200 log2(n)·np(arboricity bound),β= 10np(edge bound),t= (1−ε) n 3 p3, and estimation accuracyδ=ε/4. If the output btis< t, then reject. If the algorithm has not terminated afterO 1 p · poly (log(n),1/ε) steps, then reject
-
[6]
If the output btis>(1 + ε 2 ) n 3 p3, then reject
Run Algorithm D (from Lemma A.8) with parametersα ′ = 200 log2(n)·np(arboricity bound),β= 10np(edge bound), andt= (1−ε) n 3 p3, and estimation accuracyδ=ε/4. If the output btis>(1 + ε 2 ) n 3 p3, then reject. If the algorithm has not terminated after O 1 p ·poly (log(n),1/ε) steps, then reject
-
[7]
Otherwise, accept the graph. We now prove that this algorithm implies Lemma A.2. Proof.Completeness:We first reason about completeness, i.e., that Algorithm 1 accepts G∼ Gn,p with high probability (both over the distribution over graphs and the algorithm’s ran- domness). By Corollary 2.12 and Proposition 2.10, with high probability, sincep=ω ε−2 ·1/n , G∼...
-
[8]
To see this, observe that such a circuit can only depend on at mostk d input variables/coordinates
→ {0,1}m with gate fan-inkand depthdcan be written as a summation over at mostm·2 kd AND gates with fan-in at mostk d. To see this, observe that such a circuit can only depend on at mostk d input variables/coordinates. Therefore, the circuit can be written as a summation over at most 2 kd AND gates with fan-in kd, taken over input coordinates and/or their...
Show all 14 references
-
[9]
Consider permutationsσ(x G) of theverticesof then-vertex input graphG
indicating the edges present, we can rewriteC:{0,1} n → {0,1}m equivalently as C(x G) = X i∈[2kd ] gi(xG) = X i∈[2kd ] Y j∈Si hi(xG j ). Consider permutationsσ(x G) of theverticesof then-vertex input graphG. First, sinceF is invariant under graph isomorphism by definition of a...
-
[10]
For all motifsHon at most 2k d vertices, run AlgorithmInduced-Motif-Quality- Efficient(on inputsG, n, p,G n,p, ε, andH) to perform quality control on the count of labeled induced copies ofHinG
-
[11]
Constructing an algorithm that is correct with high probability overD
If the quality control algorithmrejectson any motifHon at most 2k d vertices, then output reject. Else, output accept. Observe that the quality control algorithm is thesamefor all graph parameter computable by a Sum-NC 0 circuit with fan-ink. Towards proving Theorem B.2, we be...
-
[12]
IfC(x) =accept, then outputE y∼D[ρ(y)]
-
[13]
Proof of Proposition C.1.First, by the correctness of algorithmsCandEfor quality control andρ-approximation, respectively, the algorithm always outputs a (1±ε)-approximation ofρ(x)
Else, outputE(x). Proof of Proposition C.1.First, by the correctness of algorithmsCandEfor quality control andρ-approximation, respectively, the algorithm always outputs a (1±ε)-approximation ofρ(x). We now argue about the runtime. First, with probability at least 1−1/T,x∼ Dsa...
-
[14]
Sincen 2 ≥2 2( k 2)+1np∆(H)/2 andn≥Cp −∆(H) , this is ≤E[X G]2 · 1 10 · 1 k2 · ε2 2k
·(2k) 2k. Sincen 2 ≥2 2( k 2)+1np∆(H)/2 andn≥Cp −∆(H) , this is ≤E[X G]2 · 1 10 · 1 k2 · ε2 2k . Finally, wheni=j= 0, the summation over the expectation of the indicators for the correspondingS 1, S2, T1, T2 is≤E[X G]2 due to the independence of theS 1, S2 indicators with theT...
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.