{"id":"59df1247-2a42-4d0a-ad8f-5da6facaa339","arxiv_id":"2505.04604","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Testing whether a Boolean function is a k-junta and finding its relevant variables have the same optimal sample complexity, achieved by the brute-force consistent-set algorithm.","lead":"This paper proves that deciding whether a Boolean function depends on only k variables and finding those variables need the same number of random examples. It settles the exact sample size for both problems, showing the straightforward consistent-set search is optimal.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 3.19(3) is false: the products F_zG_z are not negatively associated, so Lemma 3.20 and the lower-bound proof are unsupported as written.","rationale":"The reader correctly identified Proposition 3.19 as the fragile point of the lower-bound proof, but focused on the sub-gaussian parameter in Proposition 3.19(1). That issue is repairable: from Eq. (6), F_z has variance Theta(D/K), so its sub-gaussian norm is Theta(sqrt(D/K)) rather than O(D/K); the product norm for F_zG_z becomes O(D/K) instead of O(D^2/K^2), and the resulting tail in Lemma 3.20 still has the same order. The more serious problem is Proposition 3.19(3). The proof claims F_zG_z is a monotone increasing function of disjoint blocks of negatively associated variables, which is false because F_z and G_z are signed. In fact, the products are positively correlated when the underlying F and G sequences are negatively correlated, so the sequence {F_zG_z} is not negatively associated. Since Lemma 3.20 relies on Theorem 3.18 for negatively associated sub-exponential variables, the concentration bound used in Lemma 3.21 has no valid proof as written. The upper bound, the SOPP reduction, and the overall equivalence framework are independent and seem sound; the flaw is localized to Section 3.3.2 but it is load-bearing for the main lower bound. The result may still be true with a correct concentration argument, but the submitted proof does not establish it, so a conditional acceptance is not sufficient; the paper should be rejected or sent back for a major revision of the lower-bound proof.","tokens_in":28434,"tokens_out":36729,"duration_ms":371428,"concrete_test":"Enumerate all balanced functions on k=4 bits with |S∩T|=1 (so D=2, K=16), compute H_0 = F_0G_0 and H_1 = F_1G_1 for each pair (f,g), and compute Cov(H_0,H_1) over the uniform balanced-function distribution. If this covariance is positive, Proposition 3.19(3) is false. A companion analytical check: attempt to re-derive Lemma 3.20 without invoking negative associativity, for instance by conditioning on G and using a high-probability upper bound on ||G||_2^2; if this requires a new argument, the current lower-bound proof is incomplete.","verdict_should_be":"REJECT","load_bearing_attack":"The lower bound in Theorem 3.1 is obtained via Lemma 3.21, whose proof uses Lemma 3.20 to control the concentration of R = 1/2 + (2/D)<F,G>. Lemma 3.20 applies Theorem 3.18 to the sum of the variables F_zG_z, which requires the sequence {F_zG_z}_z to be negatively associated; this is exactly what Proposition 3.19(3) asserts. That assertion is not justified and is in fact false. F_z = rho_f(z) - 1/2 is signed, so F_zG_z is not a monotone function of the underlying NA variables X_{z,i}, Y_{z,i}; the proof's monotonicity claim fails. Concretely, for two distinct blocks z, z', E[F_zG_z F_{z'}G_{z'}] = E[F_z F_{z'}] E[G_z G_{z'}] because f and g are independent, and with zero means this is Cov(F_z,F_{z'}) Cov(G_z,G_{z'}). Negative associativity of the F's and of the G's makes both covariances non-positive, hence their product is non-negative (strictly positive in the nondegenerate regime). Since the H_z = F_zG_z have mean zero, a positive covariance between H_z and H_{z'} violates negative associativity (taking the identity functions on those two coordinates). Thus Theorem 3.18 cannot be invoked as written. The reader's sub-gaussian parameter objection to Proposition 3.19(1) is a real but secondary typo: the correct norm sqrt(D/K) still gives product sub-exponential norm O(D/K), and the final exponent in Lemma 3.20 could plausibly be recovered. But Lemma 3.20 as proved depends essentially on the false NA claim, and no alternative concentration argument is supplied; the balls-and-bins lower bound therefore has no valid proof as submitted.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distribution-free sample-based testing of k-juntas and k-feature selection. It formalizes a \"brute-force\" algorithm that outputs any set of k variables consistent with the sample, and claims that this algorithm is sample-optimal for both tasks with sample size Θ((1/ε)(√(2^k log C(n,k)) + log C(n,k))). The upper bound is obtained by reducing both tasks to testing a distribution property called \"Supported on One-Per-Pair\" (SOPP) and giving a tight SOPP tester. The lower bound is built from a balls-and-bins lemma applied to balanced k-juntas: under the uniform distribution, the labels of a random balanced junta are shown to be nearly uniform on m samples for m up to the claimed lower bound, and a product-distribution reduction converts this into the 1/ε dependence. The paper also derives a lower bound for junta truncation. The central lower-bound proof relies on a concentration lemma whose proof uses a false negative-association assertion; the main theorem is therefore not established as written.","tokens_in":28777,"tokens_out":10964,"duration_ms":110152,"significance":"If the main theorem can be repaired, this is a substantial contribution: it gives the first tight sample-complexity bound for distribution-free sample-based junta testing, establishes an equivalence between testing and feature selection, and introduces an elegant connection to the SOPP distribution-testing problem. The upper-bound framework (Lemmas 2.4 and 2.5) is clean and appears correct, and the balls-and-bins strategy is a natural and potentially reusable technique. However, the current proof of the uniform lower bound hinges on Lemma 3.20, whose proof is invalid as written; until this is fixed, the paper's central claim is unverified.","major_comments":[{"comment":"The proof of Lemma 3.20 is not valid as written. Proposition 3.19(3) asserts that the variables {F_z G_z} are negatively associated, but this assertion is false. For distinct z, z', since f and g are independent and all four variables have mean zero, E[F_z G_z F_{z'} G_{z'}] = E[F_z F_{z'}] E[G_z G_{z'}] = Cov(F_z,F_{z'}) Cov(G_z,G_{z'}). Negative associativity of the F's and of the G's gives both covariances ≤ 0, so the product is ≥ 0 and is strictly positive in the nondegenerate case. Negative associativity of {F_z G_z} would require Cov(F_z G_z, F_{z'} G_{z'}) ≤ 0, since the identity functions on two disjoint coordinates are both monotone increasing. Moreover, the proof's claim that F_z G_z is a monotone function of the underlying variables fails because F_z and G_z are signed. Since Theorem 3.18 is invoked in Lemma 3.20 only through the asserted negative associativity, and Lemma 3.20 is the sole concentration input to Proposition 3.13 and Lemma 3.21, the uniform lower bound (Theorem 3.1) and hence the main lower bound (Theorem 1.6) are not established as written. Please either prove a valid concentration inequality for sum_z F_z G_z by another method or restructure the lower-bound argument.","section":"§3.3.2, Proposition 3.19(3) and Lemma 3.20"},{"comment":"The claimed sub-gaussian parameter is inconsistent with Eq. (6). F_z = (D/(2K)) sum_{i=1}^{K/D} X_{z,i}, where the X_{z,i} are conditionally centered {±1} variables, so Var(F_z) = Θ(D/K) and the sub-gaussian norm is Θ(√(D/K)), not O(D/K). The stated bound flows into the stated O(D^2/K^2) sub-exponential parameter for F_z G_z. With the corrected norm, the product norm becomes O(D/K), and the final exponent in Lemma 3.20 appears recoverable; I therefore view this as a correctable technical error rather than a separate obstruction, but it must be stated and proved correctly.","section":"§3.3.2, Proposition 3.19(1)"}],"minor_comments":[{"comment":"In the simulation step, the two branches are both described as \"if x_{n+i*} = 1\". The second branch should read \"if x_{n+i*} = 0\", since otherwise the simulated distribution is not µ_q.","section":"§3.4.1, Proposition 3.24"},{"comment":"The displayed derivation defining T(∆) and the subsequent ratio T(∆)/T(∆−1) is hard to follow and appears to contain a typo in the exponent on (n choose k). Please re-check the algebra so that the splitting argument can be verified without ambiguity.","section":"§3.3.3, proof of Lemma 3.21"},{"comment":"The hypothesis states \"k = k(n) < n−2\", but the reduction is to feature selection on a domain of 2n bits while the junta setup uses n bits. The relationship between k and n should be clarified so that the two domains are not confused.","section":"§3.2, Lemma 3.10"},{"comment":"The formal theorem states k < (1−τ)n/e, while Lemmas 3.22 and 3.25 use k ≤ (1−τ)n. These hypotheses should be aligned, or the derivation of the stricter condition should be explained.","section":"Theorem 1.6 vs. Lemmas 3.22 and 3.25"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nQuick take: this paper has a genuinely nice upper-bound story, but the lower bound has a load-bearing flaw that the reader's report underweights. The sub-gaussian parameter issue in Proposition 3.19(1) is real but minor—the correct norm is sqrt(D/K), not D/K, and the final concentration exponent survives the fix. The serious problem is Proposition 3.19(3), which claims the variables {F_z G_z} are negatively associated.\n\nThat claim is false. For z ≠ z', write H_z = F_z G_z. Since f and g are independent, E[H_z H_z'] = E[F_z F_z'] E[G_z G_z']. The F's are negatively associated with mean zero, so E[F_z F_z'] ≤ 0; likewise for the G's. The product is therefore non-negative, and strictly positive in the nondegenerate regime. Negative association with mean zero would require non-positive covariance, so {H_z} is not negatively associated. The proof's monotonicity argument fails because F_z is signed: multiplying by G_z destroys the required monotonicity in the underlying variables.\n\nLemma 3.20 applies Theorem 3.18 to the sum of the H_z's, and that theorem explicitly requires negative association. Without it, the stated concentration tail has no proof. Lemma 3.21 and Theorem 3.1 then collapse, since they rely directly on Lemma 3.20. I see no alternative concentration argument in the manuscript.\n\nWhat is actually good: the SOPP reduction in Section 2 is clean and gives a tight upper bound for both junta testing and feature selection; the balls-and-bins framework is a sensible way to attack the lower bound; and the paper is well-written and self-contained. The equivalence may well be true, and I would guess it is, but the current lower-bound proof needs a new idea, not a small correction.\n\nThis paper is for people working on distribution-free sample-based property testing and the testing-versus-learning question. The upper bound and the framing deserve a serious referee; the lower bound needs another round. I would send it to peer review, with a referee specifically tasked to examine the concentration section, but I would not cite the lower bound as proven in its current form.","headline":"The upper-bound side is clean, but the uniform lower bound rests on a false negative-association claim in Proposition 3.19(3), so the main theorem is not proven as written.","tokens_in":29357,"tokens_out":4182,"would_cite":false,"duration_ms":42627,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Testing whether a boolean function depends on only k variables and finding those k variables are statistically equivalent: both have sample complexity $\\Theta\\left(\\frac{1}{\\varepsilon}\\left(\\sqrt{2^k \\log \\binom{n}{k}} + \\log…","keywords":["junta testing","feature selection","sample-based testing","distribution-free","sample complexity","property testing","balanced functions","negative association"],"falsifier":"Compute the empirical tail $P[\\langle F,G\\rangle > D\\lambda/2]$ for uniformly random balanced functions $f,g$ at several $(k,\\Delta)$ pairs: Lemma 3.20 predicts decay $\\exp(-c(K^2/D)\\lambda^2)$, but the true sub-gaussian norm of $F_z$ gives the slower rate $\\exp(-c(K/D)\\lambda)$; observing which rate holds settles whether the proof's concentration step is valid.","tokens_in":28201,"feed_emoji":"⚖️","tokens_out":12019,"duration_ms":107861,"temperature":0.7,"pith_summary":"This paper proves that, in the distribution-free sample-based setting, the testing question—does an unknown boolean function depend on only $k$ of its $n$ inputs?—and the search question—if it does, which $k$ inputs?—are statistically equivalent. The same simple algorithm, which draws samples and keeps any set of $k$ variables that no sample contradicts, is sample-optimal for both tasks, with sample size $\\Theta\\left(\\frac{1}{\\varepsilon}\\left(\\sqrt{2^k \\log \\binom{n}{k}} + \\log \\binom{n}{k}\\right)\\right)$. This is the first tight bound for any natural class of boolean functions in this model, and it improves the previous lower bound of $\\Omega\\left(\\sqrt{2^k} + \\log \\binom{n}{k}\\right)$. The proof works by reducing both tasks to a distribution-testing problem called SOPP (supported on one per pair) and by a balls-and-bins argument showing that random balanced juntas are indistinguishable from random functions below that sample size.","feed_headline":"Testing a k-junta and finding its k variables cost the same","feed_subtitle":"The brute-force 'keep any consistent k-variable set' algorithm is sample-optimal for both, settling a key testing-versus-learning question.","key_machinery":"The central object is the SOPP testing problem: a distribution $p$ over $[2N]$ is SOPP if each pair of coordinates $(2i, 2i-1)$ contains at most one support point, and testing SOPP with $N = 2^k$ reduces to both junta testing and feature selection. Conditioning each candidate $k$-variable set $S$ gives a distribution over the $(k+1)$-bit strings $(x_S, f(x))$, and SOPP captures exactly whether $f$ is a junta on $S$; the SOPP tester (reject only if a sample hits both members of some pair) is proved sample-optimal. The lower bound is driven by a balls-and-bins lemma: if $M$ random 'balls' (balanced $k$-juntas) thrown into $2^m$ bins have uniform collisions and unlikely collisions, their labels become nearly uniform and hence indistinguishable from random functions. The hard part is verifying the unlikely-collision condition for the family of all balanced $k$-juntas, using negative-association concentration for sub-gaussian and sub-exponential variables.","core_discovery":"Testing $k$-juntas and $k$-feature selection require the same number of random samples: $m = \\Theta\\left(\\frac{1}{\\varepsilon}\\left(\\sqrt{2^k \\log \\binom{n}{k}} + \\log \\binom{n}{k}\\right)\\right)$. The obvious algorithm—draw $m$ samples, then output Accept (for testing) or a set $T$ (for feature selection) if $T$ is consistent with every sample—achieves this bound, and the paper proves matching lower bounds that hold even for two-sided error testers. For constant $\\varepsilon$, the lower bound already holds under the uniform distribution; the $1/\\varepsilon$ dependence is forced by a construction over a product distribution with exponentially decaying coordinates. A byproduct is the first tight lower bound (up to constants) for $k$-junta truncation testing.","pith_inferences":["A candidate general principle suggested by the equivalence: sample-based testing of a class $H$ via the consistent-hypothesis algorithm is sample-optimal exactly when proof-based one-sided testers cannot be beaten by evidence-based two-sided testers; juntas now join the positive side, while support-size functions are the known negative example.","The SOPP reduction is a transferable template: any distribution-free sample-based test of a property expressible as 'each hypothesis is a function on a bounded set of coordinates' could be analyzed by mapping each candidate coordinate set to a two-point-pair distribution, with junta testing as the case where the witness set is exactly a $k$-subset of variables.","A direct check of the flagged concentration step: computing the true sub-gaussian norm of $F_z$ in Equation (6) validates whether the lower-bound proof can be repaired, since the paper's claimed $O(D/K)$ parameter is smaller than the variance-derived $\\Theta(\\sqrt{D/K})$; the main theorem might still hold, but not by the given route."],"forward_implications":["For any distribution-free sample-based $k$-junta tester, no estimator based on correlations between variable sets can beat the trivial consistent-set algorithm; the union-bound analysis is tight up to constant factors.","Feature selection provides no statistical advantage over testing: deciding whether a junta exists costs the same as recovering the relevant variables, and the two problems can be solved by the same algorithm.","Under the uniform distribution with constant $\\varepsilon$, once the sample size falls below the stated bound, random balanced juntas become indistinguishable from random functions, so no tester can succeed below it.","When the distance parameter $\\varepsilon$ is small (down to $2^{-\\tau n}$), the sample bound must grow as $1/\\varepsilon$, and achieving that dependence requires a known non-uniform product distribution rather than the uniform one.","A tight lower bound for testing $k$-junta truncation follows as a byproduct, improving the previous $\\Omega(\\log \\binom{n}{k})$ lower bound."],"supporting_citations":[{"why":"Supplies the previous lower bound $\\Omega(\\sqrt{2^k}+\\log \\binom{n}{k})$ for active and passive junta testing, which this paper tightens.","marker":"[AHW16]"},{"why":"Establishes the VC-dimension framework for distribution-free sample-based testing that the paper's upper bound builds on.","marker":"[BFH21]"},{"why":"Defines sample-based testers and shows the consistent-hypothesis algorithm is optimal for learning but not always for testing, the question this paper resolves for juntas.","marker":"[GR16]"},{"why":"The classic testing-by-learning reduction, used here as the contrast showing why junta testing does not reduce to feature selection.","marker":"[GGR98]"},{"why":"Shows testing support size is strictly easier than learning the histogram, providing the contrasting class in the testing-vs-learning question.","marker":"[FH25]"},{"why":"Introduces $k$-junta truncation testing, which this paper's lower bound tightens.","marker":"[HN23]"},{"why":"Supplies the negative-association definitions, closure properties, and Chernoff-type inequalities used in the lower-bound concentration proof.","marker":"[Waj17]"},{"why":"Provides the sub-gaussian and sub-exponential characterizations and the product-of-subgaussians lemma used in Proposition 3.19.","marker":"[Ver18]"}],"fun_headline_variants":["Testing vs. finding k-junta variables: same sample cost","k-junta testing and feature selection: one optimal algorithm","Sample-optimal testing and finding of k-juntas: same bound","One sample complexity for testing and locating k-junta variables","Testing k-juntas vs. finding them: identical sample needs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower bound stands on the concentration claim in Lemma 3.20 (Section 3.3.2), which assumes each $F_z$ has sub-gaussian parameter $O(D/K)$ even though $F_z = (D/(2K))\\sum_{i=1}^{K/D} X_{z,i}$ is a scaled sum of random $\\pm1$ variables whose true sub-gaussian norm is $\\Theta(\\sqrt{D/K})$; without a corrected parameter the uniform-distribution lower bound is unsupported.","fun_headline_variants_meta":{"raw":{"variants":["Testing vs. finding k-junta variables: same sample cost","k-junta testing and feature selection: one optimal algorithm","Sample-optimal testing and finding of k-juntas: same bound","One sample complexity for testing and locating k-junta variables","Testing k-juntas vs. finding them: identical sample needs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000542,"raw_usage":{"total_tokens":2549,"prompt_tokens":852,"completion_tokens":1697,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":468,"completion_tokens_details":{"reasoning_tokens":1612}},"tokens_in":468,"tokens_out":1697,"duration_ms":10872,"temperature":1.0,"reasoning_tokens":1612,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:26:24.744187+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the empirical tail $P[\\langle F,G\\rangle > D\\lambda/2]$ for uniformly random balanced functions $f,g$ at several $(k,\\Delta)$ pairs: Lemma 3.20 predicts decay $\\exp(-c(K^2/D)\\lambda^2)$, but the true sub-gaussian norm of $F_z$ gives the slower rate $\\exp(-c(K/D)\\lambda)$; observing which rate holds settles whether the proof's concentration step is valid.","supporting_citations":[],"review_version":1}