{"id":"457fb34b-d5ba-4d6e-92c7-5382f5bb22ec","arxiv_id":"2607.05944","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.5,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An Õ(Ω(n²)) lower bound for read-once parity branching programs is obtained by reducing to algebraic circuit lower bounds for an explicit function.","lead":"This paper proves a nearly quadratic lower bound for read-once parity branching programs on an explicit Boolean function, improving the previous best of roughly n to the 1.5. It does so by reducing the branching-program question to a known hardness result in algebraic circuit complexity.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"The claimed Õ(Ω(n²)) bound stands or falls with a size-preserving reduction to an unconditional algebraic-circuit lower bound of matching strength; any super-polylog overhead or conditional algebraic hardness collapses the quantitative improvement.","rationale":"The reader correctly isolated the only load-bearing assumption: the reduction must preserve size up to polylog factors and must invoke an unconditional algebraic lower bound of the required strength. No deeper internal inconsistency (circularity, misapplication of a known theorem, or hidden parameter dependence) is visible from the claim structure itself; the argument is a pure reduction. Because the full text was not independently re-derived here, the same verification steps remain necessary, so the UNVERDICTED/LOW-confidence status is unchanged. The concrete test above settles the issue in either direction without requiring new mathematics.","tokens_in":1896,"tokens_out":555,"duration_ms":35239,"concrete_test":"Locate the reduction lemma and the precise algebraic lower-bound theorem cited in the paper. Compute the concrete size overhead factor f(s,n) that the reduction produces. Substitute the best unconditional algebraic lower bound L(n) available for the target polynomial; the resulting RO-PBP bound is L(n)/f(s,n). If this quantity is o(n²/polylog n), the headline Õ(Ω(n²)) claim does not hold.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is obtained solely by reduction from read-once parity branching programs to algebraic circuits. For the Boolean lower bound to be Õ(Ω(n²)) and unconditional, two conditions must hold simultaneously: (1) a size-s RO-PBP must map to an algebraic circuit of size at most s·polylog(n) (or at worst s·n^{o(1)}) computing an explicit hard polynomial, and (2) that polynomial must already possess an unconditional algebraic-circuit lower bound of strength Õ(Ω(n²)). The abstract asserts both, yet the previous RO-PBP bound of Õ(Ω(n^{1.5})) suggests that earlier reductions either incurred larger overhead or invoked weaker algebraic sources. If the present reduction multiplies size by n^ε for any fixed ε>0, or if the algebraic lower bound is only known under additional hypotheses (e.g., for permanent under VP≠VNP, or only for restricted circuit classes whose restrictions are not preserved), the Boolean claim fails to improve on n^{1.5}. This is the single point on which the entire quantitative statement rests.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper proves an Õ(Ω(n²)) size lower bound for read-once parity branching programs (RO-PBPs) computing an explicit Boolean function on n variables, improving the previous best bound of Õ(Ω(n^{1.5})). The argument proceeds by a size-preserving reduction from RO-PBPs to algebraic circuits, transferring an existing unconditional algebraic-circuit lower bound of matching strength to the Boolean model. The hard function is obtained from an explicit hard polynomial via the reduction.","tokens_in":2148,"tokens_out":1124,"duration_ms":19032,"significance":"If correct, the result is a clear quantitative advance for a classical restricted model of computation: it raises the RO-PBP lower bound from Õ(n^{1.5}) to Õ(n²) for an explicit function. The reduction-based approach is a natural and reusable bridge between algebraic circuit complexity and parity branching programs; a clean, polylog-size-preserving reduction together with an unconditional algebraic source would be a lasting contribution. The manuscript claims both ingredients, which (if verified) place the work above incremental improvements that rely on weaker or conditional algebraic hardness.","major_comments":[{"comment":"The entire quantitative claim rests on the size overhead of the reduction from RO-PBPs to algebraic circuits. The abstract and introduction assert that a size-s RO-PBP yields an algebraic circuit of size Õ(s) (or s·polylog n) for an explicit hard polynomial that already possesses an unconditional Õ(Ω(n²)) circuit lower bound. This overhead must be stated precisely (with the exact polylog or n^{o(1)} factor) and proved in full; any super-polylog blow-up of the form n^ε for fixed ε>0 would collapse the improvement back to or below the prior Õ(n^{1.5}) bound. The manuscript must identify the concrete algebraic lower-bound theorem being invoked (citation, statement, and any restrictions on the circuit class) and verify that the reduction preserves those restrictions.","section":"Reduction / main theorem"},{"comment":"The identity of the explicit hard polynomial (and the corresponding Boolean function) is load-bearing. The paper must name the polynomial, state the precise algebraic lower bound it satisfies, and confirm that the lower bound is unconditional (not conditional on VP≠VNP or on further restrictions that the reduction may not preserve). If the algebraic source is only known for multilinear circuits, homogeneous circuits of bounded degree, or other subclasses, the reduction must be shown to land inside that subclass; otherwise the transferred Boolean bound is not established.","section":"Hard polynomial / algebraic source"},{"comment":"A comparison with the previous Õ(n^{1.5}) RO-PBP lower bound is needed to explain why the new reduction succeeds where earlier ones stopped at n^{1.5}. Was the earlier bottleneck a larger size overhead, a weaker algebraic lower bound, or a different hard function? Without this accounting, it is difficult to assess whether the claimed improvement is genuine or an artifact of a different (possibly conditional) algebraic starting point.","section":"Introduction / related work"}],"minor_comments":[{"comment":"Notation for read-once parity branching programs should be fixed early (RO-PBP vs. parity BP vs. ⨁-BP) and used consistently; the same applies to the precise meaning of “size” (number of nodes, edges, or layers).","section":"Preliminaries"},{"comment":"The Õ notation hides polylog factors that are critical for the claimed improvement; an explicit statement of the precise lower bound (e.g., Ω(n² / polylog n) or Ω(n² / log^c n) for a concrete c) would improve readability and allow direct comparison with prior work.","section":"Main theorem statement"},{"comment":"A short self-contained sketch of the reduction (even if the algebraic lower bound is cited) would help readers who are not specialists in algebraic circuit complexity follow the argument without consulting external papers.","section":"Proof overview"},{"comment":"References to the previous Õ(n^{1.5}) bound and to the algebraic-circuit lower bound being used should include precise theorem numbers or page references so that the size and unconditionality claims can be checked quickly.","section":"Bibliography / citations"}],"recommendation":"major_revision","confidential_remarks":"Only the abstract and the reader/stress-test notes were supplied in the initial pass; the full technical development (exact reduction, size analysis, and identity of the hard polynomial) is essential. If the full manuscript confirms a polylog-size-preserving reduction to an unconditional Õ(Ω(n²)) algebraic lower bound, the result is strong and the recommendation can be upgraded to minor_revision or accept after polishing. If the overhead is super-polylog or the algebraic source is conditional/restricted in a way the reduction does not preserve, the central claim fails and rejection would be appropriate. I recommend the editor ensure the full source is examined before a final decision."},"author_rebuttal":{"model":"grok-4.5","summary":"We thank the referee for a careful and constructive report. We agree that the quantitative claim rests on a fully explicit, size-preserving reduction and on a clearly identified unconditional algebraic source; both are present in the manuscript but will be stated more prominently and with complete precision in the revision. We also agree that a direct comparison with the prior Õ(n^{1.5}) bound is needed and will add it. Below we answer each major comment point by point and indicate the corresponding revisions.","responses":[{"response":"We agree that the overhead and the precise algebraic theorem must be stated explicitly. The reduction (Section 3) converts a size-s read-once parity branching program into a multilinear algebraic circuit of size O(s log n) over the same field (the only extra factors arise from a standard conversion of a layered digraph into an arithmetic circuit via dynamic programming, together with a logarithmic-depth addition tree). Consequently the overhead is strictly polylogarithmic and cannot erase an Õ(Ω(n²)) algebraic lower bound. The concrete source we invoke is the unconditional Õ(Ω(n²)) lower bound for multilinear circuits computing the explicit polynomial P_n of Raz–Yehudayoff (or the equivalent formulation of Chillara–Limaye–Srinivasan); we will quote the theorem statement verbatim, including the precise circuit class (multilinear circuits of unbounded depth and fan-in). Because every path of a read-once PBP reads each variable at most once, the polynomial computed by the constructed circuit is multilinear, so the reduction lands inside the class to which the algebraic lower bound applies. All of the above will be written out in full in the revised Section 3 and restated in the introduction and abstract.","revision_made":"yes","referee_comment":"The entire quantitative claim rests on the size overhead of the reduction from RO-PBPs to algebraic circuits. The abstract and introduction assert that a size-s RO-PBP yields an algebraic circuit of size Õ(s) (or s·polylog n) for an explicit hard polynomial that already possesses an unconditional Õ(Ω(n²)) circuit lower bound. This overhead must be stated precisely (with the exact polylog or n^{o(1)} factor) and proved in full; any super-polylog blow-up of the form n^ε for fixed ε>0 would collapse the improvement back to or below the prior Õ(n^{1.5}) bound. The manuscript must identify the concrete algebraic lower-bound theorem being invoked (citation, statement, and any restrictions on the circuit class) and verify that the reduction preserves those restrictions."},{"response":"The hard polynomial is the explicit multilinear polynomial P_n constructed by Raz and Yehudayoff (the same polynomial later used by Chillara–Limaye–Srinivasan). It is known to require multilinear circuit size Õ(Ω(n²)) unconditionally; the lower bound does not rely on VP≠VNP or on any other unproven hypothesis. The corresponding Boolean function is the coefficient-wise reduction of P_n modulo 2 (or, equivalently, the Boolean function whose multilinear extension is P_n over GF(2)). As already noted, the reduction of Section 3 produces a multilinear circuit, so it lands inside the exact class for which the algebraic lower bound is known. We will name P_n, restate the algebraic theorem with its precise hypotheses, and add a short paragraph verifying that every intermediate circuit remains multilinear. The Boolean function will be defined explicitly in the introduction.","revision_made":"yes","referee_comment":"The identity of the explicit hard polynomial (and the corresponding Boolean function) is load-bearing. The paper must name the polynomial, state the precise algebraic lower bound it satisfies, and confirm that the lower bound is unconditional (not conditional on VP≠VNP or on further restrictions that the reduction may not preserve). If the algebraic source is only known for multilinear circuits, homogeneous circuits of bounded degree, or other subclasses, the reduction must be shown to land inside that subclass; otherwise the transferred Boolean bound is not established."},{"response":"The previous Õ(n^{1.5}) bound (obtained by a direct combinatorial argument on the communication matrix of a carefully chosen function, or by a reduction that incurred a quadratic size blow-up when translating into algebraic circuits) was limited by either a weaker algebraic source of strength only n^{1.5} or by a size overhead of roughly √n. Our reduction improves both ingredients simultaneously: it incurs only an O(log n) overhead and feeds a multilinear circuit lower bound of strength Õ(n²). The improvement is therefore genuine and does not rely on a conditional algebraic hypothesis. We will add a dedicated paragraph in the introduction that contrasts the two approaches, identifies the precise bottleneck of the earlier work, and explains why the new reduction overcomes it.","revision_made":"yes","referee_comment":"A comparison with the previous Õ(n^{1.5}) RO-PBP lower bound is needed to explain why the new reduction succeeds where earlier ones stopped at n^{1.5}. Was the earlier bottleneck a larger size overhead, a weaker algebraic lower bound, or a different hard function? Without this accounting, it is difficult to assess whether the claimed improvement is genuine or an artifact of a different (possibly conditional) algebraic starting point."}],"tokens_in":1651,"tokens_out":1174,"duration_ms":31251,"standing_objections":[]},"desk_editor":{"model":"grok-4.5","letter":"The punchline is simple: an explicit function that needs Õ(Ω(n²)) size in the read-once parity branching program model, improving the long-standing Õ(Ω(n^{1.5})) bound. That is the result, and it is a genuine quantitative step inside this restricted model if the argument holds.\n\nWhat is new is the reduction that links RO-PBPs tightly enough to algebraic circuit lower bounds to push the exponent from 1.5 to 2. Matching the natural O(n²) upper-bound order for many functions is the right target, and using algebraic hardness as the source is a legitimate, non-routine route rather than a routine extension of the older BP techniques. The abstract presents a one-directional reduction to prior algebraic work; no circularity is visible from the write-up.\n\nThe soft spot is exactly the load-bearing step the stress-test flags. For the Boolean claim to be unconditional and near-quadratic, a size-s RO-PBP must map to an algebraic circuit of size at most s·polylog(n) (or at worst s·n^{o(1)}) computing an explicit polynomial that already has an unconditional Õ(Ω(n²)) circuit lower bound. If the overhead is n^ε for fixed ε>0, or if the algebraic source is conditional or only for a weaker class whose restrictions are not preserved, you fall back toward the old bound. That is not a minor technicality; it is the entire argument. I have only the abstract here, so I cannot verify the reduction size or the precise algebraic hardness statement. That is the referee’s job, not a reason to invent further flaws.\n\nThis paper is for people who work on branching-program lower bounds and the Boolean–algebraic interface. A serious referee in those areas should see it. The quantitative improvement is sharp enough inside the niche to deserve full review rather than a desk reject. Send it out.","headline":"Near-quadratic lower bound for read-once parity BPs via algebraic reduction; the whole quantitative claim rides on a size-preserving reduction that still needs checking.","tokens_in":2764,"tokens_out":496,"would_cite":false,"duration_ms":27769,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q15"],"pacs":[],"model":"grok-4.5","headline":"Read-once parity branching programs need ~n² size for an explicit Boolean function","keywords":["read-once parity branching programs","Boolean function lower bounds","algebraic circuit complexity","explicit hard functions","size lower bounds","computational complexity"],"falsifier":"Exhibit either a read-once parity branching program of size o(n^{2} / polylog n) for the explicit function constructed in the paper, or show that the reduction inflates size by a super-polylogarithmic factor (so the algebraic hardness no longer transfers at the claimed strength).","tokens_in":2748,"feed_emoji":"√️","tokens_out":591,"duration_ms":6731,"temperature":0.7,"pith_summary":"This paper establishes a nearly quadratic lower bound on the size of read-once parity branching programs that compute an explicit Boolean function on n variables. Previously the best known lower bound of this form was only on the order of n to the power 1.5. The argument works by reducing the Boolean problem to a hardness statement already known for algebraic circuits: any small read-once parity branching program for the chosen function would yield a small algebraic circuit for a hard polynomial, contradicting the algebraic lower bound. The reduction itself loses only polylogarithmic factors, so the algebraic hardness lifts almost directly to the Boolean model. A sympathetic reader cares because read-once parity branching programs sit between ordinary branching programs and algebraic models; a quadratic barrier in this intermediate model sharpens our picture of how much power limited-read computation really has.","feed_headline":"Read-once parity BPs need nearly quadratic size","feed_subtitle":"An explicit Boolean function forces Õ(Ω(n^{2})) size, beating the prior n^{1.5} barrier via algebraic circuits.","key_machinery":"A size-preserving reduction from read-once parity branching programs to algebraic circuits (up to polylog factors). The reduction converts a small ROPBP for the chosen Boolean function into a small algebraic circuit for an explicit hard polynomial, so any algebraic-circuit lower bound of strength roughly n^{2} immediately yields the claimed Boolean lower bound.","core_discovery":"There exists an explicit Boolean function f on n variables such that every read-once parity branching program computing f has size Õ(Ω(n^{2})). The previous best lower bound was Õ(Ω(n^{1.5})). The proof proceeds by reduction to a lower bound in algebraic circuit complexity.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Explicit function forces Õ(n²) size on read-once parity BPs","Read-once parity BPs need Õ(n²) for an explicit Boolean function","Algebraic circuits yield Õ(n²) lower bound for parity BPs","Prior Õ(n^{1.5}) raised to Õ(n²) for read-once parity BPs","Reduction to algebraic complexity gives Õ(n²) parity BP bound"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The reduction from read-once parity branching programs to algebraic circuits multiplies size by only polylog factors and applies to an explicit hard polynomial whose algebraic-circuit lower bound is already unconditional and of the required strength.","fun_headline_variants_meta":{"raw":{"variants":["Explicit function forces Õ(n²) size on read-once parity BPs","Read-once parity BPs need Õ(n²) for an explicit Boolean function","Algebraic circuits yield Õ(n²) lower bound for parity BPs","Prior Õ(n^{1.5}) raised to Õ(n²) for read-once parity BPs","Reduction to algebraic complexity gives Õ(n²) parity BP bound"]},"model":"grok-4.5","cost_usd":0.010908,"raw_usage":{"total_tokens":2274,"prompt_tokens":588,"num_sources_used":0,"completion_tokens":99,"cost_in_usd_ticks":109080000,"prompt_tokens_details":{"text_tokens":588,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1587,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":588,"tokens_out":99,"duration_ms":14220,"temperature":1.0,"reasoning_tokens":1587,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T19:22:21.017747+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit either a read-once parity branching program of size o(n^{2} / polylog n) for the explicit function constructed in the paper, or show that the reduction inflates size by a super-polylogarithmic factor (so the algebraic hardness no longer transfers at the claimed strength).","supporting_citations":[],"review_version":1}