{"id":"ecb576bf-39bd-404f-b8b9-df94bf0ab710","arxiv_id":"2507.02814","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new random-walk framework yields near-optimal sample complexity bounds for replicable uniformity testing (settling an open question) and for replicable closeness testing.","lead":"This paper determines how many samples are needed to test whether probability distributions are uniform, close, or independent, when the test must give the same output on repeated runs. It settles an open question about replicable uniformity testing and introduces a new lower-bound technique that may apply broadly.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.7's proof uses a global replicability hypothesis (w.r.t. the mixture HU) to conclude a pointwise concentration statement for each fixed ξ, a step that is unjustified and is the true load-bearing point of the lower bound transfer.","rationale":"The reader's identified constant error in Lemma 5.13 is real, but it only affects the quantitative mixing-time bound and can be repaired by taking O(log n) steps; it does not threaten the asymptotic conclusion. The local/global gap in Lemma 5.7 is a genuine logical discontinuity in the proof of the central lower bound (Theorem 1.3). Because the gap is repairable by a case split, the work is plausibly correct, so the conditional verdict stands. I agree with the reader that the paper should not be accepted without revisions, but my concern is more specific than the mixing-time constant and targets the concentration argument that transfers average acceptance probability to individual hard instances.","tokens_in":43935,"tokens_out":19476,"duration_ms":204654,"concrete_test":"Re-derive Lemma 5.17 from its stated assumption: attempt to prove κ(ξ) ≤ 1/(20K) for every ξ using only E_ξ κ(ξ) ≤ 1/(10K). If the derivation is impossible, verify whether Proposition 5.5 can be repaired by first handling ξ with κ(ξ) ≥ log^{-2}n (where (14) is immediate) and applying Lemma 5.17 only when κ(ξ) is small. A direct way to settle the matter is to construct a deterministic tester A that is 0.1-correct on M0/Mε and has E_ξ κ(ξ) small, but for some ξ in a positive-measure set has κ(ξ) ≥ 1/2 and acceptance probabilities not concentrated; existence of such an A disproves Lemma 5.7 as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Proposition 5.5 depends on Lemma 5.7, which claims that for any fixed ξ, a deterministic tester that is log^{-2}n-replicable with respect to the mixture HU has acceptance probabilities over p∼Mξ concentrated around their mean. The proof of Lemma 5.7 goes through Lemma 5.17, which assumes only 1/(10K)-replicability with respect to HU. In the proof of Lemma 5.17, Lemma 5.9 is invoked with κ defined for the fixed ξ as Pr_{p∼Mξ,T,T'}[A(T)≠A(T')], and the argument requires 2Kκ ≤ 0.1 to ensure the random-walk path is stable with high probability. However, the stated HU-replicability provides only E_ξ κ(ξ) ≤ 1/(10K); it does not imply the pointwise bound κ(ξ) ≤ 1/(20K). Since ξ is continuous, κ could be large on a small-measure set of ξ without violating the global average, and for such ξ the concentration conclusion can fail. The text contains no case split that treats large-κ ξ separately, even though for those ξ the desired non-replicability statement (14) would already hold. Thus the concentration transfer is not established as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distribution testing under algorithmic replicability. It states three main results: (1) a near-optimal sample-complexity characterization of replicable uniformity testing, Theta-tilde(sqrt(n) epsilon^{-2} rho^{-1} + epsilon^{-2} rho^{-2}); (2) a tight lower bound for replicable closeness testing; and (3) new replicable algorithms for closeness and independence testing. The lower-bound framework replaces the symmetry assumption of Liu and Ye with a concentration argument based on a random walk on sample count vectors, whose mixing time is claimed to be polylogarithmic. The upper bounds combine random-threshold testing with variance reduction, including an averaged statistic for independence testing. The proof is structured into Section 5 for lower bounds and Sections 3--4 for upper bounds, with deferred technical lemmas in appendices.","tokens_in":44149,"tokens_out":23127,"duration_ms":241348,"significance":"If the main claims are correct, the paper settles the open problem posed by Liu and Ye on the optimality of replicable uniformity testing and introduces a random-walk-based technique for proving unconditional lower bounds in replicable distribution testing, which appears genuinely novel. The upper-bound side is also significant: the closeness tester nearly matches the lower bound, and the independence tester demonstrates an averaging technique that may be reusable in other replicable estimation tasks. The paper is carefully written and the proofs are detailed, with explicit deferred appendices. However, the lower-bound argument as written has several load-bearing gaps: a pointwise-versus-global replicability issue in the concentration transfer, an incorrect constant in the coordinate mixing-time proof for part of the parameter range, and a mismatch between the distributional lower bound that is actually proved and the worst-case replicability lower bound claimed in Theorem 1.3. These issues are substantial but appear potentially fixable.","major_comments":[{"comment":"The hypothesis of Lemma 5.17 is that A is 1/(10K)-replicable with respect to the mixture HU, which bounds E_{xi~U[0,eps]} kappa(xi) <= 1/(10K), where kappa(xi) = Pr_{p~Mxi,T,T'}[A(T) != A(T')]. The proof then invokes Lemma 5.9, whose parameter kappa is precisely this fixed-xi quantity. A global bound on E_xi kappa(xi) does not imply the pointwise bound kappa(xi) <= 1/(10K) needed for the random-walk path stability argument. Since xi is continuous, kappa could be large on a small-measure set of xi without violating the global bound, and the proof of Lemma 5.17 contains no case split for such xi. Consequently Lemma 5.7, which asserts concentration for every xi under only global replicability, is not established as written. This step is load-bearing: Lemma 5.7 is used in Proposition 5.5 to derive equation (14), and the same pattern is repeated for closeness testing in Lemma 5.27. A correct proof needs either a pointwise replicability hypothesis or a separate treatment of the large-kappa region.","section":"Section 5.2, Lemma 5.17 and Lemma 5.7"},{"comment":"The proof of Lemma 5.13 contains the assertions `2xi < 0.2` and `0.4xi < 0.04` in the sublinear case. Since the hard-instance parameter xi ranges over [0, eps] with eps allowed up to 1/4, these inequalities are false for xi > 0.1. The claimed two-step mixing time tau(0.04) <= 2 for the coordinate random walk is therefore not proven in the stated parameter range. This affects Theorem 5.10, Lemma 5.15, Lemma 5.17, and ultimately the lower bound for uniformity testing. The constants can likely be repaired by allowing the mixing parameter to be a larger constant (the argument would still yield a constant relaxation time), or by splitting the parameter range, but as written the proof is invalid for eps > 0.1.","section":"Section 5.2, Lemma 5.13"},{"comment":"Proposition 5.5 establishes only that a correct deterministic Poissonized tester cannot be rho log^{-2} n-replicable with respect to the meta-distribution HU. This is a distributional replicability statement at the much smaller parameter rho log^{-2} n, and it does not imply failure of worst-case (epsilon, rho)-replicability as defined in Definition 1.1: a tester whose disagreement probability is, say, rho/2 on every distribution would satisfy the proposition's conclusion yet still be rho-replicable. To derive the lower bound on the sample complexity of (epsilon, rho)-replicable uniformity testing, the proof must include an explicit replicability amplification step (e.g., running the original tester multiple times with fresh samples and taking a majority, at the cost of an O(log(1/rho)) factor in sample complexity) or otherwise bridge the gap between rho log^{-2} n and rho. No such argument appears in the proof of Theorem 1.3, so the stated Theta-tilde lower bound does not follow from the presented analysis. The final step of Proposition 5.5, which asserts Pr_{p~HU}[disagreement >= Omega(rho log^{-2} n)] >= rho from a rho-fraction of xi with E_{p~Mxi}[disagreement] >= log^{-2} n, is also not justified by the preceding Markov argument and needs clarification.","section":"Section 5.2, proof of Theorem 1.3"}],"minor_comments":[{"comment":"Footnote 6 states that fully removing the log^{-2} n replicability requirement requires an eigenvalue argument deferred to a future version. This admission is directly related to major comment 3, and the paper should either prove the stronger statement or explicitly state which version of the theorem is conditional on that future argument.","section":"Section 5.2, footnote 6"},{"comment":"The algorithm asks to estimate the expectations Na and Za up to o(1) error by running IndependenceStats with fresh randomness; the number of repetitions needed and the resulting effect on the sample complexity are not specified. The subsequent proof refers to a 'standard median trick' but does not detail how the median interacts with the variance bounds (e.g., Corollaries 4.11--4.13) or with the replicability guarantee.","section":"Section 4, Algorithm 3 lines 3 and 7"},{"comment":"The proof of Lemma 2.8 is a one-line triangle-inequality argument that does not explicitly handle the maximum over starting states in the definition of mixing time. This is a standard fact, but the proof as written is too terse to be fully verifiable.","section":"Section 2.3, Lemma 2.8"},{"comment":"The sentence 'we assume that tilde-o(sqrt(n) epsilon^{-2} rho^{-1}) = epsilon^{-2} rho^{-2}' is unclear and should be rewritten; the comparison between the two lower-bound terms needs a precise statement.","section":"Section 5.2, first paragraph"}],"recommendation":"major_revision","confidential_remarks":"The lower-bound framework is interesting and likely important, but the current submission has three load-bearing gaps in the proof of the main uniformity lower bound: the pointwise-versus-global replicability issue in Lemmas 5.7/5.17, the incorrect constant and parameter range in Lemma 5.13, and the unbridged gap between distributional rho log^{-2} n-replicability and worst-case rho-replicability in deriving Theorem 1.3. All three appear fixable with additional work, so rejection is not warranted, but the argument as written is not yet correct. The paper is also somewhat informal in the independence-testing upper bound, though that is not the central issue. The citation of [DGK+21], which is co-authored by two of the present authors, is appropriate and does not create circularity, but the reliance on its lemmas should be double-checked for the exact constants used here."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main event is the lower-bound framework in Section 5. The random-walk construction lets the authors prove concentration of acceptance probabilities without assuming tester symmetry, which is exactly what was blocking the field. That is a real step forward, and it appears to deliver the first unconditional near-optimal lower bound for replicable uniformity testing, plus a tight closeness bound. The upper bounds for closeness and independence are clean adaptations of known high-probability testers, and the connection to the high-probability regime is worth stating explicitly.\n\nThe soft spots are real but, I think, repairable. The stress-test concern about Lemma 5.7/5.17 is legitimate: the proof uses global replicability with respect to HU to draw a pointwise conclusion for a fixed ξ. The text does not handle ξ where κ(ξ) is large. The saving grace is that for those ξ the desired non-replicability statement already holds, so a case split in Proposition 5.5 would fix the argument. But as written, the concentration transfer is not established. This is the load-bearing point of the lower bound, so it must be patched.\n\nThere are smaller issues. Footnote 6 admits that removing the log^{-2} n replicability requirement needs an eigenvalue argument that is deferred. Lemma 5.13 has a constant error: 0.4ξ < 0.04 is false for ξ close to ε when ε > 0.1. The asymptotic mixing time survives, but the line is wrong. Lemma 4.10's \"almost identical\" case analyses in the independence tester are sketched rather than shown; they deserve fuller proofs. The imports from [DGK+21] are fine - they are published results with independent proofs, and the present results do not appear to assume what they are proving.\n\nOverall, the paper is significant and the framework is likely to be reused. It deserves a serious referee. My recommendation is to send it to peer review, but with the clear instruction that the authors must address the pointwise-versus-average gap in Lemma 5.17 and fix the small errors before it is accepted. The central claims are probably correct, but the proof as written is not fully verified.","headline":"A genuinely new lower-bound technique that likely settles the open uniformity testing question, with a few repairable gaps in the random-walk concentration proof.","tokens_in":44719,"tokens_out":3868,"would_cite":true,"duration_ms":41636,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","62G10","60J10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper settles the sample complexity of replicable uniformity testing up to logarithmic factors, and gives near-matching bounds for closeness and independence testing.","keywords":["algorithmic replicability","distribution testing","sample complexity","uniformity testing","closeness testing","independence testing","random walk mixing","Poissonization"],"falsifier":"Run the coordinate random walk of Lemma 5.13 for a concrete large-epsilon setting, for instance ε=0.2 and m close to n/ε², and measure the total-variation distance from stationarity after two steps from a range of starting counts; if any starting state stays more than 0.04 away, the claimed mixing time is false. Also, the stated deduction 0.4ξ < 0.04 already fails for ξ=0.2, so a direct numerical check of the two-step distribution, rather than the proof's inequality, is what would settle the claim.","tokens_in":1698,"feed_emoji":"🎲","tokens_out":4038,"duration_ms":125568,"temperature":0.7,"pith_summary":"The paper establishes that any algorithm which (ε,ρ)-replicably tests uniformity over a domain of size n must use $\\widetilde{\\Theta}(\\sqrt{n}\\,\\varepsilon^{-2}\\rho^{-1}+\\varepsilon^{-2}\\rho^{-2})$ samples. This settles the open question left by the earlier replicable uniformity tester, and it does so without assuming the tester is symmetric. The same lower-bound technique gives a matching bound for closeness testing, and the paper supplies new replicable testers for closeness and independence whose sample counts match the bounds up to logarithmic factors. The result matters because replicability—returning the same answer on two independent sample sets—is a formal stability guarantee, and knowing its exact sample price lets practitioners compare replicable testers with standard high-probability testers.","feed_headline":"Replicable uniformity testing cost pinned down","feed_subtitle":"New lower-bound method shows prior tester nearly optimal; closeness and independence testers follow.","key_machinery":"The central machinery is the sample random walk $\\mathrm{RW}_{m,\\xi}$ on the space of sample-count vectors: pick a hard distribution from the meta-distribution, draw two independent Poissonized samples, and let the walk transition from one count vector to the next. Because Poissonization makes coordinates independent, the walk factors into n scalar random walks; the paper proves these scalar walks have constant relaxation time and hence O(log n) mixing time, which is exactly what lets the lower bound avoid any symmetry assumption on the tester. On the upper-bound side, the key devices are comparison against a random threshold and an averaged version of an existing independence statistic, whose variance is controlled by an Efron–Stein argument through the expected number of non-singleton flattened samples.","core_discovery":"The paper's central claim is that the sample complexity of (ε,ρ)-replicable uniformity testing over [n] is $\\widetilde{\\Theta}(\\sqrt{n}\\,\\varepsilon^{-2}\\rho^{-1}+\\varepsilon^{-2}\\rho^{-2})$. The lower bound is proved by constructing a meta-distribution over hard instances and showing, without any symmetry assumption on the tester, that acceptance probabilities concentrate around their average when the tester is moderately replicable. The key vehicle is a random walk on Poissonized sample-count vectors that mixes in O(log n) steps, letting the authors transfer an average acceptance probability to individual hard instances. With upper bounds from a random-threshold closeness tester and an averaged independence statistic, the paper also gives near-tight sample complexities for replicable closeness testing and the first replicable independence tester.","pith_inferences":["If the mixing-time lemma survives scrutiny, the same sample-walk argument should yield matching lower bounds for replicable identity testing and independence testing, which the paper leaves open.","The formal resemblance to high-probability testing suggests the hypothesis that replicable testing is equivalent to high-probability testing with failure probability set to ρ, up to logarithmic factors; a generic reduction in either direction would unify the two lines of work.","The averaging procedure used for the independence statistic may be a general recipe: any statistic that is Lipschitz under deleting singleton samples can be stabilized by averaging over internal randomness, which could help convert other high-probability testers into replicable ones."],"forward_implications":["The earlier replicable uniformity tester is sample-optimal up to logarithmic factors, so no future algorithm can beat the $\\widetilde{\\Theta}(\\sqrt{n}\\,\\varepsilon^{-2}\\rho^{-1}+\\varepsilon^{-2}\\rho^{-2})$ barrier.","Replicable closeness testing has sample complexity $\\widetilde{\\Theta}(n^{2/3}\\varepsilon^{-4/3}\\rho^{-2/3}+\\sqrt{n}\\,\\varepsilon^{-2}\\rho^{-1}+\\varepsilon^{-2}\\rho^{-2})$.","Replicable independence testing over $[n_1]\\times[n_2]$ can be solved with $\\widetilde{O}(n_1^{2/3}n_2^{1/3}\\rho^{-2/3}\\varepsilon^{-4/3}+\\sqrt{n_1n_2}\\,\\rho^{-1}\\varepsilon^{-2}+\\rho^{-2}\\varepsilon^{-2})$ samples.","The new lower-bound framework applies to replicable distribution testing generally, so future lower bounds can be obtained without imposing symmetry on the tester."],"supporting_citations":[{"why":"gives the prior replicable uniformity tester and poses the open question answered by Theorem 1.3; also supplies the random-threshold recipe used in the new upper bounds.","marker":"[LY24]"},{"why":"introduces the formal definition of replicability and gives the ε^{-2}ρ^{-2} lower bound from bias estimation that forms one term of the final bound.","marker":"[ILPS22]"},{"why":"provides the high-probability closeness and independence testers whose statistics, expectation-gap lemmas, and non-singleton sample-count bounds the new testers build on.","marker":"[DGK+21]"},{"why":"supplies the spectral-gap-to-mixing-time theorem used to show the sample random walk mixes in O(log n) steps.","marker":"[LPW06]"},{"why":"contributes the averaging-over-random-partitions idea that stabilizes the averaged independence statistic in the upper bound.","marker":"[ADKR19]"},{"why":"provides the flattening technique for heavy bins and the hard-instance construction used for the closeness lower bound.","marker":"[DK16]"},{"why":"gives the standard hard instance for non-replicable closeness testing on which the meta-distribution N_ξ is based.","marker":"[CDVV14]"}],"fun_headline_variants":["Replicable uniformity testing: sample complexity pinned","New lower-bound tool tightens replicable testing costs","Open question answered: replicable uniformity testing cost","Replicable testing: uniformity, closeness, independence costs","Random-walk lower bounds pin replicable uniformity testing"],"cache_read_input_tokens":46848,"weakest_assumption_plain":"The load-bearing premise is that the sample random walk mixes in O(log n) steps under the paper's parameter ranges; if that mixing is actually slow, the concentration argument that carries average acceptance probabilities to individual hard instances fails and the lower bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Replicable uniformity testing: sample complexity pinned","New lower-bound tool tightens replicable testing costs","Open question answered: replicable uniformity testing cost","Replicable testing: uniformity, closeness, independence costs","Random-walk lower bounds pin replicable uniformity testing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001059,"raw_usage":{"total_tokens":4365,"prompt_tokens":787,"completion_tokens":3578,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":403,"completion_tokens_details":{"reasoning_tokens":3503}},"tokens_in":403,"tokens_out":3578,"duration_ms":30400,"temperature":1.0,"reasoning_tokens":3503,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:20:27.740264+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the coordinate random walk of Lemma 5.13 for a concrete large-epsilon setting, for instance ε=0.2 and m close to n/ε², and measure the total-variation distance from stationarity after two steps from a range of starting counts; if any starting state stays more than 0.04 away, the claimed mixing time is false. Also, the stated deduction 0.4ξ < 0.04 already fails for ξ=0.2, so a direct numerical check of the two-step distribution, rather than the proof's inequality, is what would settle the claim.","supporting_citations":[],"review_version":1}