{"id":"32d53f08-0bf2-4738-830d-2c9f402f3859","arxiv_id":"2605.00995","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Constant-degree polynomial samplers over F_2^m produce distributions at total variation distance 1-o(1) from Ber(1/3)^⊗n, with concrete bounds for d=1,2,3 and a supporting lemma that no degree-d polynomial has bias exactly 1/3.","lead":"The paper proves that distributions generated by evaluating constant-degree polynomials over F_2 cannot approximate the product distribution Ber(1/3)^n in total variation distance, with explicit rates for small degrees. This extends prior lower bounds on sampling from local functions and shallow circuits to algebraic samplers.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's identification of the structural theorem and bias lemma is accurate as the technical core, but the high-level architecture (inductive reduction via bounded-support structure) closes the gap between constant marginal deviation and the stronger 1-o_n(1) claim without circularity or unsupported steps. The explicit rates for small d are consistent with parameter loss in the induction and do not indicate a flaw. The fact that an elementary proof of the bias lemma was previously unknown does not, by itself, constitute a load-bearing risk once the structure-based argument is supplied.","tokens_in":2080,"tokens_out":437,"duration_ms":168865,"concrete_test":"For d=2, enumerate all quadratic polynomials over F_2^m for m≤8 (feasible via exhaustive search over the 2^{O(m^2)} space restricted to degree ≤2) and compute min |Pr[P=1]-1/3|; confirm it is bounded below by a positive constant independent of m, matching the claimed δ_2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that any degree-d polynomial sampler induces a distribution at TV distance 1-o_n(1) from Ber(1/3)^⊗n, with the bias lemma (any degree-d polynomial has |Pr[P=1]-1/3|≥δ_d>0) proved via the structural theorem that biased degree-d polynomials are functions of a bounded number of degree-(d-1) polynomials. This structure limits effective support size, yielding only finitely many possible Pr values for fixed d (none equal to 1/3), hence positive δ_d. The sampling lower bound then follows by induction on d, with quantitative rates obtained from the resulting recurrence on the structure depth. The argument is internally consistent: the marginal-deviation lower bound of δ_d is strengthened to 1-o_n(1) because low-degree constraints prevent dependence patterns that could keep TV bounded away from 1 for large n. No gap in the application of the structural theorem or in the induction is apparent.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript claims that any distribution over {0,1}^n generated by n degree-d polynomials over F_2 (evaluated on uniform random input) has total variation distance 1-o_n(1) from Ber(1/3)^⊗n for constant d. Explicit quantitative lower bounds are stated for d=1 (1-exp(-Ω(n))), d=2 (1-exp(-Ω(log n / log log n))), and d=3 (1-exp(-Ω(√log log n))). A supporting bias lemma asserts that no degree-d polynomial P satisfies |Pr[P=1]-1/3| < δ_d for a positive constant δ_d = δ_d > 0; the lemma is proved by invoking structural theorems that express biased degree-d polynomials as functions of a bounded number of degree-(d-1) polynomials, which in turn limits the possible bias values and enables an inductive argument on d to obtain the TV bounds.","tokens_in":2297,"tokens_out":536,"duration_ms":43417,"significance":"If the central claims hold, the work extends the line of sampling lower bounds (building on Viola 2012) from local functions, decision trees, and circuits to constant-degree polynomial samplers, showing that even this model cannot approximate the target product distribution. The bias lemma is of independent interest for the analysis of Boolean functions, as it rules out bias exactly 1/3 for low-degree polynomials via structural decomposition rather than direct calculation. The explicit rates for small d are a concrete strength, and the argument is internally consistent once the structural theorems are applied to the specific bias target.","major_comments":[],"minor_comments":[{"comment":"The abstract states that an elementary proof of the bias lemma was previously unknown; the manuscript should briefly note in the introduction or §1 why the structural-theorem approach qualifies as non-elementary or what alternative elementary routes were considered.","section":null},{"comment":"The quantitative bounds for d=2 and d=3 arise from a recurrence on structure depth; a short paragraph or table summarizing the recurrence parameters and how they yield the stated exponents would improve readability.","section":null},{"comment":"Notation: the o_n(1) term is defined as vanishing for fixed d as n→∞; adding an explicit sentence in the introduction confirming that δ_d is independent of n and m would prevent any ambiguity about uniformity.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript fits well within the scope of a complexity-theory venue; the reliance on prior structural results is properly cited and does not appear to overstate novelty."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their positive assessment and recommendation to accept the manuscript. Their summary correctly captures the main results on total variation distance lower bounds for constant-degree polynomial samplers from Ber(1/3)^⊗n, the explicit quantitative bounds for small d, and the supporting bias lemma for low-degree polynomials over F_2.","responses":[],"tokens_in":1662,"tokens_out":81,"duration_ms":15910,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main result is that any n-bit sampler built from degree-d polynomials over F2 has total variation distance 1-o(1) from the product Ber(1/3)^n, for fixed d. They give concrete rates: 1-exp(-Omega(n)) for d=1, 1-exp(-Omega(log n / log log n)) for d=2, and 1-exp(-Omega(sqrt(log log n))) for d=3. As a side result they show that no single degree-d polynomial can have bias within delta_d of 1/3 for some positive delta_d depending only on d.","headline":"Polynomial samplers of constant degree stay far from the Ber(1/3) product distribution, with explicit TV rates for d=1,2,3 and a supporting bias lemma.","tokens_in":2800,"tokens_out":208,"would_cite":false,"duration_ms":18127,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Any distribution generated by n degree-d polynomials over F_2 is at least 1-o(1) far in total variation from the product of n independent Ber(1/3) random variables.","keywords":["low-degree polynomials","sampling lower bounds","total variation distance","product Bernoulli distribution","bias lemma","F_2","structural theorem","complexity of distributions"],"falsifier":"An explicit construction of degree-d polynomials P_1 to P_n where the output distribution has total variation distance o(1) to Ber(1/3)^⊗n for large n.","tokens_in":2979,"feed_emoji":"","tokens_out":594,"duration_ms":28954,"temperature":0.7,"pith_summary":"The paper establishes lower bounds on how well low-degree polynomial functions can sample from a product distribution. Specifically, evaluating n polynomials of fixed degree d on a uniform random input from F_2^m produces a distribution on {0,1}^n whose total variation distance to Ber(1/3) raised to n is 1 minus a small term that goes to zero only as n increases. This holds because each individual polynomial cannot have its acceptance probability too close to 1/3, and this bias propagates. A reader would care because it shows fundamental limitations of algebraic methods in generating nearly independent biased bits, extending known barriers from circuit and local samplers.","feed_headline":"Polynomial samplers miss Ber(1/3) product by 1-o(1)","feed_subtitle":"Distributions induced by degree-d polynomials on F_2 stay 1-o(1) far in TV distance from independent 1/3-biased bits, with concrete bounds.","key_machinery":"The structural theorem for low-degree polynomials over F_2 stating that any biased degree-d polynomial can be written as a function of a small number of degree-(d-1) polynomials, used to bound the bias inductively.","core_discovery":"When P is an n-tuple of degree-d polynomials from F_2^m to F_2, the induced distribution on {0,1}^n satisfies ||P - Ber(1/3)^⊗n||_TV = 1 - o_n(1) for any constant d. For d=1 the distance is at least 1 - exp(-Omega(n)), for d=2 at least 1-exp(-Omega(log n / log log n)), and for d=3 at least 1-exp(-Omega(sqrt(log log n))). This relies on proving that for any degree-d polynomial Q, Pr[Q(X)=1] is bounded away from 1/3 by some absolute constant delta_d >0.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Degree-d polynomial samplers stay 1-o(1) TV distant from Ber(1/3) product","Low-degree polys induce 1-o(1) TV distance from Ber(1/3) product","Degree d polynomials are 1-o(1) TV far from Ber(1/3) bit product","Fixed degree polynomial distributions show TV gap of 1-o(1) to Ber(1/3)"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The structural theorem that any biased degree-d polynomial over F_2 can be written as a function of a small number of degree-(d-1) polynomials holds.","fun_headline_variants_meta":{"raw":{"variants":["Degree-d polynomial samplers stay 1-o(1) TV distant from Ber(1/3) product","Low-degree polys induce 1-o(1) TV distance from Ber(1/3) product","Degree d polynomials are 1-o(1) TV far from Ber(1/3) bit product","Fixed degree polynomial distributions show TV gap of 1-o(1) to Ber(1/3)"]},"model":"grok-4.3","cost_usd":0.012672,"raw_usage":{"total_tokens":5691,"prompt_tokens":1029,"num_sources_used":0,"completion_tokens":104,"cost_in_usd_ticks":126724500,"prompt_tokens_details":{"text_tokens":1029,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":4558,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":1029,"tokens_out":104,"duration_ms":39514,"temperature":1.0,"reasoning_tokens":4558,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-09T14:29:16.441297+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit construction of degree-d polynomials P_1 to P_n where the output distribution has total variation distance o(1) to Ber(1/3)^⊗n for large n.","supporting_citations":[],"review_version":1}