{"id":"3e68ee6d-170e-46e9-9e98-5ce81de0e16c","arxiv_id":"2508.09422","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"A new classical algorithm solves noisy planted kXOR quadratically faster than the previous best classical method for large constant k, cutting the known quantum speedup from quartic to quadratic.","lead":"This paper gives a new classical algorithm for the noisy planted kXOR problem that runs quadratically faster than the previous best classical algorithm when k is a large constant. It matters because it shrinks the known quantum speedup for this problem from quartic to quadratic, helping map when quantum computers genuinely beat classical ones.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The quadratic speedup rests on an unproved anticoncentration bound for the noisy kXOR polynomial; if its constants degrade in k or at the algorithm's noise level, the runtime exponent and the claimed speedup collapse.","rationale":"I read the paper as making a falsifiable runtime claim: a new classical algorithm is quadratically faster than the best prior classical algorithm for noisy planted kXOR with large constant k. The strongest point in the abstract is the novelty of combining birthday-paradox subsampling with polynomial anticoncentration; the weakest point is that the anticoncentration lemma is only named, not stated. Everything—the sample complexity, the false-positive control, and the final exponent—depends on the exact constants in that lemma. If the lemma holds with the constants needed, the claim is plausible; if it degrades in k or fails at the algorithm's operating noise, the runtime collapses. This is exactly the premise the reader identified, and I agree with that assessment. I do not have the full text, so I cannot determine whether the lemma is correct. Thus no change to the reader's UNVERDICTED verdict is warranted. If the full text passes the concrete test above, the verdict should move toward CONDITIONAL; if it fails, the verdict should be REJECT. Neither adjustment is possible from the abstract alone, so UNCHANGED is the honest output.","tokens_in":809,"tokens_out":5194,"duration_ms":62170,"concrete_test":"Open the full text and locate the anticoncentration theorem and the runtime theorem. Then: (1) instantiate k=4 and k=6 at the maximal noise level η allowed by the theorem; simulate 10^4 runs of the birthday-subsampling subroutine on n=2^14 variables, counting the fraction of x≠x* with |F(x)| within a factor 1/2 of the planted signal. If the empirical false-positive probability exceeds the theorem's failure probability at the chosen sample size, the lemma's constants are wrong. (2) Independently re-derive the end-to-end runtime formula with the lemma's constants and compare it to the named baseline; if the exponent difference is not exactly a factor of two for these k, the abstract's 'quadratically faster' claim is not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is a tight comparison of runtimes: the new classical algorithm is supposed to improve quadratically on the best previous classical algorithm for noisy planted kXOR with large constant k. The described mechanism combines birthday-paradox subsampling with a random polynomial F(x)=Σ y_i χ_{S_i}(x) whose expectation is m(1-2η) at the planted vector x* and zero elsewhere. To make the search succeed, the algorithm needs a quantitative anticoncentration estimate: with high probability, every x≠x* has |F(x)| well below m(1-2η), so no false positive beats the planted signal. The abstract states only that such polynomial anticoncentration is used; it gives neither the lemma nor the constants. The load-bearing concern is that this bound may have a hidden dependence on k or η. For instance, if the variance of F(x) over random equation selection is 2^k times larger than claimed, or if the tail bound fails below the subsampling rate chosen by the birthday argument, then the sample size will not separate the planted point from the best false positive. The claimed semirandom extension makes this worse, since an adversary can correlate equations and break the anticoncentration estimate. Because the conclusion is an exponent-level speedup, any polynomial factor in k in the hidden constants can change the comparison in the intended 'large constant k' regime. The abstract also never names the baseline algorithm or its runtime, so the claimed quadratic factor cannot be audited from the provided text. This is not a detected error; it is the precise condition that must hold for the abstract's sentence to be true.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims a new classical algorithm for the noisy planted kXOR problem in the regime of large constant k. The algorithm is said to be quadratically faster than the best previous classical algorithm, using tools from sublinear-time algorithms (birthday paradox) and polynomial anticoncentration. As a consequence, the quantum speedup of Schmidhuber et al. (QIP, SODA, PRX 2025) would shrink from quartic to quadratic, while preserving a space advantage for the quantum side. The abstract also states that the algorithm works in the semirandom case. No precise theorem statements, runtime bounds, or parameter conditions are given in the abstract; the full text was not available for this review.","tokens_in":1058,"tokens_out":2965,"duration_ms":31916,"significance":"If the claimed quadratic speedup is correct and holds for large constant k with explicit constants, this is a meaningful advance in the classical complexity of noisy planted kXOR and in the understanding of quantum speedups for this problem. Reducing a claimed quartic quantum speedup to quadratic is a significant structural result, and the semirandom extension would broaden its applicability. The paper's approach -- combining birthday-paradox subsampling with polynomial anticoncentration -- is plausible and potentially interesting. However, because the technical content is not accessible here, the significance cannot be fully assessed. The central claim is precise and falsifiable, which is a strength, but the lack of a stated theorem and proof in the visible material prevents verification.","major_comments":[{"comment":"The claim \"quadratically faster than the best previous one\" is not auditable because no baseline algorithm is named and no runtime bounds are given. A quadratic speedup is an exponent-level statement; the abstract must state the previous best runtime (e.g., T_old(n,m,k,η)) and the new runtime (T_new(n,m,k,η)) so that the comparison can be checked. Without these, the central claim is unverifiable.","section":"Abstract (first sentence of the contribution)"},{"comment":"The correctness of the algorithm rests on a quantitative anticoncentration bound separating the planted vector from all false positives. The abstract provides neither the bound nor its dependence on k and noise η. If the bound's constants degrade in k or fail at the subsampling rate used by the birthday argument, the sample-size separation collapses and the runtime exponent is not achieved. A precise anticoncentration lemma with explicit constants and the parameter regime in which it holds is load-bearing and must be stated.","section":"Abstract (\"polynomial anticoncentration\" tool)"},{"comment":"In a semirandom model, an adversary can introduce correlations across equations, which can invalidate the independence assumptions underlying the anticoncentration estimate. The abstract gives no specification of the semirandom model or the conditions under which the anticoncentration bound survives adversarial perturbations. Without a formal model and proof, the semirandom claim is unsupported and potentially in tension with the anticoncentration mechanism.","section":"Abstract (\"also works in the semirandom case\")"},{"comment":"\"Large constant k\" and \"noisy\" are not quantified. Since the speedup is claimed for large constant k, the hidden dependence of the runtime on k is essential: a polynomial factor in k inside an exponential or in a subexponential exponent can change the comparison in the intended regime. The paper should state a theorem with explicit conditions, e.g., k ≥ k0, η ≤ η0, and a runtime bound of the form O(f(k,n,m,η)) with the dominating term exposed.","section":"Abstract (parameter regime)"}],"minor_comments":[{"comment":"The reference to Schmidhuber et al. is by author name and venue but no full citation or arXiv identifier is given in the abstract. Please provide a reference in the abstract or in the first paragraph of the introduction so that readers can locate the baseline.","section":"Abstract (first paragraph)"},{"comment":"The phrase \"the quantum speedup ... becomes only quadratic\" could be read as a universal claim. It is more precise to say \"the speedup over this classical algorithm is quadratic\" or \"the best known classical algorithm achieves a quadratic speedup over the quantum algorithm\" to avoid overstatement.","section":"Abstract (last sentence)"},{"comment":"The terms \"birthday paradox\" and \"polynomial anticoncentration\" are named but not connected to specific sections or equations. If the full paper has such structure, please include pointers (e.g., 'Sections 4 and 5') for navigability.","section":"Abstract (tools)"}],"recommendation":"uncertain","confidential_remarks":"The manuscript was provided as abstract-only; I could not inspect the proofs, the numerical constants, or the precise theorem statements. The central claim is interesting and potentially publishable if the technical analysis is correct. However, the abstract alone does not provide enough substance for a definitive recommendation. I strongly recommend obtaining the full text for a thorough review. The stress-test concern about anticoncentration constants is well placed based on the abstract's silence on that bound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version. If the algorithm is what the abstract says, this is a real result: a new classical algorithm for noisy planted kXOR that is quadratically faster than the previous best for large constant k, cutting the quantum speedup Schmidhuber et al. reported from quartic to quadratic. The combination of birthday-paradox sampling and polynomial anticoncentration is a plausible way to get there, and the semirandom extension is a nice bonus. It is not a restatement of the quantum paper; the comparison is to an unnamed classical baseline.\n\nThe honest problem is that the abstract cannot carry this weight. The runtime bounds aren't stated, the baseline algorithm isn't named, and the anticoncentration lemma is just called a tool. Since the claim is an exponent-level speedup, any hidden factor in k in the anticoncentration constants could change the comparison in the large-constant-k regime. The semirandom part worries me more: an adversary can correlate equations, and anticoncentration estimates for the random polynomial typically rely on independence. If the bound degrades badly with k or with the noise level, the sample size won't separate the planted vector from the best false positive.\n\nI want to be clear: I'm not saying the paper is wrong. The stress-test note correctly frames this as the condition that must hold, not a detected defect. The abstract is unusually thin on the technical content, which is why my confidence stays low. Given the authors' track record and the importance of the question, I would not desk-reject it. A serious referee should check three things: the anticoncentration lemma's dependence on k and eta, the birthday-paradox sample size against the signal-to-noise ratio, and the baseline algorithm's actual runtime. If those check out, this is a strong paper.\n\nWho's it for? People working on planted CSPs, sublinear algorithms, and quantum advantage. It deserves a serious referee.\n\nMy recommendation: send it to peer review, not because I'm convinced, but because the potential significance is high and the issues are checkable, not fatal.","headline":"A credible, potentially important classical speedup for planted kXOR, but the abstract hides the anticoncentration constants and the baseline runtime; needs full-text refereeing.","tokens_in":1627,"tokens_out":2188,"would_cite":true,"duration_ms":21197,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper presents a classical algorithm for noisy planted $k$XOR that is quadratically faster than the best previous classical method for large constant $k$, which cuts the quantum speedup of Schmidhuber et al. from quartic to quadratic.","keywords":["planted kXOR","quantum speedup","classical algorithm","birthday paradox","polynomial anticoncentration","semirandom","sublinear-time algorithms","average-case complexity"],"falsifier":"Fix a specific large constant $k$ and a noise level, then compute the relevant anticoncentration constant (such as the fourth moment) of the noisy planted $k$XOR polynomial used by the algorithm and compare it with the threshold the analysis requires; if the constant falls below that threshold, the polynomial test cannot certify the planted signal and the claimed runtime collapses. Alternatively, run the birthday-paradox subsampling step on a concrete planted instance and measure whether the signal-to-noise ratio remains above the level needed for the subsequent polynomial step.","tokens_in":636,"feed_emoji":"⚡","tokens_out":3733,"duration_ms":39137,"temperature":0.7,"pith_summary":"The paper tackles the noisy planted $k$XOR problem, where a random $k$-variable XOR formula is hidden in noise and the goal is to recover a planted assignment that satisfies more constraints than a random one. A recent quantum algorithm solved this problem quartically faster than every known classical algorithm. The paper's central claim is that, for large constant $k$, this quantum gap is not necessary: a new classical algorithm, built from birthday-paradox subsampling and polynomial anticoncentration, runs quadratically faster than the best previous classical algorithm. If the analysis is correct, the quantum speedup for this problem drops from quartic to quadratic, with the quantum algorithm retaining only a space advantage. The algorithm also works in the semirandom case, where noise is chosen adversarially.","feed_headline":"Quantum edge for planted kXOR cut to quadratic","feed_subtitle":"A new classical algorithm with birthday-paradox sampling runs quadratically faster, leaving quantum only a space advantage.","key_machinery":"Birthday-paradox subsampling: randomly select a small set of constraints so that variable collisions occur with constant probability, yielding low-width subproblems that are cheap to solve. Polynomial anticoncentration: a quantitative bound showing that the random polynomial arising from the noisy planted $k$XOR instance has moments large enough to certify the planted signal rather than being overwhelmed by noise. The two work together to replace the more expensive search of earlier classical algorithms with a collision-based, sample-efficient method.","core_discovery":"For noisy planted $k$XOR with large constant $k$, the authors construct a classical algorithm that improves the best prior classical runtime by a quadratic factor. The algorithm combines two ingredients: birthday-paradox subsampling, which efficiently finds small correlated subsets of constraints, and polynomial anticoncentration, which shows that the noisy $k$XOR polynomial does not concentrate too tightly around its mean, so the planted signal can be detected and extracted. This improvement directly shrinks the speedup of the quantum algorithm of Schmidhuber et al. from quartic to quadratic, while the quantum method still uses less space. The same construction extends to the semirandom set","pith_inferences":["If the required anticoncentration constant degrades with the parameter $k$, the quadratic speedup may only hold for a narrow range of 'large constant $k$'; checking the $k$-dependence of the bound is a natural next step.","The same birthday-paradox-plus-anticoncentration recipe could transfer to other planted high-arity constraint satisfaction problems, such as planted $k$SAT or random $k$XOR under different noise models, yielding analogous classical speedups.","The classical improvement suggests the earlier quartic gap may have been an artifact of incomplete classical analysis rather than a fundamental separation; a testable corollary is whether further classical improvements are possible for small $k$, a regime this method does not cover.","Because the quantum side retains a space advantage, a concrete benchmark for follow-up work is whether a classical algorithm with comparable space usage can close the remaining quadratic gap or achieve a time-space tradeoff."],"forward_implications":["For large constant $k$, the quantum algorithm of Schmidhuber et al. is only quadratically faster than the new classical algorithm, not quartically.","The quantum algorithm still retains a space advantage over the new classical one, so quantum resources may still be useful when space is limited.","The new classical algorithm also applies to the semirandom planted $k$XOR variant, where noise can depend on the planted solution adversarially.","The result narrows a prominent quantum-classical gap on a canonical average-case problem, which informs where quantum speedups are robust versus where they reflect missing classical technique.","It demonstrates that sublinear-time techniques, here the birthday paradox, can combine with polynomial anticoncentration to yield provable classical speedups in planted constraint problems."],"supporting_citations":[{"why":"Supplies the quantum algorithm whose quartic speedup over all classical methods is the baseline the paper aims to reduce; the paper's central claim is that this speedup shrinks to quadratic.","marker":"Schmidhuber et al. (QIP, SODA, & Phys. Rev. X 2025)"}],"fun_headline_variants":["Quantum kXOR edge cut from quartic to quadratic","Classical birthday paradox narrows quantum kXOR lead","Quadratic classical speedup shrinks quantum kXOR lead"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The runtime improvement depends on a polynomial anticoncentration bound for the noisy planted $k$XOR polynomial holding with the right constants at the algorithm's noise level and sampling rate; if that constant degrades in $k$ or the subsampling washes out the planted signal, the claimed quadratic speedup does not materialize.","fun_headline_variants_meta":{"raw":{"variants":["Quantum kXOR edge cut from quartic to quadratic","Classical birthday paradox narrows quantum kXOR lead","Quadratic classical speedup shrinks quantum kXOR lead"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001088,"raw_usage":{"total_tokens":4327,"prompt_tokens":634,"completion_tokens":3693,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":378,"completion_tokens_details":{"reasoning_tokens":3639}},"tokens_in":378,"tokens_out":3693,"duration_ms":26497,"temperature":1.0,"reasoning_tokens":3639,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T21:03:41.736008+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix a specific large constant $k$ and a noise level, then compute the relevant anticoncentration constant (such as the fourth moment) of the noisy planted $k$XOR polynomial used by the algorithm and compare it with the threshold the analysis requires; if the constant falls below that threshold, the polynomial test cannot certify the planted signal and the claimed runtime collapses. Alternatively, run the birthday-paradox subsampling step on a concrete planted instance and measure whether the signal-to-noise ratio remains above the level needed for the subsequent polynomial step.","supporting_citations":[],"review_version":1}