Pith. sign in

REVIEW 3 major objections 4 minor 39 references

A Lower Bound for Read-Once Parity Branching Programs

T0 review · 3 major / 4 minor · reviewed 2026-07-08 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Read-once parity branching programs need ~n² size for an explicit Boolean function

desk verdict 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. read the letter →

arxiv 2607.05944 v1 pith:PISA5JV4 submitted 2026-07-07 cs.CC

Ben Lee Volk This is my paper · ORCID
classification cs.CC MSC 68Q1768Q15
keywords read-onceparitybranchingprogramsBooleanfunctionlowerboundsalgebraiccircuitcomplexityexplicithardfunctionssizecomputational
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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).

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Reduction / main theorem] 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.
  2. [Hard polynomial / algebraic source] 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.
  3. [Introduction / related work] 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.
minor comments (4)
  1. [Preliminaries] 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).
  2. [Main theorem statement] 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.
  3. [Proof overview] 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.
  4. [Bibliography / citations] 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.

Simulated Author's Rebuttal

3 responses · 0 unresolved

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.

read point-by-point responses

  1. Referee: 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.

    Authors: 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: yes

  2. Referee: 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.

    Authors: 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: yes

  3. Referee: 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.

    Authors: 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: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: one-directional reduction from RO-PBP to an external algebraic-circuit lower bound.

full rationale

The paper claims an Õ(Ω(n²)) lower bound for read-once parity branching programs by reducing the Boolean model to a lower bound in algebraic circuit complexity. The abstract and the stated derivation present a one-way size-preserving (up to polylog) reduction that maps a small RO-PBP for an explicit Boolean function to a small algebraic circuit for an explicit hard polynomial; the algebraic hardness is treated as prior external work, not derived from the RO-PBP statement itself. There is no self-definitional loop (the Boolean size is not defined in terms of the algebraic size), no fitted parameter renamed as a prediction, no uniqueness theorem imported from the same authors to forbid alternatives, and no ansatz smuggled in via self-citation. Self-citation, if any, is not load-bearing for the central quantitative claim. The residual risk that the algebraic source might share authors or unstated hypotheses is a correctness/assumption concern, not circularity under the stated criteria. Score 0 is therefore the honest finding: the derivation is self-contained against the external algebraic benchmark and does not reduce by construction to its own inputs.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

From the abstract alone the paper rests on (1) the standard definition of read-once parity branching programs, (2) the existence of an explicit hard polynomial with a sufficiently strong algebraic-circuit lower bound, and (3) a size-preserving reduction between the two models. No free parameters are fitted; no new physical or mathematical entities are invented. The main unexamined load-bearing pieces are the precise statement of the algebraic lower bound and the size overhead of the reduction.

assumptions (3)
  • domain assumption Standard definition and size measure of read-once parity branching programs
    The model is taken as given from the literature; the lower bound is with respect to that model.
  • domain assumption Existence of an explicit polynomial with a sufficiently strong algebraic-circuit lower bound that the reduction can invoke
    The abstract states the proof reduces to a lower bound in algebraic circuit complexity; that algebraic result is an external axiom for the Boolean claim.
  • ad hoc to paper The reduction maps a size-s read-once parity BP to an algebraic circuit of size Õ(s) (or s·polylog) for the related polynomial
    This size relationship is the novel technical step claimed by the paper; if the blow-up is larger the quantitative bound weakens.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Lower Bound for Read-Once Parity Branching Programs." pith.science (2026). https://pith.science/paper/PISA5JV4

@misc{pith2026260705944,
  author       = {Pith},
  title        = {Pith review of: A Lower Bound for Read-Once Parity Branching Programs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PISA5JV4}},
  note         = {Machine review of arXiv:2607.05944}
}
abstract

We prove an $\tilde{\Omega}(n^2)$ lower bound for read-once parity branching programs computing an explicit boolean function on $n$ variables. The previous best lower bound was $\tilde{\Omega}(n^{1.5})$. Our lower bound is proved by reducing the problem to a lower bound in algebraic circuit complexity.

Figures

Figures reproduced from arXiv: 2607.05944 by the authors.

Figure 1
Figure 1. Cycle with chords. Blue nodes are in B and black nodes are not in B. The matching σB maps 2 to 3 by an edge labeled y2 and then 1 to 4 by an edge labeled y1. gives the recursive formula Mi,j = X k∈[i+1,j],xk̸=xi Mi+1,k−1 · Mk+1,j . (The “xk ̸= xi” condition makes sure we only count x-valid matchings). The base cases for this induction are empty intervals whose value is 1. Our dynamic programming algorithm is inspire… view at source ↗
Figure 2
Figure 2. “Cutting” a cycle at the leader ℓ and drawing the edges on an interval. Suppose now ℓ > 0 is a leader such that σB(ℓ) < ℓ, and order the elements as ℓ, ℓ + 1, ℓ + 2, . . . , n − 1, 0, 1, 2, . . . , σB(ℓ), . . . , ℓ − 1 By definition there is a directed edge from ℓ to σB(ℓ). As before, since ℓ was connected to σB(ℓ) it means that all elements on the arc [ℓ + 1, σB(ℓ) − 1] of the cycle were already matched to one anot… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    http://dx.doi.org/10.1007/S00493-019-4009-0 Unbalancing Sets and An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits

    Noga Alon, Mrinal Kumar, and Ben Lee Volk. http://dx.doi.org/10.1007/S00493-019-4009-0 Unbalancing Sets and An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits . Comb. , 40(2):149--178, 2020

    work page doi:10.1007/s00493-019-4009-0 2020

  2. [2]

    http://dx.doi.org/10.1016/0022-0000(87)90010-9 A Lower Bound for Read-Once-Only Branching Programs

    L \' a szl \' o Babai, P \' e ter Hajnal, Endre Szemer \' e di, and Gy \" o rgy Tur \' a n. http://dx.doi.org/10.1016/0022-0000(87)90010-9 A Lower Bound for Read-Once-Only Branching Programs . J. Comput. Syst. Sci. , 35(2):153--162, 1987

    work page doi:10.1016/0022-0000(87)90010-9 1987

  3. [3]

    http://dx.doi.org/10.1007/978-3-540-45138-9\_23 Lower Bounds for General Graph-Driven Read-Once Parity Branching Programs

    Henrik Brosenne, Matthias Homeister, and Stephan Waack. http://dx.doi.org/10.1007/978-3-540-45138-9\_23 Lower Bounds for General Graph-Driven Read-Once Parity Branching Programs . In Mathematical Foundations of Computer Science (MFCS) , volume 2747 of Lecture Notes in Computer Science , pages 290--299. Springer, 2003

    work page doi:10.1007/978-3-540-45138-9 2003

  4. [4]

    Razborov, and Roman Smolensky

    Allan Borodin, Alexander A. Razborov, and Roman Smolensky. http://dx.doi.org/10.1007/BF01200404 On Lower Bounds for Read- k -Times Branching Programs . Computational Complexity , 3:1--18, 1993

    work page doi:10.1007/bf01200404 1993

  5. [5]

    http://dx.doi.org/10.1016/0304-3975(83)90110-X The Complexity of Partial Derivatives

    Walter Baur and Volker Strassen. http://dx.doi.org/10.1016/0304-3975(83)90110-X The Complexity of Partial Derivatives . Theor. Comput. Sci. , 22:317--330, 1983

    work page doi:10.1016/0304-3975(83)90110-x 1983

  6. [6]

    http://dx.doi.org/10.1007/S00224-022-10113-9 One-Tape Turing Machine and Branching Program Lower Bounds for MCSP

    Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, and Yuichi Yoshida. http://dx.doi.org/10.1007/S00224-022-10113-9 One-Tape Turing Machine and Branching Program Lower Bounds for MCSP . Theory Comput. Syst. , 68(4):868--899, 2024

    work page doi:10.1007/s00224-022-10113-9 2024

  7. [7]

    http://dx.doi.org/10.4230/LIPICS.CCC.2024.20 Lower Bounds for Set-Multilinear Branching Programs

    Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, and Amir Shpilka. http://dx.doi.org/10.4230/LIPICS.CCC.2024.20 Lower Bounds for Set-Multilinear Branching Programs . In 39th Computational Complexity Conference ( CCC ) , volume 300 of LIPIcs , pages 20:1--20:20. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024

    work page doi:10.4230/lipics.ccc.2024.20 2024

  8. [8]

    http://dx.doi.org/10.1007/S00037-022-00223-8 Quadratic Lower Bounds for Algebraic Branching Programs and Formulas

    Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk. http://dx.doi.org/10.1007/S00037-022-00223-8 Quadratic Lower Bounds for Algebraic Branching Programs and Formulas . Comput. Complex. , 31(2):8, 2022

    work page doi:10.1007/s00037-022-00223-8 2022

Show all 39 references
  1. [9]

    Forbes, Mrinal Kumar, and Ramprasad Saptharishi

    Michael A. Forbes, Mrinal Kumar, and Ramprasad Saptharishi. http://dx.doi.org/10.4230/LIPICS.CCC.2016.33 Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity . In 31st Conference on Computational Complexity ( CCC ) , volume 50 of LIPIcs...

    2016 doi

  2. [10]

    https://eccc.weizmann.ac.il/report/2026/001 Multilinear Algebraic Branching Programs and the Min-Partition Rank Method

    Th \' e o Bor \' e m Fabris, Nutan Limaye, Srikanth Srinivasan, and Amir Yehudayoff. https://eccc.weizmann.ac.il/report/2026/001 Multilinear Algebraic Branching Programs and the Min-Partition Rank Method . Electron. Colloquium Comput. Complex. , TR26 , 2026. Pre-print availabl...

    2026

  3. [11]

    Michael A. Forbes. http://dx.doi.org/10.4230/LIPICS.CCC.2024.31 Low-Depth Algebraic Circuit Lower Bounds over Any Field . In 39th Computational Complexity Conference ( CCC ) , volume 300 of LIPIcs , pages 31:1--31:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024

    2024 doi

  4. [12]

    Forbes and Amir Shpilka

    Michael A. Forbes and Amir Shpilka. http://dx.doi.org/10.1109/FOCS.2013.34 Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs . In 54th Annual IEEE Symposium on Foundations of Computer Science ( FOCS ) , pages 243--252...

    2013 doi

  5. [13]

    Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson

    Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson. http://dx.doi.org/10.4086/TOC.2021.V017A010 Proof Complexity Lower Bounds from Algebraic Circuit Complexity . Theory Comput. , 17:1--88, 2021

    2021 doi

  6. [14]

    Razborov

    Dima Grigoriev and Alexander A. Razborov. http://dx.doi.org/10.1007/S002009900021 Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields . Appl. Algebra Eng. Commun. Comput. , 10(6):465--487, 2000

    doi

  7. [15]

    http://dx.doi.org/10.1145/3618260.3649616 Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers

    Tuomas Hakoniemi, Nutan Limaye, and Iddo Tzameret. http://dx.doi.org/10.1145/3618260.3649616 Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers . In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC) , pages 1396--1404. ACM , 2024

    2024 doi

  8. [16]

    http://dx.doi.org/10.1016/J.TCS.2006.01.052 Lower bounds for restricted read-once parity branching programs

    Matthias Homeister. http://dx.doi.org/10.1016/J.TCS.2006.01.052 Lower bounds for restricted read-once parity branching programs . Theor. Comput. Sci. , 359(1-3):1--14, 2006

    2006 doi

  9. [17]

    http://dx.doi.org/10.1145/322326.322341 Some Exact Complexity Results for Straight-Line Computations over Semirings

    Mark Jerrum and Marc Snir. http://dx.doi.org/10.1145/322326.322341 Some Exact Complexity Results for Straight-Line Computations over Semirings . Journal of the ACM , 29(3):874--897, 1982

    1982 doi

  10. [18]

    http://dx.doi.org/10.1007/978-3-642-24508-4 Boolean Function Complexity - Advances and Frontiers , volume 27 of Algorithms and combinatorics

    Stasys Jukna. http://dx.doi.org/10.1007/978-3-642-24508-4 Boolean Function Complexity - Advances and Frontiers , volume 27 of Algorithms and combinatorics . Springer, 2012

    2012 doi

  11. [19]

    http://dx.doi.org/10.1137/0214050 A Lower Bound for the Formula Size of Rational Functions

    Kyriakos Kalorkoti. http://dx.doi.org/10.1137/0214050 A Lower Bound for the Formula Size of Rational Functions . SIAM J. Comput. , 14(3):678--687, 1985

    1985 doi

  12. [20]

    http://dx.doi.org/10.1109/SCT.1993.336536 On Span Programs

    Mauricio Karchmer and Avi Wigderson. http://dx.doi.org/10.1109/SCT.1993.336536 On Span Programs . In Proceedings of the Eighth Annual Structure in Complexity Theory Conference , pages 102--111. IEEE Computer Society, 1993

    1993 doi

  13. [21]

    https://www.cse.iitb.ac.in/ nutan/papers/abp-complexity.pdf Homogeneous ABP complexity of elementary symmetric polynomial , 2019

    Nutan Limaye, Kunal Mittal, and Mukesh Pareek. https://www.cse.iitb.ac.in/ nutan/papers/abp-complexity.pdf Homogeneous ABP complexity of elementary symmetric polynomial , 2019

    2019

  14. [22]

    http://dx.doi.org/10.1145/3734215 Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

    Nutan Limaye, Srikanth Srinivasan, and S \' e bastien Tavenas. http://dx.doi.org/10.1145/3734215 Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits . J. ACM , 72(4):26:1--26:35, 2025

    2025 doi

  15. [23]

    https://mathoverflow.net/questions/264226/singular-locus-of-zero-set-of-elementary-symmetric-polynomial Singular locus of zero locus of elementary symmetric polynomials , 2017

    Izaak Meckler and Gjergji Zaimi. https://mathoverflow.net/questions/264226/singular-locus-of-zero-set-of-elementary-symmetric-polynomial Singular locus of zero locus of elementary symmetric polynomials , 2017

    2017

  16. [24]

    http://mi.mathnet.ru/dan32449 On a Boolean function

    Eduard Ivanovich Nechiporuk. http://mi.mathnet.ru/dan32449 On a Boolean function . Dokl. Akad. Nauk SSSR , 169:765--766, 1966

    1966

  17. [25]

    http://dx.doi.org/10.1145/103418.103462 Lower Bounds for Non-Commutative Computation (Extended Abstract)

    Noam Nisan. http://dx.doi.org/10.1145/103418.103462 Lower Bounds for Non-Commutative Computation (Extended Abstract) . In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC) , pages 410--418. ACM , 1991

    1991 doi

  18. [26]

    Okolnishnikova

    E.A. Okolnishnikova. https://web.vu.lt/mif/s.jukna/boolean/Russians/Okolnishnikova-1991.pdf Lower bounds on the complexity of realization of characteristic functions of binary codes by branching programs . Metody Diskretnogo Analiza , 51:61--83, 1991

    1991

  19. [27]

    https://eccc.weizmann.ac.il/report/2025/128 Computing the Elementary Symmetric Polynomials in Positive Characteristics

    Ian Orzel. https://eccc.weizmann.ac.il/report/2025/128 Computing the Elementary Symmetric Polynomials in Positive Characteristics . Electron. Colloquium Comput. Complex. , TR25 , 2025. Pre-print available at http://arxiv.org/abs/TR25-128 arXiv:TR25-128

    2025

  20. [28]

    http://dx.doi.org/10.4086/TOC.2006.V002A006 Separation of Multilinear Circuit and Formula Size

    Ran Raz. http://dx.doi.org/10.4086/TOC.2006.V002A006 Separation of Multilinear Circuit and Formula Size . Theory Comput. , 2(6):121--135, 2006

    2006 doi

  21. [29]

    http://dx.doi.org/10.1145/1502793.1502797 Multi-linear formulas for permanent and determinant are of super-polynomial size

    Ran Raz. http://dx.doi.org/10.1145/1502793.1502797 Multi-linear formulas for permanent and determinant are of super-polynomial size . J. ACM , 56(2):8:1--8:17, 2009

    2009 doi

  22. [30]

    http://dx.doi.org/10.1137/070707932 A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

    Ran Raz, Amir Shpilka, and Amir Yehudayoff. http://dx.doi.org/10.1137/070707932 A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits . SIAM J. Comput. , 38(4):1624--1647, 2008

    2008 doi

  23. [31]

    http://dx.doi.org/10.1007/S00037-008-0254-0 Balancing Syntactically Multilinear Arithmetic Circuits

    Ran Raz and Amir Yehudayoff. http://dx.doi.org/10.1007/S00037-008-0254-0 Balancing Syntactically Multilinear Arithmetic Circuits . Comput. Complex. , 17(4):515--535, 2008

    2008 doi

  24. [32]

    http://dx.doi.org/10.1007/S00037-009-0270-8 Lower Bounds and Separations for Constant Depth Multilinear Circuits

    Ran Raz and Amir Yehudayoff. http://dx.doi.org/10.1007/S00037-009-0270-8 Lower Bounds and Separations for Constant Depth Multilinear Circuits . Comput. Complex. , 18(2):171--207, 2009

    2009 doi

  25. [33]

    https://github.com/dasarpmar/lowerbounds-survey/releases/ A survey of lower bounds in arithmetic circuit complexity

    Ramprasad Saptharishi. https://github.com/dasarpmar/lowerbounds-survey/releases/ A survey of lower bounds in arithmetic circuit complexity . Github survey, 2015

    2015

  26. [34]

    http://dx.doi.org/10.1016/J.TCS.2005.03.016 A hierarchy result for read-once branching programs with restricted parity nondeterminism

    Petr Savick \' y and Detlef Sieling. http://dx.doi.org/10.1016/J.TCS.2005.03.016 A hierarchy result for read-once branching programs with restricted parity nondeterminism . Theor. Comput. Sci. , 340(3):594--605, 2005

    2005 doi

  27. [35]

    http://dx.doi.org/10.1007/BF01436566 Die Berechnungskomplexit\" a t Von Elementarsymmetrischen Funktionen Und Von Interpolationskoeffizienten

    Volker Strassen. http://dx.doi.org/10.1007/BF01436566 Die Berechnungskomplexit\" a t Von Elementarsymmetrischen Funktionen Und Von Interpolationskoeffizienten . Numerische Mathematik , 20(3):238--251, June 1973

    1973 doi

  28. [36]

    http://dx.doi.org/10.1561/0400000039 Arithmetic Circuits: A survey of recent results and open questions

    Amir Shpilka and Amir Yehudayoff. http://dx.doi.org/10.1561/0400000039 Arithmetic Circuits: A survey of recent results and open questions . Found. Trends Theor. Comput. Sci. , 5(3-4):207--388, 2010

    2010 doi

  29. [37]

    Thathachar

    Jayram S. Thathachar. http://dx.doi.org/10.1145/276698.276881 On Separating the Read-k-Times Branching Program Hierarchy . In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC) , pages 653--662. ACM , 1998

    1998 doi

  30. [38]

    http://dx.doi.org/10.1145/42282.46161 On the complexity of branching programs and decision trees for clique functions

    Ingo Wegener. http://dx.doi.org/10.1145/42282.46161 On the complexity of branching programs and decision trees for clique functions . J. ACM , 35(2):461--471, 1988

    1988 doi

  31. [39]

    http://dx.doi.org/10.1007/BFB0030340 An Exponential Lower Bound for One-Time-Only Branching Programs

    Stanislav Z \' a k. http://dx.doi.org/10.1007/BFB0030340 An Exponential Lower Bound for One-Time-Only Branching Programs . In Mathematical Foundations of Computer Science (MFCS) , volume 176 of Lecture Notes in Computer Science , pages 562--566. Springer, 1984

    1984 doi

Pith tools

Reviewed July 8, 2026 · model on record in the stance chip above.