{"id":"bec1d7d5-1047-4a6a-9dce-867df33c130f","arxiv_id":"2507.02842","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Replicable testers can be assumed to threshold a deterministic statistic against a random number, and this canonical structure yields improved sample-complexity bounds for several classic testing problems.","lead":"This paper gives structural tools for replicable hypothesis testers, algorithms whose output is stable when rerun on fresh samples from the same distribution. It shows such testers can be cast in a canonical form, then uses that form to prove new near-optimal sample-complexity bounds for coin, uniformity, closeness, and Gaussian mean testing.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Gaussian mean testing lower bound depends on an unproved folklore TV bound (Prop. 3.7); if its constant or scaling is wrong, the Ω(√d/(α²ρ)) term may fail.","rationale":"The reader's weakest-assumption analysis identifies Proposition 3.7, and my own pass confirms it is the most load-bearing unresolved point. I rechecked the canonical-properties proof (Lemmas 4.5–4.9 and Theorem 1.2), the chaining lemma (Lemma 5.1 and Theorem 1.3), and the main lower-bound applications; they are internally consistent and do not appear to hide a structural error. The Gaussian lower bound is the one place where the argument explicitly imports an unproved, constant-sensitive fact: the TV bound between a chi-square and a small positive shift. If that fact fails, Lemma 7.14's indistinguishability condition can fail, and the claimed Ω(√d/(α²ρ)) sample-complexity lower bound would not be established. The bound is very likely true with the stated constants, and a short proof would fully resolve the issue, which is why the verdict should remain CONDITIONAL rather than being hardened. The secondary overclaim about 'constant-factor optimal' closeness testing (the lower bound has logarithmic factors in some regimes) is a presentation issue and does not affect the central structural claim.","tokens_in":61338,"tokens_out":22888,"duration_ms":259625,"concrete_test":"Supply a short proof of Proposition 3.7, e.g., via the Hellinger affinity: for χ²_k with density f_k, show 1 − ∫√(f_k(x) f_k(x+t)) dx ≤ C·t²/k for |t| ≤ 0.001√k, hence TV(χ²_k, χ²_k+t) ≤ C′·t/√k ≤ 0.1. Independently, numerically evaluate TV(χ²_k, χ²_k+t) for k = 1, 10, 10², 10⁴, 10⁶ and t = ±0.001√k using high-precision integration or a root-finding implementation of the L¹ distance; if any computed value exceeds 0.1, the bound as used in Lemma 7.14 is false and Theorem 1.10 needs revisiting. If the analytic bound is produced and the numerics agree, the concern is resolved without changing the stated results.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 3.7 is stated as folklore without proof or citation, yet it is the linchpin of Lemma 7.14, which bounds the total-variation distance between the norms of Gaussian empirical means used to build the chaining lower bound for replicable Gaussian mean testing (Theorem 1.10). Specifically, Lemma 7.14 uses Prop. 3.7 to argue that dTV(χ²_{d−1}, t + χ²_{d−1}) ≤ 0.1 for |t| ≤ 0.001√(d−1), and this is applied to conclude that consecutive distributions in the chain have TV at most 0.5. If the claimed 0.1 were, say, 0.6, then the final expectation argument in Lemma 7.14 would no longer yield dTV(Z₁,Z₂) ≤ 0.5, and the lower bound would not follow. The bound itself is plausible — a Hellinger or ∫|f'| estimate gives TV = O(t/√k) — so the gap is likely repairable, but as written it is an unproved assertion in a load-bearing spot. A secondary issue is that Prop. 3.7 is stated only for 0 ≤ t ≤ 0.001√k, while the application needs the bound for signed t; translation invariance makes this benign, but it should be stated and justified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops general structural and technical tools for replicable hypothesis testing. Its main results are: (i) a canonical-form theorem (Theorem 1.2) asserting that any replicable tester for a symmetric discrete property can be replaced, with the same sample count and accuracy, by a random-threshold algorithm that is order-invariant, label-invariant, and permutation-robustly replicable; (ii) a chaining lower-bound theorem (Theorem 1.3) that converts a chain of pairwise TV-close distributions into a replicability lower bound; (iii) a general ``expectation-gap'' framework for converting non-replicable estimators into replicable testers, yielding constant-factor-optimal or near-optimal bounds for coin, uniformity, and closeness testing; and (iv) a polynomial-time replicable Gaussian mean testing algorithm with a new upper bound plus a matching-in-leading-terms lower bound, together with a replicable hypothesis-selection algorithm. The paper is broad, with detailed proofs of the new structural claims and quantitative applications summarized in Table 1.","tokens_in":61545,"tokens_out":27290,"duration_ms":294716,"significance":"If the results hold, this is a significant advance in the young area of replicable distribution testing. The canonical reduction answers an open question of Liu and Ye and gives a clean target class against which lower bounds can be proved; the chaining framework systematizes the dominant lower-bound strategy; and the expectation-gap framework gives a reusable recipe for porting non-replicable testers. The Gaussian mean testing upper bound is notable as the first polynomial-time algorithm of its kind with a decoupled 1/ρ^2 term, and the hypothesis-selection result demonstrates a useful reduction to coin testing. The paper also ships unusually detailed proofs for the structural lemmas. The main caveats are two load-bearing gaps, both of which appear repairable: an unproved folklore chi-square total-variation bound used in the Gaussian lower bound, and an incomplete symmetrization argument in the matching-based filter of the Gaussian upper bound.","major_comments":[{"comment":"Proposition 3.7 is stated as folklore without proof or citation, and it is the key ingredient in Lemma 7.14 for showing that the norms of empirical means from consecutive Gaussian means are TV-close. The bound dTV(χ²_k, χ²_k + t) ≤ 0.1 for 0 ≤ t ≤ 0.001√k is plausible and can likely be proved by a Hellinger or characteristic-function argument, but the Gaussian lower bound Theorem 1.10 would fail if the constant or scaling were wrong. The paper needs either a complete proof or an exact citation, including the small-k regime, and the statement should be given for signed |t| ≤ 0.001√k because Lemma 7.14 applies it to shifts that are random and signed.","section":"§3.2, Prop. 3.7; §7.5, Lemma 7.14"},{"comment":"The symmetrization proof of Lemma 7.7 does not, as written, establish the claimed existence of a fixed µ1 with the stated high-probability concentration for MS(X', Y'). The proof bounds |MS(X, Y) − µ1(X)| and |MS(X, Y') − µ2(Y')| separately and then appeals to the triangle inequality, but it never controls |µ1(X) − µ2(Y')|; µ1 depends on the first fixed X and µ2 depends on the fixed Y'. A correct argument needs an additional concentration step showing that these conditional expectations are close to a common value for most X and Y'. Since Lemma 7.7 underlies Step B of the Gaussian mean testing upper bound, the algorithm's correctness and replicability for arbitrary distributions are not fully supported as currently written.","section":"§7.3, Lemma 7.7"}],"minor_comments":[{"comment":"There are typos such as ``defined by by'' in the abstract and ``alterate'' in Section 6.3.1; these should be corrected.","section":"Abstract and §1"},{"comment":"In the weak-replicability part of Lemma 7.13, the displayed inequality has the direction reversed: weak replicability gives Pr[A2(X;r) ≠ A2(X';r)] ≤ ρ, so the final line should conclude that the inequality probability is at most ρ, not at least 1−ρ.","section":"§7.5, Lemma 7.13"},{"comment":"In the proof of Corollary 6.9, ``δ = exp(1/ρ)'' should read ``δ = exp(−1/ρ)'' to match the stated failure probability exp(−1/ρ).","section":"§6.2, Corollary 6.9"},{"comment":"The proof invokes ``Lemma 4.3 in [LY24]'' informally with the phrase ``ignoring logarithmic factors''; the lemma, its parameters, and the precise logarithmic dependence should be stated formally so that the claimed tildes are checkable.","section":"§5.1.2, Theorem 1.4"},{"comment":"In Step C of Algorithm 7.1, the text ``Y1,...,Ysa'' contains a typo, and the reuse of the names X1,...,Xs,Y1,...,Ys after Steps A and B is confusing; the fresh samples should be renamed.","section":"§7.4, Algorithm 7.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is well within the scope of the journal and is likely to be influential if the identified gaps are repaired. The canonical reduction and chaining framework are the main structural novelties; the concurrent work [DGK+25] overlaps on uniformity and closeness lower bounds, so the distinct value of this paper also rests on the Gaussian mean testing and hypothesis-selection results. The two major concerns are both fixable in my assessment, but they are load-bearing and should be addressed with complete arguments before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline result is the canonical characterization: any replicable tester for a symmetric property can be replaced, with no loss in sample complexity or accuracy, by a label-invariant, order-invariant, threshold-accepting algorithm that is even permutation-robust. That resolves the Liu-Ye open question and genuinely reduces the design question to choosing the test statistic. The chaining lower bound is a clean, general way to convert indistinguishability chains into replicability lower bounds, and it gives simpler proofs plus sharper constants for uniformity and identity testing. The expectation-gap framework is a useful systematization of a known trick, and it yields the right coin testing bounds and the first nontrivial closeness bounds. The polynomial-time Gaussian mean tester is a real advance over the inefficient DP-based reduction, and the decoupling of the 1/ρ² factor from √d/α² is meaningful.\n\nI verified the main structural lemmas and the chaining proof. They are internally consistent, and no dependency looks circular. The one genuine soft spot is Proposition 3.7: a folklore bound on the TV distance between a chi-square and its shift, stated without proof or citation, yet used as the linchpin of Lemma 7.14 for the Gaussian lower bound. The bound is plausible and probably repairable, but as written it is a load-bearing assertion in a central proof. If the constant or scaling is off, the Ω(√d/(α²ρ)) term could fail. I also agree that the abstract overstates the closeness result: the lower bound has logarithmic factors, so \"constant-factor optimal\" is not strictly what the paper proves. Several other imported statements (e.g., Valiant's wishful-thinking lemma) are used without proof, which is normal in this literature, but they are cited, unlike Prop 3.7.\n\nThese are fixable. The main contributions are new, the proofs are careful, and the concurrent work comparison is honest about overlaps and differences. I would send this to a serious referee. The referee should ask for a proof or citation for Prop 3.7, a corrected statement about the closeness lower bound, and a small cleanup of the informal claims. The core results will survive.","headline":"A substantial and largely sound paper: the canonical-properties theorem and chaining lower bound are real tools, but the Gaussian lower bound rests on an unproved folklore bound and the closeness claims should be softened.","tokens_in":62146,"tokens_out":1253,"would_cite":true,"duration_ms":17786,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","62G10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Replicable testers for symmetric properties can be assumed to accept iff a deterministic statistic exceeds a uniform random threshold, without losing accuracy or samples.","keywords":["replicability","hypothesis testing","distribution testing","sample complexity","canonical threshold algorithm","Gaussian mean testing","expectation-gap estimator","chaining lower bound"],"falsifier":"Compute or numerically bound $\\mathrm{TV}(\\chi^2_k,\\ \\chi^2_k + t)$ for $t = 0.001\\sqrt{k}$ at large $k$ (say $k \\ge 10^4$) and check whether it stays below $0.1$; if it ever exceeds $0.1$, the chain construction in Lemma 7.14 that supports the replicable Gaussian mean testing lower bound breaks.","tokens_in":61107,"feed_emoji":"🧪","tokens_out":7310,"duration_ms":77348,"temperature":0.7,"pith_summary":"A replicable algorithm is one that gives the same answer with high probability on two independent samples from the same distribution. This paper proves that every replicable tester for a symmetric property of discrete distributions can be transformed, without changing sample count or accuracy, into a canonical threshold tester: compute a deterministic statistic from the sample set and compare it to one uniform random number. The transformed tester is also invariant to the order of samples and to the labeling of the domain, an answer to an open question. The authors use this structure to prove new lower bounds for uniformity and closeness testing, and a general estimator that turns many non-replicable testers into replicable ones with near-optimal overhead. They also give a polynomial-time replicable tester for Gaussian mean testing and a replicable hypothesis-selection algorithm.","feed_headline":"Replicable testers reduce to one random threshold","feed_subtitle":"A structural theorem streamlines lower bounds and yields near-optimal tests for coins, closeness, and Gaussians.","key_machinery":"The mechanism is the canonical threshold format: an algorithm that draws $r \\sim \\mathrm{Unif}[0,1]$ and outputs accept if and only if $r \\le f(X)$ for a deterministic $f: X^s \\to [0,1]$. The construction defines $f(X)$ as the acceptance probability of the original algorithm on input $X$, then averages $f$ over permutations of the sample order and of the domain labels; the averaged $f$ keeps the accept/reject distribution unchanged on every distribution, inherits $\\rho$-replicability, and gains $\\rho$-permutation-robust replicability. A companion chaining lemma (Lemma 5.1) shows that if consecutive distributions in a chain have total variation distance at most $0.5$, then a canonical tester that is $2/3$-reliable on the two endpoints must fail replicability when the chain has length about $1/\\rho$, which is what turns the canonical form into lower bounds.","core_discovery":"The paper's central claim is Theorem 1.2: if a $\\rho$-replicable algorithm tests a symmetric property of discrete distributions over $[n]$ with $s$ samples and accuracy $1-\\delta$, then there is another $\\rho$-replicable algorithm with the same sample count and accuracy that accepts exactly when a deterministic function $f(X)$ of the input exceeds a uniform random threshold in $[0,1]$; this $f$ is invariant to sample order and to element labels, and the algorithm is $\\rho$-permutation-robust replicable, meaning its output stays stable even when the underlying distribution is replaced by a permutation of itself. This confines the whole problem of symmetric replicable testing to the choice of a single label-invariant statistic, and it removes the freedom of a replicable algorithm to use arbitrary internal randomness per input.","pith_inferences":["If the canonical form is right, the cost of replicability for a symmetric problem is determined by how spread out the test statistic $f$ is under near-null distributions; lower bounds could also be attacked by showing that every such $f$ must have large spread.","The Gaussian tester's filtering of 'bad' distributions (large covariance in one direction or many large inner products) could plausibly be lifted to other high-dimensional replicable estimation tasks, such as covariance testing or estimation under arbitrary distributions.","Proving or sharpening the folklore chi-square shift bound would settle the gap between the Gaussian mean testing upper and lower bounds; a counterexample to that bound would break the claimed $\\sqrt{d}/(\\alpha^2\\rho)$ term.","The improved in-expectation coin tester suggests a general 'replicability for free' regime for any non-replicable problem whose optimal sample complexity is much larger than $1/\\rho$, whenever the problem admits an expectation-gap analysis."],"forward_implications":["Lower bounds for symmetric replicable testing problems only need to be proven against label-invariant threshold algorithms; the previously restricted lower bound of Liu and Ye holds in general.","A general expectation-gap estimator converts any tester whose statistic has known expectation and bounded variance into a replicable one with $O(1/\\rho^2)$ worst-case overhead, removing a $\\log(1/\\rho)$ factor from prior black-box reductions.","Coin testing and closeness testing get constant-factor optimal replicable sample complexity, with closeness testing addressed for the first time, and uniformity testing gets replicability for free in the large-domain regime where $n \\gg 1/(\\epsilon^6\\rho^2)$.","Gaussian mean testing admits a polynomial-time replicable algorithm using $\\tilde{O}(\\sqrt{d}/(\\alpha^2\\rho) + \\sqrt{d}/(\\alpha\\rho^2) + 1/(\\alpha^2\\rho^2))$ samples, improving the previous inefficient $\\tilde{O}(\\sqrt{d}/(\\alpha^2\\rho^2))$ bound.","Replicable hypothesis selection with multiplicative approximation $3$ uses $O(\\log^5 n/(\\epsilon^2\\rho^2))$ samples in the worst case and $O(\\log^5 n/(\\epsilon\\rho))$ in expectation, and the improved coin tester implies better replicable sampling for any problem that uses coin testing as a black box."],"supporting_citations":[{"why":"Defines replicability, the notion of stability all algorithms in the paper must satisfy.","marker":"[ILPS22]"},{"why":"Prior replicable uniformity tester whose label-invariance restriction this paper removes, and the source of the open question resolved by Theorem 1.2.","marker":"[LY24]"},{"why":"Prior replicable coin testing bounds and high-dimensional replicability results that the new coin and Gaussian bounds improve upon.","marker":"[HIK+24]"},{"why":"Supplies the chi-square statistic and the optimal non-replicable closeness-testing analysis adapted to the replicable setting.","marker":"[CDVV14]"},{"why":"Provides the moment-matching 'wishful thinking' lemma used in the uniformity and closeness lower bounds.","marker":"[Val11]"},{"why":"Supplies the collision-statistic variance analysis used by the replicable uniformity tester.","marker":"[DGPP19]"},{"why":"Shows replicability follows from differential privacy and gives the inefficient baseline for Gaussian mean testing that the new algorithm improves on.","marker":"[BGH+23]"},{"why":"Private high-dimensional mean testing used by the prior Gaussian tester that the new polynomial-time algorithm outperforms.","marker":"[Nar22]"},{"why":"The non-replicable Gaussian mean tester whose norm-based statistic the replicable algorithm builds on.","marker":"[SD08]"},{"why":"The sharp concentration inequality for submodular functions used to bound the matching-size statistic in the Gaussian tester's Step B.","marker":"[BLM00]"}],"fun_headline_variants":["Replicable tests boil down to one threshold","A canonical form for replicable testers","Replicability via a single random cut","Optimal replicable testing: one statistic suffices","Streamlining replicable hypothesis testers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The Gaussian lower bound relies on an unproved folklore bound on the total variation distance between a chi-square distribution $\\chi^2_k$ and its shift by up to $0.001\\sqrt{k}$; if that bound's constant or scaling is wrong, the claimed $\\sqrt{d}/(\\alpha^2\\rho)$ term could fail.","fun_headline_variants_meta":{"raw":{"variants":["Replicable tests boil down to one threshold","A canonical form for replicable testers","Replicability via a single random cut","Optimal replicable testing: one statistic suffices","Streamlining replicable hypothesis testers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000224,"raw_usage":{"total_tokens":1512,"prompt_tokens":1045,"completion_tokens":467,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":661,"completion_tokens_details":{"reasoning_tokens":399}},"tokens_in":661,"tokens_out":467,"duration_ms":6082,"temperature":1.0,"reasoning_tokens":399,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:22:16.534904+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute or numerically bound $\\mathrm{TV}(\\chi^2_k,\\ \\chi^2_k + t)$ for $t = 0.001\\sqrt{k}$ at large $k$ (say $k \\ge 10^4$) and check whether it stays below $0.1$; if it ever exceeds $0.1$, the chain construction in Lemma 7.14 that supports the replicable Gaussian mean testing lower bound breaks.","supporting_citations":[],"review_version":1}