{"id":"36a3d579-270c-4bce-8bf5-f9c858ee1518","arxiv_id":"2504.16065","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors identify a link between agnostic conjunction learning and tolerant junta testing, and use it to improve both algorithms, roughly to 2^{O~(n^{1/3})} time and 2^{O~(k^{1/3})} queries.","lead":"This paper gives faster algorithms for two noisy learning and testing problems: finding the best conjunction rule from imperfect data, and checking whether a function effectively depends on only a few variables. The improvements are large enough to prove that adaptive testers beat non-adaptive ones for tolerant junta testing.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Normalized-influence estimator in §6.1 is off by (|U|!)², breaking the sampling step behind Refine-Coordinates and Theorem 3.","rationale":"The reader's weakest assumption was the external coordinate-oracle theorem from ITW21 (Theorem 24). My review identifies a different, internal load-bearing flaw: the normalized-influence estimator in §6.1 appears mis-derived by a factor of (|U|!)². This is not a disagreement with consensus; it is an internal inconsistency between Algorithm 3 and Lemma 50, traceable to the density of sorted uniform order statistics. The classical tester's entire k^{1/3} improvement rests on Refine-Coordinates sampling from normalized influences, so this bug directly threatens Theorem 3. It is concrete and easily checked: the f=χ_{1,2}, U={1,2} instance gives output 4 instead of 1. I am not claiming the paper's high-level idea is dead; the fix may be as simple as deleting the (|U|!)² multiplier, after which the estimator would be unbiased at the correct scale. But as written, the proof of Lemma 53 and hence Theorem 3 is not sound, so the verdict should be conditional on repairing this step. I would not recommend outright rejection because the rest of the architecture and the agnostic-learning result are independent of this component, and a small correction may restore the argument.","tokens_in":59514,"tokens_out":13553,"duration_ms":140675,"concrete_test":"Run the literal Algorithm 3 on f=χ_{1,2}, B=1, U={1,2}, ε=0.1, δ=0.01 and compare the output to NInf_U[f]=1; or re-derive Lemma 50 using the correct order-statistic density |U|! instead of 1/|U|! and verify whether the (|U|!)² multiplier in line 7 should be present.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Algorithm 3 samples r_1,...,r_|U| iid uniform on [0,1], sorts them decreasing to y_1>...>y_|U|, and uses y_|U|, the minimum. Lemma 50 asserts that E_y[E_x[(T_{\\sqrt{y_|U|}}g(x))^2]] = NInf_U[f]/(|U|!)², and Algorithm 3 therefore outputs (|U|!)² times the empirical average of the γ_t. But sorted order statistics have density |U|! on the simplex {1≥a_1≥...≥a_|U|≥0}, not density 1/|U|!. Direct computation gives E[(min)^j] = 1/C(j+|U|,|U|), so E_y[E_x[(T_{\\sqrt{min}}g)^2]] = ∑_{S⊇U} fhat(S)²/C(|S|,|U|) = NInf_U[f]. For the simple case f = χ_{1,2}, U={1,2}, g=1, γ_t=1 for every t and Algorithm 3 returns 4, while NInf_U[f]=1. Thus Lemma 48 and Lemma 50 are false as stated. This matters because Refine-Coordinates (Algorithm 4, line 2(c)(iv)) samples sets T with probability proportional to the λ_U returned by Estimate-Ninf, and Lemma 65 proves the required total-variation closeness using additive accuracy of λ_U at the true NInf scale. With the erroneous (|U|!)² factor, the stated additive guarantee fails and the proof of Lemma 53 — and hence the correctness proof of the classical tester behind Theorem 3 — does not go through as written. A common multiplicative factor would cancel in exact arithmetic, but the proof relies on additive error bounds that do not survive the scaling, so the sampling/TV argument in §6.2.2 is not justified.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims two main results. First, it gives a distribution-free algorithm for agnostically PAC learning conjunctions over {±1}^n that runs in time 2^{O~(n^{1/3})} for constant excess error ε, improving on the previous 2^{O~(n^{1/2})} algorithm of KKMS08. Second, it gives an adaptive classical tolerant k-junta tester that makes 2^{O~(k^{1/3})} queries, improving on the 2^{O~(√k)}-query algorithms of ITW21 and NP24 and thereby yielding the first super-polynomial separation between adaptive and non-adaptive tolerant testing for a natural Boolean property. The paper also presents a quantum 'warm-up' tester with the same query complexity and a new estimator for normalized influences (Algorithm 3). The classical tester relies on coordinate-oracle machinery from ITW21 and on a recursive coordinate-filtering procedure (Refine-Coordinates, Algorithm 4).","tokens_in":59872,"tokens_out":15341,"duration_ms":145399,"significance":"If the correctness issues identified below are resolved, the contribution would be substantial. The claimed agnostic-learning result improves a long-standing bound of Kalai et al., and the claimed tolerant-testing result would give a provable super-polynomial adaptive/non-adaptive separation for a natural Boolean property-testing problem. The paper is ambitious and quite detailed: algorithms and parameters are stated explicitly, several technical ingredients (ball distributions, SharpNoise, local estimators, normalized-influence sampling) are developed at length, and the exposition of the conceptual link between learning conjunctions and junta testing is interesting. The proofs contain enough structure that a local correction to the estimator of Section 6.1 could plausibly repair the main theorem, but as written the classical tester's correctness argument has at least one load-bearing error.","major_comments":[{"comment":"After sorting iid uniforms r_1,...,r_|U| decreasing as y_1>...>y_|U|, the variable y_|U| is the minimum of |U| iid uniform random variables and has density |U|(1-t)^{|U|-1}; equivalently, the ordered vector has density |U|! on the ordered simplex, not 1/|U|! as assumed in the proof of Lemma 50. Direct computation gives E_y[E_x[(T_{√(y_|U|)} g(x))^2]] = ∑_{S⊇U} fhat(S)^2 / C(|S|,|U|) = NInf_U[f], not NInf_U[f]/(|U|!)^2. Consequently Algorithm 3's final multiplication by (|U|!)^2 makes the estimator return (|U|!)^2 · NInf_U[f] in the limit, so the additive accuracy claim of Lemma 48 does not hold at the true NInf scale. This error is load-bearing: Lemma 65 uses the λ_U values from Estimate-Ninf to argue that the sets T sampled in Algorithm 4 line 2(c)(iv) are within total-variation distance (ε/k')^5·(2^{k^{1/3}polylog})^{-1} of the true normalized-influence distribution, and Lemma 53 and the correctness proof of Algorithm 7 depend on that bound. The fix appears local (drop the (|U|!)^2 multiplier and correct the density in Lemma 50), but it must be propagated through Lemmas 52 and 65.","section":"§6.1, Lemma 50 and Algorithm 3"},{"comment":"Lemma 65 conditions on the event E_x[h^2(x)] ≥ ε^2/(2(k')^2) and then invokes Lemma 59 to conclude W_{≥γ}[h] ≥ ε^2/(4(k')^2). However Lemma 59's hypothesis is E_x[h^2(x)] ≥ ε^2/(2k^2), and in the formal setting k' = poly(k,1/ε) is generally much larger than k, so the stated condition does not imply Lemma 59's hypothesis. The same k vs k' mismatch appears in the proof of Lemma 53, where the exit/non-exit thresholds are asserted at ε^2/(2(k')^2) and 2ε^2/(k')^2, whereas Algorithm 4 line 2(c)(iii) and Assumption 54 use ε^2/k^2 and 2ε^2/k^2. These thresholds feed the total-variation argument that justifies the sampling step, so the manuscript must state them consistently at the k^2 scale (or change the algorithm's thresholds accordingly) for the proof of Lemma 53 to go through. If the occurrences of (k')^2 in these two proofs are typos, they still need to be corrected because the submitted text, as written, does not establish the required bound.","section":"§6.2.2, Lemma 65 and the proof of Lemma 53"}],"minor_comments":[{"comment":"The success probability in Lemma 29 is written as 'εm' rather than ε^m, and the same superscript appears lost in the proof of Lemma 32 ('εm·εm'). The intended meaning is clear, but the notation should be fixed throughout Section 4.","section":"§4.3, Lemma 29 and the proof of Lemma 32"},{"comment":"The displayed update for g_{S∪{u}} is not readable as written: 'g_{S∪{u}}(x) = g_S(x) − 1/2(g_S(x) + g(x⊕u S))' appears to involve g_S(x⊕u) and should use a precise notation for the set S. Please rewrite this line unambiguously, matching the induction in Lemma 49.","section":"§6.1, Algorithm 3 line 3(a)"},{"comment":"The coordinates i_1,...,i_m are drawn with replacement from C, while I is then treated as a set of m coordinates. If duplicates occur, |I| is smaller than m; the later probability calculations in Lemmas 55 and 56 treat the draws with replacement, which is consistent, but the algorithm should state explicitly that I is the set of distinct drawn coordinates, since the averaging operation f^I_ave is defined for a set.","section":"§6.2, Algorithm 4 line 2(a)"}],"recommendation":"major_revision","confidential_remarks":"The factor error in §6.1 sits at the base of the classical tester, so I could not certify Theorem 3 from the submitted text. That said, the error looks like a local algebraic slip rather than a fundamental obstruction: removing the (|U|!)^2 multiplier and correcting the density in Lemma 50 should restore the intended estimator. Given the density of the proof, I would recommend that the authors and an independent reader carefully re-check the constants in §6.1–§6.2, including the k vs k' thresholds in Lemma 65 and the proof of Lemma 53, before the paper is accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version. The paper has two genuinely interesting algorithmic results and one clear bug that, as written, invalidates the proof of the classical tester. The bug sits in §6.1: the normalized-influence estimator is off by a factor of (|U|!)². The sorted order statistics on the simplex have density |U|!, not 1/|U|!. So Lemma 50's identity is wrong; the correct expectation is NInf_U, not NInf_U/(|U|!)². Algorithm 3 multiplies by (|U|!)², so its output is (|U|!)²·NInf_U, and Lemma 48 is false as stated. This is not cosmetic: for the γ used in Refine-Coordinates the factor is exp(Ω(k^{1/3} log k)). Since the proof of Lemma 65 uses λ_U as an additive estimate of NInf_U, the TV-distance argument in §6.2.2 collapses, and the proof of Theorem 3 does not go through.\n\nThe rest of the paper is in much better shape. The conceptual connection between agnostic conjunction learning and tolerant junta testing is real and nicely explained. The agnostic learning algorithm (Theorem 1) and the quantum warm-up (Theorem 2) look sound to me, and the disclosure of the DKR25 overlap is honest. The local estimators and SharpNoise machinery are carefully assembled. I found no circularity problems and the citation patterns are appropriate.\n\nThe fix is likely simple: drop the (|U|!)² factor (or correct the density) and adjust the accuracy parameters. Because the factor is common across all sets U, sampling probabilities would be unchanged in exact arithmetic; what needs reworking is the additive-error analysis in Lemma 65 and the statements of Lemmas 48 and 50. I expect Theorem 3 to survive, but I can't certify it without the patch.\n\nRecommendation: this deserves a serious referee. Send it to review, with a prompt to the authors about the §6.1 bug. I would not cite the current version for the classical tester, but I would watch the revision closely.","headline":"A promising pair of algorithms for agnostic conjunction learning and tolerant junta testing, but the classical tester as written contains a wrong density factor in the normalized-influence estimator that breaks the proof; it looks repairable.","tokens_in":60443,"tokens_out":9501,"would_cite":false,"duration_ms":88370,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that learning conjunctions and testing juntas share one mechanism, giving $2^{\\widetilde O(n^{1/3})}$-time learning, $2^{\\widetilde O(k^{1/3})}$-query testing, and the first super-polynomial adaptive/non-adaptive…","keywords":["agnostic learning","conjunctions","tolerant junta testing","adaptive query complexity","non-adaptive lower bounds","Fourier analysis of Boolean functions","local estimators","normalized influences"],"falsifier":"Exhibit a single family of Boolean functions for which every poly(k,1/ε)-coordinate reduction satisfying the stated oracle properties moves dist(f,J_k) by more than ε; then Algorithm 7's guarantee fails at its first step. More locally, a concrete counterexample to Claim 47 or Lemma 60—e.g., a junta whose high-level Fourier mass is concentrated on sets that evade every sampled C—would pinpoint exactly where the refinement argument breaks.","tokens_in":59293,"feed_emoji":"⚡","tokens_out":10866,"duration_ms":91914,"temperature":0.7,"pith_summary":"The paper's goal is to establish that two seemingly unrelated noisy-data problems—agnostically learning conjunctions and tolerantly testing juntas—are the same problem in disguise, and to exploit that hidden identity. It claims that a shared 'ball distribution' idea yields a distribution-free agnostic learner for conjunctions running in time $2^{\\widetilde O(n^{1/3})}\\operatorname{poly}(n,1/\\varepsilon)$, an adaptive classical tolerant junta tester making $2^{\\widetilde O(k^{1/3})}$ queries, and a matching-query quantum warm-up tester. If these claims are right, adaptive tolerant junta testing provably beats non-adaptive tolerant junta testing, because non-adaptive testers are known to need $2^{\\widetilde\\Omega(\\sqrt{k})}$ queries. A reader should care because this is a first super-polynomial adaptive-vs-non-adaptive separation for a natural tolerant Boolean property, and because the learner improves the long-standing $2^{\\widetilde O(\\sqrt{n})}$ bound for a basic distribution-free learning problem.","feed_headline":"One idea cuts costs from square root to cube root for two problems","feed_subtitle":"The same ball-distribution trick cuts the exponent from 1/2 to 1/3 for both problems.","key_machinery":"The load-bearing mechanism is the ball distribution produced by a small random sample of coordinates, together with the SharpNoise operator that enforces it on the Fourier side. In learning, drawing $m=n^{1/3}$ positive examples defines the event $E_{\\vec a}$: strings within Hamming distance $n^{2/3}$ of the first example over the coordinates where all examples agree; on $E_{\\vec a}$ the optimal conjunction has approximate degree $O(n^{1/3}\\log(1/\\varepsilon))$, so the low-degree $L^1$ regression theorem learns it. In testing, the analogous object is $f^C=\\mathrm{SharpNoise}^C_{\\ell,\\kappa,\\Delta}f$, which sharply attenuates all Fourier coefficients whose support has more than $\\ell$ coordinates outside $C$ while nearly preserving the rest; local estimators then compute junta correlations for exponentially many candidate sets $U$ by reusing one set of sample bundles. The classical tester adds a normalized-influence filtering loop, Refine-Coordinates, that pares each candidate coordinate set down to one with half as many irrelevant variables, guaranteeing that a pure set of relevant coordinates is found within $2^{\\widetilde O(k^{1/3})}$ total candidates.","core_discovery":"At its core, the paper claims that the optimal conjunction in agnostic learning and the optimal $k$-junta in tolerant testing are both 'coverage' problems: each wants a small set of variables that captures as much weight as possible of an underlying distribution—the spectral sample in testing, the labeled-example marginal in learning. The paper formalizes this by placing a ball distribution on the sampled coordinates (in learning, inputs within Hamming distance $n^{2/3}$ of the first positive example; in testing, sets whose Fourier support barely escapes the sampled coordinate set $C$), on which the target has approximate degree $O(k^{1/3}\\operatorname{polylog} k)$, then using low-degree regression or local estimators on that ball. Theorem 3 states that Algorithm 7 $\\pm\\varepsilon$-accurately estimates $\\operatorname{dist}(f,\\mathcal{J}_k)$ for every $f:\\{\\pm1\\}^n\\to\\{\\pm1\\}$ using $2^{\\widetilde O(k^{1/3})}$ classical queries; Theorem 1 states that Algorithm 1 agnostically learns conjunctions to excess error $\\varepsilon$ in time $2^{n^{1/3}\\operatorname{polylog}(n,1/\\varepsilon)}$; Theorem 2 gives the quantum analogue of the tester. The paper's own conclusion is that adaptive tolerant junta testing provably outperforms non-adaptive, since the known non-adaptive lower bound is $2^{\\widetilde\\Omega(\\sqrt{k})}$.","pith_inferences":["If the connection is genuine, it predicts that any further improvement to agnostic conjunction learning (below $2^{n^{1/3}}$) should transfer to tolerant junta testing, and vice versa; the paper leaves this transfer as a challenge.","A testable extension is to use the ball-distribution trick on other 'coverage' concept classes, such as decision lists or monotone DNF terms, by checking whether the sampled Hamming ball admits a low-degree approximant; the paper does not explore those cases.","The classical tester's dependence on exact coordinate oracles suggests an immediate robustness experiment: replace oracles by approximate versions and measure how the $2^{\\widetilde O(k^{1/3})}$ bound degrades; nothing in the paper quantifies this."],"forward_implications":["Adaptive tolerant junta testing is provably more powerful than non-adaptive: the $2^{\\widetilde O(k^{1/3})}$-query tester beats the known $2^{\\widetilde\\Omega(\\sqrt{k})}$ non-adaptive lower bound, giving the first super-polynomial separation for a natural tolerant Boolean property.","Agnostic conjunction learning runs in time $2^{n^{1/3}\\operatorname{polylog}(n,1/\\varepsilon)}$, and boosting converts this into $2^{n^{1/3}\\operatorname{polylog}(n,s)}$-time learning of $s$-term DNF formulas and total-integer-weight LTFs over conjunctions.","The quantum warm-up shows the spectral-sample oracle is the only quantum ingredient needed; the same machinery classically simulates it through normalized-influence sampling, suggesting quantum speedup here is not essential once coordinates are reduced.","The new arbitrary-accuracy estimator for normalized influences (Algorithm 3) replaces constant-factor approximations and may strengthen other algorithms that use influence information."],"supporting_citations":[{"why":"Supplies the low-degree L1 polynomial regression theorem that the agnostic conjunction learner uses to convert approximation into a hypothesis.","marker":"[KKMS08]"},{"why":"Provides the approximate coordinate-oracle reduction (Theorem 24) that lets the classical tester work over poly(k,1/ε) coordinates, and gives the sub-exponential junta-distance tester that this paper improves and its normalized-influence approach.","marker":"[ITW21]"},{"why":"Introduces the local-estimator technology and gives the 2^{Ω~(√k)} non-adaptive lower bound that the new adaptive tester beats.","marker":"[NP24]"},{"why":"Originates the approximate coordinate oracles that Theorem 24 relies on for variable reduction.","marker":"[DMN19]"},{"why":"Supplies the flat polynomial construction used in the local estimators for smooth functions.","marker":"[KLS96]"}],"fun_headline_variants":["One idea cuts testing and learning costs from sqrt to cube root","Adaptive testers beat sqrt lower bound with cube-root queries","Cube-root exponent for two problems from one ball-distribution trick","Two classic problems get cube-root algorithms from one trick"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the prior coordinate-oracle theorem is exactly as strong as stated: it must reduce the n input coordinates to a poly(k,1/ε)-size set while preserving distance to the closest k-junta up to ε, and must give error-free access to the reduced dictator coordinates with only poly(log(q/δ)) overhead.","fun_headline_variants_meta":{"raw":{"variants":["One idea cuts testing and learning costs from sqrt to cube root","Adaptive testers beat sqrt lower bound with cube-root queries","Cube-root exponent for two problems from one ball-distribution trick","Two classic problems get cube-root algorithms from one trick"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001242,"raw_usage":{"total_tokens":5184,"prompt_tokens":1122,"completion_tokens":4062,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":738,"completion_tokens_details":{"reasoning_tokens":3993}},"tokens_in":738,"tokens_out":4062,"duration_ms":26829,"temperature":1.0,"reasoning_tokens":3993,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:11:03.478144+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a single family of Boolean functions for which every poly(k,1/ε)-coordinate reduction satisfying the stated oracle properties moves dist(f,J_k) by more than ε; then Algorithm 7's guarantee fails at its first step. More locally, a concrete counterexample to Claim 47 or Lemma 60—e.g., a junta whose high-level Fourier mass is concentrated on sets that evade every sampled C—would pinpoint exactly where the refinement argument breaks.","supporting_citations":[],"review_version":1}