Pith. sign in

REVIEW 2 major objections 5 minor 11 references

On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read This paper constructs explicit algebraic branching programs of size matching known lower bounds for the rectangular permanent, rectangular determinant, and noncommutative determinant, and proves that evaluating the noncommutative…

desk verdict Even-k construction is correct and new, but Theorem 2 overclaims for odd k; still deserves serious refereeing. read the letter →

arxiv 1908.08347 v1 pith:GKZTMMPO submitted 2019-08-22 cs.CC

V. Arvind , Abhranil Chatterjee , Rajit Datta , Partha Mukhopadhyay This is my paper · ORCID
classification cs.CC
keywords algebraicbranchingprogramsrectangulardeterminantpermanentnoncommutativearithmeticcomplexitysymmetrizedelementarysymmetricpolynomialHadamardproductparameterized#W[1]-hardness
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

The paper's central claim is that three central polynomial families—the noncommutative rectangular permanent, the commutative rectangular determinant, and the square noncommutative determinant—possess explicit algebraic branching programs (layered directed graphs whose path labels sum to the polynomial) with size matching known lower bounds up to polynomial factors, and that these programs can be output in time comparable to their size. For the permanent side this means an explicit ABP of size $O^*(\binom{n}{\lfloor k/2\rfloor})$ for a $k\times n$ matrix of noncommuting variables, obtained by first building an ABP of the same size for the noncommutative symmetrized elementary symmetric polynomial $S^*_{n,k}$. For the determinant side it means an explicit $O^*(2^k)$ ABP for the commutative rectangular determinant and for the $k\times k$ noncommutative determinant. The paper also proves that evaluating the noncommutative rectangular determinant on matrices of dimension $n^{\epsilon}$ is $\#\mathrm{W}[1]$-hard, so an explicit $O^*(n^{o(k)})$ ABP is unlikely. A sympathetic reader should care because these are the first explicit constructions known to match the lower bounds, rather than merely nonconstructive existence results.

What carries the argument

The load-bearing identity is Lemma 11, $S^*_{n,k} = \sum_{S\in{\downarrow\mathcal{F}}}(-1)^{|S|}\hat{f}_S^2$, where $\mathcal{F}$ is the family of subsets of $[n]$ of size exactly $k/2$ and $\hat{f}_S$ is the sum of the symmetrized monomials $\hat{f}_A$ over all $A\supseteq S$ with $A\in\mathcal{F}$. This identity lets a degree-$k$ polynomial be assembled from a single multi-output ABP whose nodes are indexed by subsets of size at most $k/2$, together with a reversed copy of the same ABP. For the determinant ABP, the carrying object is a subset-chain ABP with edge labels $\operatorname{sgn}(S,j)\,x_{i+1,j}$, where the sign counts, by insertion sort, how many elements of $S$ are larger than $j$; Claim 15 verifies that the product of these signs along a subset chain equals the sign of the corresponding permutation. For the rectangular determinant, a Hadamard product with the noncommutative ordered elementary symmetric polynomial filters out the ordered column monomials.

What would settle it

Set $k=3$ and follow Lemma 11 literally: $\mathcal{F}$ is empty, so the inclusion-exclusion sum ranges only over $|S|\le 1$ and the right-hand side is a sum of terms $\hat{f}_S^2$ of degree 2, not 3. Thus the proof constructs no ABP for $S^*_{n,3}$; finding an odd $k$ for which no explicit ABP of size $O^*(\binom{n}{\lfloor k/2\rfloor})$ exists would falsify the theorem as stated.

Watch

Extended reading notes

Core claim

The discovery is that inclusion-exclusion over half-sized subsets turns the degree-$k$ symmetric polynomial $S^*_{n,k}$ into a signed sum of squares $\sum_{S}(-1)^{|S|}\hat{f}_S^2$, where each $\hat{f}_S$ has degree $k/2$ and can be computed by a layered ABP with $\binom{n}{\downarrow k/2}$ nodes; reversing one copy of that ABP and joining sinks to sources with sign labels yields an explicit ABP for $S^*_{n,k}$, and renaming variables in the right order turns it into an ABP for the noncommutative rectangular permanent. The same layered idea, with edges labeled by insertion-sort signs, gives an explicit $2^k$-layer ABP for the noncommutative determinant, and a Hadamard product with the ordered noncommutative elementary symmetric polynomial filters the determinant monomials to produce the commutative rectangular determinant. The hardness result uses Hadamard products of the noncommutative rectangular determinant with an injection filter to isolate the graph polynomial of a directed graph, showing that evaluating it over matrix algebras counts $k$-paths and is $\#\mathrm{W}[1]$-hard.

Load-bearing premise

The construction of the $S^*_{n,k}$ and permanent ABPs is defined only for even $k$, because the family $\mathcal{F}$ of subsets of size exactly $k/2$ is empty when $k$ is odd; the paper states the bounds for all $k$ but supplies no odd-$k$ argument.

Editorial extensions

If this is right

  • The noncommutative rectangular permanent and $S^*_{n,k}$ now have explicit ABPs of size $O^*(\binom{n}{\lfloor k/2\rfloor})$ over any field, with construction time matching the size; when $k$ is even this matches the lower bound up to polynomial factors.
  • The commutative rectangular determinant has an explicit ABP of size $O^*(2^k)$, turning the previously known $O^*(2^k)$ evaluation algorithm into a uniform branching program.
  • The $k\times k$ noncommutative determinant has an explicit $O^*(2^k)$ ABP, making the known lower bound constructively tight.
  • A polynomial with the same zero-nonzero support as $S^*_{n,k}$ has a $2^k$-explicit ABP; squaring it by Hadamard product gives a $4^k$-explicit positively weakly equivalent polynomial.
  • Evaluating the noncommutative rectangular determinant on $n^\epsilon\times n^\epsilon$ rational matrices is $\#\mathrm{W}[1]$-hard, so an explicit ABP of size $O^*(n^{o(k)})$ for it is unlikely.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The restriction to even $k$ looks removable: a natural extension would split $k$ into $a=\lfloor k/2\rfloor$ and $b=\lceil k/2\rceil$ and symmetrize over mixed products $f_A f_B$ with $|A|=a$ and $|B|=b$, but the paper does not carry this out; if it works, the permanent bound would hold for all $k$.
  • The $2^k$ weakly equivalent construction is close to a known route to a deterministic $O^*(2^k)$ algorithm for $k$-path: a positively weakly equivalent $2^k$-explicit ABP would give such an algorithm via Hadamard squaring, so the paper's open problem is a precise target.
  • The commutative rectangular determinant ABP's reliance on ordering variables suggests that the same layered construction may give ABPs for other symmetric multilinear polynomials obtained by filtering monomials with Hadamard products.
  • The $\#\mathrm{W}[1]$-hardness for matrix-valued evaluation contrasts with the small-algebra algorithm $O^*(2^k r^{2k})$ in the appendix; the gap indicates the hardness comes from the dimension of the matrices, not from $k$ alone.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper gives explicit algebraic branching program (ABP) constructions for several rectangular determinant and permanent polynomials. In the noncommutative setting, it claims an O*((n down k/2))-size explicit ABP for the symmetrized elementary symmetric polynomial S*_{n,k} and, by set-multilinearization, for the rectangular permanent rPer(Y). In the commutative setting, it claims an O*(2^k)-size explicit ABP for the rectangular determinant rDet(X), and separately an O*(2^k)-size explicit ABP for the square noncommutative determinant. It also proves that evaluating the noncommutative rectangular determinant over rational matrix algebras is #W[1]-hard. The upper-bound proofs are based on an inclusion-exclusion identity for S*_{n,k}, multi-output ABPs and a reversal lemma, a subset-chain ABP with insertion-sort sign labels for the determinant, a Vandermonde-based weak-equivalence construction, and Hadamard products.

Significance. If the gap concerning odd k is repaired, the paper would deliver the first explicit ABPs matching Nisan's lower bounds up to polynomial factors, which is a genuinely useful contribution to noncommutative and parameterized arithmetic complexity. The constructions are self-contained and are not obtained by fitting parameters to the lower bounds; Nisan's results are used only as external benchmarks. The subset-chain ABP for the noncommutative determinant and the Vandermonde weak-equivalence construction are elegant and are likely to be reusable. The hardness reduction via Hadamard products and matrix-valued evaluations is also of independent interest.

major comments (2)
  1. [Section 3.1, Theorem 2] Theorem 2 is stated for all k, but the proof of Theorem 2.1 requires k to be even: the family F is defined as the subsets of [n] of size exactly k/2, and Lemma 11 sums f_A f_B over disjoint A,B in F, which only makes sense when k/2 is an integer. Consequently Theorem 2.2, obtained by set-multilinearization, is also unsupported for odd k. Moreover, the notation \binom{n}{\downarrow k/2} in the theorem statement is undefined when k is odd. Please either restrict the statements to even k, or supply the missing odd-k construction, for example by splitting k into floor(k/2) and ceil(k/2) and proving an inclusion-exclusion identity for sum_S (-1)^{|S|} \hat f_S \hat g_S with two different symmetrized families. The paper currently contains no such argument.
  2. [Section 3.1, Lemma 13] The construction of the multi-output ABP B2 is described only by the recurrence \hat f_{i-1,S} = \hat f_{i,S} + \hat f_{i,S\cup{i}} for i not in S, with the statement that one can take a copy of B1 and 'simultaneously compute' the values. The manuscript does not give an explicit layer-by-layer graph, does not specify the edge labels (including constant labels), and does not analyze the construction time. Since the paper's main contribution is the explicitness of the upper bounds, this is a load-bearing gap: a formal description of B2 as a layered ABP with the claimed O*((n down k/2)) size should be provided.
minor comments (5)
  1. [Section 5, Lemma 17] In the proof of Lemma 17, the edge labels are written as x_{i+1,j} and x_{i+1,n+j}, but they should be y_{i+1,j} and y_{i+1,n+j} to match the definition of the polynomial F in F<Y>.
  2. [Abstract and Theorem 5] The abstract says evaluating the rectangular noncommutative determinant is W[1]-hard, while Theorem 5 states #W[1]-hard; please make the statement consistent.
  3. [Section 4.2, Remark 16] The remark calls f = g o g 'positively weakly equivalent' to S*_{n,k}, but the coefficients of g are Vandermonde determinants over an arbitrary field with at least n distinct elements. The notion '> 0' is not defined for a general or finite field; please state that the remark is intended for ordered fields such as the rationals, or replace 'positive' with a precisely defined notion.
  4. [Section 4.3] After taking the Hadamard product with S^nc_{n,k}(Z) and substituting z_i = 1, the proof should state explicitly that the resulting ABP is over the commuting variables x_{j,i} and computes exactly rDet(X); the argument is clear, but a one-sentence justification would remove ambiguity.
  5. [Notation] The paper uses O^*(.) to suppress polynomial factors in both n and k; since the bounds are parameterized by k, it would be helpful to state explicitly that O^*(2^k) and O^*( (n down k/2) ) mean the displayed quantity times a polynomial in n and k.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the ABP constructions are self-contained; the only concern is a non-circular proof gap for odd k.

full rationale

The paper's claimed derivations do not reduce to their inputs by construction. The S*_{n,k} ABP (Theorem 2.1) is built from an explicit inclusion-exclusion identity (Lemma 11), whose proof is self-contained, together with explicit multi-output ABPs B1 and B2 (Lemmas 12 and 13) that compute the symmetrized monomials f_A and their superset sums by direct recurrence; no parameter is fitted and no target polynomial is used as an input. Theorem 2.2 obtains rPer(Y) by set-multilinearizing that ABP, which by definition maps each word y_{i1}...y_{ik} to y_{1,i1}...y_{k,ik}, yielding exactly the rectangular permanent. The determinant ABP (Theorem 4.1) is an explicit subset-layered construction whose sign correctness is proved in Claim 15. Theorem 4.2 uses a Vandermonde determinant to show support equals S*_{n,k}, and Theorem 4.3 filters a 2^k-size ABP by Hadamard product with a standard poly(n,k)-size ABP for the noncommutative elementary symmetric polynomial, then substitutes z_i=1; this is a composition of independent constructions, not a circular one. Citations to the authors' earlier work [2],[3] supply standard Hadamard-product lemmas whose assumptions do not include the target results, so they are real external support rather than load-bearing self-citation. The one legitimate concern is an omitted proof, not circularity: Section 3.1 defines F as 'the family of subsets of [n] of size exactly k/2', so Lemma 11's inclusion-exclusion is only valid when k is even, while Theorem 2 is stated for all k and the paper never supplies the odd-k construction (e.g., by splitting into floor(k/2) and ceil(k/2)). This is a correctness/coverage gap, not an equivalence-by-construction, and it does not change the circularity score.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

No data fitting or invented mathematical objects appear. The construction relies on standard inclusion-exclusion, external theorems about Hadamard products of ABPs, and Nisan's lower bounds for optimality framing. The only chosen constants are the distinct field elements alpha_i in Section 4.2, which are existential and not tuned to any data.

free parameters (1)
  • Distinct field elements alpha_1,...,alpha_n for the weak-equivalence construction = arbitrary distinct elements; only existence is used
    Section 4.2 introduces alpha_i to build a Vandermonde matrix. Any n distinct field elements work; the values are not fitted to data, but they are chosen by hand to make the argument work.
assumptions (6)
  • standard math Inclusion-exclusion principle for finite sets
    Used in Lemma 11 to derive S*_{n,k} as an alternating sum of squares of symmetrized polynomials.
  • domain assumption Nisan's rank lower bounds for ABP size of S*_{n,k} and noncommutative determinant
    The paper cites Nisan [11] to assert that the constructed ABP sizes are optimal. The constructions themselves do not depend on the lower bound, but the framing of optimality does.
  • domain assumption Hadamard product of two noncommutative ABPs can be computed by an ABP of product size
    This is Theorem 9 from Arvind, Joglekar, and Srinivasan [2], used in Section 4.3 to filter z-monomials and in Section 5 to combine polynomials.
  • domain assumption Evaluation of Hadamard product via transition matrices
    Lemma 10 from Arvind and Srinivasan [3] is used in the hardness proof to convert evaluation of rDet on matrices into an FPT evaluation of a Hadamard product.
  • domain assumption Counting directed k-paths in a graph is #W[1]-hard
    The hardness reduction starts from the #W[1]-complete problem of counting simple k-paths in directed graphs.
  • domain assumption The field F has at least n distinct elements for Theorem 4.2
    The Vandermonde matrix argument requires n distinct alpha_i; the theorem states this condition explicitly.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials." pith.science (2026). https://pith.science/paper/GKZTMMPO

@misc{pith2026190808347,
  author       = {Pith},
  title        = {Pith review of: On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GKZTMMPO}},
  note         = {Machine review of arXiv:1908.08347}
}
abstract

We study the arithmetic circuit complexity of some well-known family of polynomials through the lens of parameterized complexity. Our main focus is on the construction of explicit algebraic branching programs (ABP) for determinant and permanent polynomials of the \emph{rectangular} symbolic matrix in both commutative and noncommutative settings. The main results are: 1. We show an explicit $O^{*}({n\choose {\downarrow k/2}})$-size ABP construction for noncommutative permanent polynomial of $k\times n$ symbolic matrix. We obtain this via an explicit ABP construction of size $O^{*}({n\choose {\downarrow k/2}})$ for $S_{n,k}^*$, noncommutative symmetrized version of the elementary symmetric polynomial $S_{n,k}$. 2. We obtain an explicit $O^{*}(2^k)$-size ABP construction for the commutative rectangular determinant polynomial of the $k\times n$ symbolic matrix. 3. In contrast, we show that evaluating the rectangular noncommutative determinant over rational matrices is $W[1]$-hard.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 6 canonical work pages

  1. [6]

    7 Markus Bläser

    URL: https://doi.org/10.1016/j.ipl.2010.07.005, doi:10.1016/j.ipl.2010.07.005. 7 Markus Bläser. Noncommutativity makes determinants hard. volume 243, pages 172–183, 07

    work page doi:10.1016/j.ipl.2010.07.005 2010

  2. [12]

    Arvind et

    URL: https://doi.org/10.1137/09076619X, doi:10.1137/09076619X. Arvind et. al. 13 A Computing Rectangular Permanent and Determinant over Sma ll Dimensional Algebras The main result of the section is as follows. ◮ Theorem

    doi:10.1137/09076619x

  3. [1991]

    12 Virginia Vassilevska Williams and Ryan Williams

    URL: http://doi.acm.org/10.1145/103418.103462, doi:10.1145/103418.103462. 12 Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. , 42(3):831–854,

    arXiv

  4. [2000]

    Counting paths and packings in halves

    5 Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikk o Koivisto. Counting paths and packings in halves. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009 , pages 578–586, Berlin, Heidelberg,

    work page 2009

  5. [2007]

    Lower bounds for non-commutative computation ( extended ab- stract)

    11 Noam Nisan. Lower bounds for non-commutative computation ( extended ab- stract). In Proceedings of the 23rd Annual ACM Symposium on Theory of Com - puting, May 5-8, 1991, New Orleans, Louisiana, USA , pages 410–418,

    work page 1991

  6. [2009]

    On the hardness of the noncommutative determinant

    3 Vikraman Arvind and Srikanth Srinivasan. On the hardness of the noncommutative determinant. In Proceedings of the 42nd ACM Symposium on Theory of Computing , STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 , pages 677–686,

    work page 2010

  7. [2010]

    4 Amos Beimel, Francesco Bergadano, Nader H

    URL: http://doi.acm.org/10.1145/1806689.1806782, doi:10.1145/1806689.1806782. 4 Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Ku shilevitz, and Stefano Var- ricchio. Learning functions represented as multiplicity a utomata. Journal of the ACM , 47(3):506–530,

    arXiv

  8. [2011]

    9 Ioannis Koutis and Ryan Williams

    URL: https://doi.org/10.1145/1993636.1993703, doi:10.1145/1993636.1993703. 9 Ioannis Koutis and Ryan Williams. LIMITS and applications o f group algebras for parameterized problems. ACM Trans. Algorithms , 12(3):31:1–31:18,

    arXiv

Show all 11 references
  1. [2013]

    8 Steve Chien, Prahladh Harsha, Alistair Sinclair, and Srika nth Srinivasan

    doi:10.1007/978-3-642-39206-1_15 . 8 Steve Chien, Prahladh Harsha, Alistair Sinclair, and Srika nth Srinivasan. Almost settling the hardness of noncommutative determinant. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2...

    doi

  2. [2016]

    10 Yoshiomi Nakagami and Haruo Yanai

    URL: http://doi.acm.org/10.1145/2885499, doi:10.1145/2885499. 10 Yoshiomi Nakagami and Haruo Yanai. On cullis determinant fo r rectangular matrices. Linear Algebra and its Applications , 422(2):422 – –441,

    doi

  3. [2018]

    12 On Explicit Branching Programs 2 Vikraman Arvind, Pushkar S

    URL: http://arxiv.org/abs/1807.04496, arXiv:1807.04496. 12 On Explicit Branching Programs 2 Vikraman Arvind, Pushkar S. Joglekar, and Srikanth Sriniva san. Arithmetic circuits and the hadamard product of polynomials. In IARCS Annual Conference on Foundations of Software Techno...

    2009 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.