{"id":"995a2368-69dc-4e28-ba0e-2eebfa0b6f3c","arxiv_id":"2509.02338","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Small-doubling subsets of F_2^n can now be covered by an explicit, efficiently learned subspace in polynomial time, with matching query lower bounds for classical and quantum algorithms.","lead":"This paper gives classical and quantum polynomial-time algorithms that extract the hidden subspace structure guaranteed by the 2025 Gowers, Green, Manners, and Tao Polynomial Freiman-Ruzsa theorem, using only O(log|A|) samples and few membership queries. If correct, it turns a landmark existential structure theorem into a usable algorithmic tool for theoretical computer science.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Classical Algorithmic PFR is a direct reduction to the unverified [BC25] quadratic Goldreich-Levin theorem; if [BC25]'s O(n^3) time excludes oracle-query cost or has hidden assumptions, the claimed O~(n^4) dequantized runtime collapses.","rationale":"The paper's own contribution is a clean chain: localize sparse A, construct a dense model, reduce to restricted homomorphism, then use quadratic Goldreich-Levin to learn an affine map. I checked the nontrivial algebra in Claims 3.5 and 3.6 and in Lemmas 3.3 and 3.4; the proofs are internally coherent. The dimension-accounting issue raised by the reader is a notational ambiguity: Lemma 3.4 is parameterized by the codomain dimension, so Theorem 4.1 may set that parameter to d = dim U, making the query count (m+d)^2 ~ log^2|A|. The cost of simulating S/f queries by enumerating ker(pi) is correctly counted as 2^{2K} queries to A. Thus no fatal internal gap is apparent. The genuine risk is external: the classical results are a reduction to [BC25]'s quadratic Goldreich-Levin theorem, a recent co-authored preprint. If its stated O(n^3) time is not compatible with its query count, or if its domain assumptions exclude the g used here, the central classical claim would need to be reproven. A concrete re-derivation and small-scale randomized test would settle this. Since this concern is already reflected in a CONDITIONAL verdict, I recommend no change.","tokens_in":23247,"tokens_out":36010,"duration_ms":416199,"concrete_test":"Independently re-derive Theorem 2.12 from [BC25] in the exact time model used by this paper: count oracle calls to the {-1,0,1}-valued g and the arithmetic work per call for N = m + d and epsilon = 1/(2P4(K)). Then recompute Lemma 3.4's total time as Q * O(N) plus [BC25]'s internal time. If the resulting exponent is K^{O(log K)} N^3 log N, Theorem 4.1 is sound; if an extra epsilon-dependent factor survives outside K^{O(log K)} (or if Theorem 2.12 requires Boolean f), the classical PFR runtime needs revision. A minimal computational check: run [BC25] on random quadratic-correlated functions for N = 16, 20, 24 with epsilon ~ 0.1 and verify that time scales as N^3 and query count as N^2 log N, independent of epsilon to the stated exponent.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central classical claim (Theorems 4.1, 4.3, 4.4) inherits all time and query bounds from one external tool: Theorem 2.12 ([BC25]). Lemma 3.4 applies it to the function g on N = m + d (d = dim U) at epsilon = 1/(2P4(K)) and states time K^{O(log K)}(m+n)^3 log(m+n). This is justified only if [BC25]'s O(n^3) time accounts for the (1/epsilon)^{O(log 1/epsilon)} oracle queries it makes, or if query cost is separately charged and multiplied by N per query. If [BC25]'s O(n^3) excludes query cost, the paper's bound may still absorb it, but if [BC25] has an additional epsilon-dependence in time or requires Boolean f rather than {-1,0,1}-valued g, the dequantization step fails. [BC25] is a recent preprint co-authored by one of the present authors and is not machine-checked, so it is the single load-bearing external assumption. The reader's separate dimension-accounting concern about Lemma 3.4 is not load-bearing: Lemma 3.4's 'n' is the codomain dimension, so instantiating it with d = dim U is legitimate and yields the O(log^2|A|) query bound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves algorithmic versions of the Polynomial Freiman-Ruzsa theorem. For A ⊆ F_2^n with doubling constant K, it gives a classical randomized algorithm that, with O(log|A| + K) random samples and 2^{O(K)} log^2|A| log log|A| queries to A, outputs a basis for a subspace V of size at most |A| such that A is covered by K^C translates of V; it also gives a quantum algorithm with quadratically better query complexity. The proof strategy is to avoid algorithmizing the entropic proof of GGMT by instead going through a dense model / Freiman-isomorphism reduction, proving an algorithmic restricted-homomorphism lemma, and using quadratic Goldreich-Levin type learning (classically via Briet--Castro-Silva, quantumly via stabilizer-state learning). The paper also proves query lower bounds of Ω(n^2) classically and Ω(n) quantumly.","tokens_in":23551,"tokens_out":27830,"duration_ms":298216,"significance":"If correct, the paper resolves the natural algorithmic version of PFR: the covering subspace can be learned in polynomial time for constant K, with essentially optimal query dependence on n. The reduction from PFR to learning quadratic/stabilizer structure is conceptually clean and likely to be influential. The paper is transparent about its black-box reliance on recent external results, and the main theorems are explicitly stated with sample, query, and time complexity. However, the classical half is wholly dependent on the unverified preprint [BC25], and several technical steps in the proofs of the central lemma and the lower bounds need correction. The qualitative claims are likely salvageable, but the manuscript in its current form is not yet sound in all details.","major_comments":[{"comment":"The procedure for finding z0 does not meet its stated guarantee. With estimation error ε = 1/(128 P4(K)^3), the candidate z0 from Claim 3.6 has estimated agreement at least 1/(64P4^3) − ε = 1/(128P4^3); the empirical maximizer z* has estimate at least that, so the true agreement of z* is only bounded below by 0, not by 2^m/(128P4^3). To obtain the claimed P'_4 = 128P4^3, the estimation error would need to be at most 1/(256P4^3). Additionally, an empirical-probability estimate to error ε requires Θ(1/ε^2) samples, so the stated O(log(K)P4(K)^3) samples per candidate should be O(log(K)P4(K)^6), changing the total in Lemma 3.4 to P4(K)^9 rather than P4(K)^6. These are K-dependent factors and do not change the qualitative theorem, but the proof of this central lemma is not correct as written.","section":"Lemma 3.4 / §3.4"},{"comment":"Fano's inequality is used in the wrong direction. For uniformly random H, Fano gives Pr[error] ≥ (H(H|H') − 1)/log|supp(H)|, hence Pr[success] ≤ (I(H:H') + 1)/log|supp(H)|. The manuscript instead writes Pr[identification] ≥ 1 − I/log|supp|, which would imply success probability near 1 for t = 0, contradicting the information-theoretic setup. With the correct inequality, the proofs can be repaired to give t = Ω(n^2) and t = Ω(n), but the displayed arguments as written are invalid.","section":"§5.1 and §5.2, Theorems 5.1/5.2"},{"comment":"The classical results inherit all time and query bounds from [BC25]. The theorem as stated has O(n^3) time and n^2 log n log(1/δ)(1/ε)^{O(log 1/ε)} queries; for ε = 1/poly(n) the query count is super-polynomial in n, so the O(n^3) time cannot include oracle-query cost in the usual unit-cost oracle model. The authors should state explicitly whether 'time' excludes oracle queries and, if so, add the cost of processing each query in Lemma 3.4 and Theorem 4.1. Since [BC25] is a recent preprint by one of the present authors and is load-bearing for all classical claims, the authors should either supply a proof of the exact theorem they use or give a precise statement with consistent time/query accounting.","section":"§2.3, Theorem 2.12; used in Theorems 4.1, 4.3, 4.4"}],"minor_comments":[{"comment":"The statement '|span(A)| ≤ 2^{2K/(2K)} · |A|' appears to be a typo; the proof later uses the standard bound |span(A)| ≤ 2^{2K}|A|. Please correct the displayed theorem.","section":"Theorem 2.4"},{"comment":"The substitution K' = 2^{33}K^{13} appears to be off by a factor of 2: Claim 4.2 and the bound |A'| ≥ 2^m/(2^{11}K^4) give denominator 2^{34}K^{13}. The constants do not affect the qualitative result, but should be checked.","section":"Theorem 4.1 proof"},{"comment":"All logarithms are implicitly base 2; please state this explicitly, since expressions like m = log|4A'| + 10 depend on the base.","section":"Throughout"},{"comment":"The paper claims random samples are information-theoretically necessary to hit a basis of A, but no formal sample lower bound is proved. The lower-bound section concerns queries; please clarify or move the sample-complexity remark to the discussion.","section":"§5"}],"recommendation":"major_revision","confidential_remarks":"The central classical claim is a reduction to [BC25], a preprint co-authored by one of the present authors. This is legitimate, but it increases the risk of an unverified load-bearing step. I recommend that the editor ask the authors to include a self-contained proof or a precise statement with consistent time/query accounting for the version of Theorem 2.12 they need. The paper's own prior work [AD25a, AD25b] is cited properly, and the main idea is strong; the issues in Lemma 3.4 and the lower bounds are local and repairable, so I do not see a reason to reject, but the manuscript needs a careful revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is the first algorithmic PFR theorem, with a genuinely new quantum route through stabilizer-state learning and a dequantized classical version, and it deserves a serious referee.\n\nWhat's new and good: Theorem 4.1 gives a poly(n) algorithm that outputs a small covering subspace for a bounded-doubling set, using few samples and queries, and Theorems 4.3–4.4 give algorithmic homomorphism testing and structured decomposition. The high-level strategy is non-obvious: prove a quantum version via [CGYZ25], then dequantize via [BC25]. The classical chain (Lemmas 3.1–3.4, Claims 3.5–3.6) is coherent and line-by-line checkable; external dependencies are disclosed. The lower bounds are simple but fine.\n\nSoft spots, in rough order:\n\n- The classical algorithm rests on [BC25, Thm 2.12] at full weight: all time and query bounds in Theorems 4.1, 4.3, and 4.4 inherit from it. That paper is a recent preprint, one of the present authors is a coauthor, and it is not machine-checked. I would want an independent check of its O(n^3) time and the query-to-time accounting before betting the dequantization on it. If its time is actually larger, the O~(n^4) claim weakens.\n\n- The reader's flagged dimension issue in Lemma 3.4 is not a real gap. Lemma 3.4's n is the codomain dimension, so applying it with n = dim U to get O~(log^2 |A|) queries is legitimate.\n\n- The final selection step in Theorem 4.1 (Step 4) is under-specified. \"Take a subspace V of Im(psi) of size at most |A|\" does not by itself give a polynomial cover by translates of V. You need to choose V so that |Im(psi)|/|V| is polynomial; since |Im(psi)| <= 2^m = O(K^4|A|), such a V exists, and the argument is fixable, but it should be written out.\n\nMinor: the algorithm in Lemma 3.4 for finding z0 samples x uniformly from F_2^m and writes d(x) = f(x) - ..., but f is only defined on S; the intended meaning is \"if x in S then compute d(x), else discard\"—easy to fix, worth a clarifying sentence.\n\nWho this is for: additive combinatorics and TCS readers who want a constructive PFR; also quantum learning readers following the stabilizer-state connection. I would bring it to a reading group and I would cite it. My recommendation: send it to a serious referee, and ask for the [BC25] dependency and the Step 4 argument to be tightened before publication.","headline":"First constructive PFR, worth a serious referee; the classical part leans on one unverified preprint and one under-specified final step, both fixable.","tokens_in":24099,"tokens_out":5819,"would_cite":true,"duration_ms":64905,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11B30","11B75","68Q12","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The Polynomial Freiman-Ruzsa theorem is made algorithmic: a bounded-doubling set A⊆F_2^n yields a learnable subspace V, |V|≤|A|, covering A by K^C translates.","keywords":["algorithmic Polynomial Freiman-Ruzsa","additive combinatorics over F_2^n","subspace covering","quadratic Goldreich-Levin","stabilizer states and Gowers U^3 norm","quantum algorithms and dequantization","homomorphism testing","query lower bounds"],"falsifier":"Run the quadratic Goldreich-Levin routine [BC25] on a known quadratic phase function for n from about 50 to 400 and compare the empirical scaling of query count and runtime with n^2 log n and n^3; if the observed growth exceeds the stated bounds by an unbounded factor, the classical PFR theorem loses its polynomial guarantee. Alternatively, search for a set A with |A+A|≤K|A| that requires more than K^C translates of any subspace of size at most |A| for every fixed C; such a set would refute the base PFR statement itself.","tokens_in":23092,"feed_emoji":"🧮","tokens_out":7561,"duration_ms":84683,"temperature":0.7,"pith_summary":"Sets that only double under addition are known, by the Polynomial Freiman-Ruzsa theorem, to be coverable by few translates of a subspace no larger than the set. That theorem has been existential: extracting the subspace by brute force costs exponential time. This paper makes it constructive, proving that a basis for such a subspace can be learned in polynomial time from a tiny number of random samples and membership queries to the set, in both classical and quantum settings. The consequences are structural: local approximate linearity becomes testable and the affine map that explains it can be learned, and approximate homomorphisms admit efficiently computable decompositions. The gains hold even after accounting for matching (up to log factors) lower bounds on queries.","feed_headline":"Learning the PFR subspace now takes polynomial time","feed_subtitle":"For bounded-doubling sets A in F_2^n, algorithms recover a covering subspace from few samples and queries.","key_machinery":"The workhorse function is g(x,y)=1_S(x)(-1)^{f(x)·y}, built from a dense Freiman model S⊆F_2^m of A after a random linear projection; if A has small doubling, g is guaranteed to have large inner product with some quadratic phase (-1)^{q(x,y)}. That quadratic q is found by the quadratic Goldreich-Levin learner [BC25] classically, or by the stabilizer-state agnostic learner [CGYZ25] quantumly. Extracting the mixed second difference B(x,y)=q(x,y)-q(x,0)-q(0,y)+q(0,0) gives a matrix M with B(x,y)=y^T M x, and Fourier analysis upgrades the correlation to the conclusion f(x)=Mx+v on a constant fraction of the dense model; Ruzsa's covering lemma turns that into a cover of A by few translates of the","core_discovery":"On the paper's own terms, the central claim is Theorem 4.1: for any A⊆F_2^n with |A+A|≤K|A|, a randomized algorithm draws O(log|A|+K) random elements from A, makes 2^{O(K)} log^2|A| log log|A| queries to the membership oracle of A, and runs in K^{O(log K)} n^4 log n time; with probability at least 2/3 it returns a basis for a subspace V of size at most |A| such that A is covered by P_1'(K) translates of V. A quantum version achieves O(n^3) time and 2^{O(K)} log|A| quantum queries. The paper also proves algorithmic homomorphism testing: any map f:F_2^m→F_2^n that satisfies f(x_1)+f(x_2)=f(x_3)+f(x_4) on at least 1/K of its additive quadruples is close in fractional Hamming distance to an affi","pith_inferences":["The K-dependence (2^{O(K)} queries and K^{O(log K)} time) is treated as constant in the asymptotic guarantees; an obvious next step, left open here, is a version whose complexity is polynomial in K, which would cover sets whose doubling constant grows slowly with n.","The sampling/localization plus dense-model pipeline is not obviously restricted to F_2: the same ingredients exist in other finite fields and abelian groups, so an analogous algorithmic PFR may hold wherever a quadratic Goldreich-Levin analogue exists.","If the dequantized quadratic Goldreich-Levin routine [BC25] were improved further, the entire classical O(n^4) bound would improve automatically; conversely, the lower-bound argument shows the overall route cannot be made subquadratic in n queries.","Applications that use PFR as a black box—such as sparsification algorithms or extractor constructions—could be re-examined with the explicit subspace in hand, potentially turning existence proofs into reductions with actual running time."],"forward_implications":["If A has constant doubling K, a basis for the covering subspace can be found in O(n^4 log n) classical time, so applications of PFR that currently need a non-constructive cover can in principle use explicit covers.","Homomorphism testing becomes effective: any map that is 1/K close to affine-linearity locally can be certified and its affine approximation learned, with consequences for property testing and coding settings.","The structured approximate homomorphism result gives an explicit decomposition f=g+h into a linear part and a small-image part whenever the derivative image is small.","The Ω(n^2) classical and Ω(n) quantum query lower bounds mean the query dependence on n is settled up to logarithmic factors, so further improvement must come from the K-dependence rather than from n.","Quantum algorithms save a factor n in time and a factor log n in queries, matching the known quantum-vs-classical gap for these learning tasks."],"supporting_citations":[{"why":"Supplies the combinatorial PFR theorem, the non-constructive statement whose algorithmic version is the paper's target.","marker":"[GGMT25]"},{"why":"Provides the near-optimal quadratic Goldreich-Levin algorithm that all classical time and query bounds inherit through the dequantization step.","marker":"[BC25]"},{"why":"Provides the agnostic stabilizer-state learning algorithm that drives the quantum PFR and the Gowers-U^3 route.","marker":"[CGYZ25]"},{"why":"Gives the equivalence between inverse sumset theorems and U^3 inverse theorems, whose proof route is algorithmized here.","marker":"[GT10]"},{"why":"Shows the equivalence of polynomial Freiman-Ruzsa-type conjectures, used to pass between combinatorial and analytic formulations.","marker":"[Lov12]"},{"why":"Provides the Freiman-Ruzsa theorem bounding span(A), used for localizing sparse sets and controlling |V|.","marker":"[Ruz99]"},{"why":"Supplies Plünnecke's inequality and Ruzsa's covering lemma used in the final covering argument.","marker":"[TV06]"},{"why":"Supplies the information-theoretic query lower-bound argument adapted to prove the Ω(n^2) classical and Ω(n) quantum bounds.","marker":"[Mon12]"}],"fun_headline_variants":["PFR theorem goes algorithmic — poly time and quantum","Polynomial-time learning of Freiman-Ruzsa subspaces","Classical and quantum algorithms for PFR covering","Efficient covering subspace discovery for bounded doubling","From theorem to algorithm: PFR in poly time"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The classical speed limits are inherited wholesale from the cited quadratic Goldreich-Levin subroutine [BC25], with the quantum results separately leaning on the cited stabilizer-state learner [CGYZ25]; if either runs slower than stated, the corresponding PFR algorithms slow down in lockstep.","fun_headline_variants_meta":{"raw":{"variants":["PFR theorem goes algorithmic — poly time and quantum","Polynomial-time learning of Freiman-Ruzsa subspaces","Classical and quantum algorithms for PFR covering","Efficient covering subspace discovery for bounded doubling","From theorem to algorithm: PFR in poly time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000215,"raw_usage":{"total_tokens":1246,"prompt_tokens":708,"completion_tokens":538,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":452,"completion_tokens_details":{"reasoning_tokens":463}},"tokens_in":452,"tokens_out":538,"duration_ms":5731,"temperature":1.0,"reasoning_tokens":463,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T11:40:41.333486+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the quadratic Goldreich-Levin routine [BC25] on a known quadratic phase function for n from about 50 to 400 and compare the empirical scaling of query count and runtime with n^2 log n and n^3; if the observed growth exceeds the stated bounds by an unbounded factor, the classical PFR theorem loses its polynomial guarantee. Alternatively, search for a set A with |A+A|≤K|A| that requires more than K^C translates of any subspace of size at most |A| for every fixed C; such a set would refute the base PFR statement itself.","supporting_citations":[],"review_version":1}