{"id":"b8bfadfe-3c91-40c5-b95c-716953fff0bc","arxiv_id":"1908.08347","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"The paper gives explicit optimal-size algebraic branching programs for the noncommutative rectangular permanent and for the commutative rectangular determinant, plus a #W[1]-hardness result for evaluating the noncommutative rectangular determinant over matrices.","lead":"This paper builds small arithmetic circuits called branching programs for determinant and permanent polynomials of rectangular matrices, and shows a matching hardness barrier for a noncommutative variant.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2 is stated for all k but the proof of Section 3.1 only covers even k; the odd-k case is unproved and not addressed in the paper.","rationale":"The paper's positive constructions for even k are mathematically sound: the inclusion-exclusion in Lemma 11 is correct, the multi-output ABPs of Lemmas 12 and 13 have the claimed size, and Lemma 14 correctly combines them. The square determinant ABP of Section 4.1 and the rectangular commutative determinant ABP of Section 4.3 are also carefully argued. The central gap is the missing odd-k case in Theorem 2, exactly as the reader identified. This is a genuine incompleteness, not a manufactured concern. However, it is likely repairable: a floor/ceil split of the inclusion-exclusion should yield an ABP of size O*((n down floor(k/2))) with no division, so the theorem's O* bound would still hold. The padding step in the hardness proof is underdescribed but appears standard: by using a constant-size ABP for F and padding the number of columns, one can lift the matrix dimension to n^ε for any fixed ε > 0. Thus the concerns do not warrant a change from the reader's CONDITIONAL verdict; the paper should be accepted after a revision that adds the odd-k construction and details the padding.","tokens_in":12676,"tokens_out":52341,"duration_ms":485825,"concrete_test":"Derive the odd-k analogue of Lemma 11 with a=floor(k/2), b=ceil(k/2): set F_a = {A : |A|=a}, F_b = {B : |B|=b}, and verify S*_{n,k} = sum_{S, |S|≤a} (-1)^{|S|} hat-f_S^{(a)} hat-f_S^{(b)}, where hat-f_S^{(r)} = sum_{A⊇S, |A|=r} f_A. Then confirm that the generalized reversal lemma (with f_i g_i^R instead of f_i f_i^R) builds an ABP of size O*((n down a)) over any field without division. Check the smallest odd cases k=1 and k=3, including characteristic 2 for k=3. If this construction fails or requires division, Theorem 2 is false as stated for odd k.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 3.1, the proof of Theorem 2.1 defines F as the family of subsets of [n] of size exactly k/2 (so k must be even), and Lemma 11 proves S*_{n,k} = sum_{S in down-F} (-1)^{|S|} hat-f_S^2 by pairing A and B from F and requiring A∩B=∅. This inclusion-exclusion is valid only for even k. Theorem 2 claims (n down k/2)-explicit ABPs for all k, but no construction is given for odd k. The gap propagates to Theorem 2.2 because rPer(Y) is obtained from S*_{n,k} by set-multilinearization. For odd k one would need to split into sizes floor(k/2) and ceil(k/2), replacing the square hat-f_S^2 with a product of two different symmetrized sums; the paper does not provide this argument, nor does it discuss whether this works over any field (e.g., whether a division by 2 or k+1 is required). As written, the central upper bound for the noncommutative rectangular permanent is unsupported for odd k.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12882,"tokens_out":10325,"duration_ms":106305,"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":[{"comment":"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.","section":"Section 3.1, Theorem 2"},{"comment":"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.","section":"Section 3.1, Lemma 13"}],"minor_comments":[{"comment":"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>.","section":"Section 5, Lemma 17"},{"comment":"The abstract says evaluating the rectangular noncommutative determinant is W[1]-hard, while Theorem 5 states #W[1]-hard; please make the statement consistent.","section":"Abstract and Theorem 5"},{"comment":"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.","section":"Section 4.2, Remark 16"},{"comment":"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.","section":"Section 4.3"},{"comment":"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.","section":"Notation"}],"recommendation":"major_revision","confidential_remarks":"The odd-k gap in Theorem 2 is the main obstruction to accepting the paper as written. The even-k construction and the other upper bounds appear sound, and the gap is plausibly repairable by adding an explicit odd-k construction or by restricting the theorem. I would not reject on the current presentation alone, but the theorem statements must be corrected before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper gives explicit ABPs of size O*((n choose floor(k/2))) for the noncommutative symmetrized elementary symmetric polynomial S*_{n,k} and for rectangular permanent, but only for even k. For even k the construction is correct: the inclusion-exclusion identity in Lemma 11 works, the multi-output ABP lemmas are sound, and the reversal lemma is fine. This is a real result—it matches Nisan's lower bound and gives a polynomial-time construction where previously only existence was known. The 2^k-explicit ABP for the square noncommutative determinant (Section 4.1) is also correct and uses a clean subset-chain argument. The commutative rectangular determinant construction via Hadamard product with the noncommutative elementary symmetric polynomial checks out. The Vandermonde weak-equivalence trick for S* is clever and works over fields with at least n distinct elements.\n\nThe soft spot is exactly where the reader put it: Theorem 2 is stated for all k, but the proof of Section 3.1 defines F as subsets of size exactly k/2, so it only handles even k. For odd k there is no construction, and the obvious split into floor/ceil sizes would give an ABP of size O((n choose ceil(k/2))), which does not match the claimed (n choose floor(k/2)) bound. The authors do not mention odd k at all. This is not a minor omission; it is an overstatement of the main result. The theorem should be revised to state the even-k case only, or the odd-k construction must be supplied.\n\nThe hardness result in Section 5 is plausible, though the final padding from 2k x 2n matrices to n^epsilon x n^epsilon dimensions is hand-waved. That is a minor gap compared to the odd-k issue.\n\nOn balance: the paper is worth a serious referee. The odd-k gap is real but patchable; if the authors cannot close it, the even-k result still stands. I would send this to review and tell the referee to insist on a corrected Theorem 2.\n\nRecommendation: accept peer review, expect major revision.","headline":"Even-k construction is correct and new, but Theorem 2 overclaims for odd k; still deserves serious refereeing.","tokens_in":13446,"tokens_out":3619,"would_cite":true,"duration_ms":35591,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["algebraic branching programs","rectangular determinant","rectangular permanent","noncommutative arithmetic complexity","symmetrized elementary symmetric polynomial","Hadamard product","parameterized complexity","#W[1]-hardness"],"falsifier":"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.","tokens_in":12471,"feed_emoji":"🧮","tokens_out":10843,"duration_ms":94908,"temperature":0.7,"pith_summary":"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.","feed_headline":"Explicit optimal branching programs for rectangular determinant","feed_subtitle":"Constructions for the rectangular permanent and the noncommutative determinant match known lower bounds as well.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the inclusion-exclusion dynamic programming over subsets of size at most half the target size, which the paper adapts to build the multi-output ABP for the symmetrized polynomials.","marker":"[5]"},{"why":"Supplies the lower bounds $\\Omega(\\binom{n}{\\downarrow k/2})$ for $S^*_{n,k}$ and $\\Omega(2^k)$ for the noncommutative determinant that the paper's explicit ABPs match.","marker":"[11]"},{"why":"Supplies the theorem that the Hadamard product of two noncommutative ABPs can be computed as another ABP of the product size, used for the rectangular determinant construction.","marker":"[2]"},{"why":"Supplies Lemma 10, the matrix-evaluation technique for Hadamard products that drives the #W[1]-hardness proof for the noncommutative rectangular determinant.","marker":"[3]"},{"why":"Supplies the $O^*(2^k)$ algorithm for rectangular permanent evaluation used in the appendix and as the motivating parameterized connection.","marker":"[12]"},{"why":"Supplies the definition and background of the rectangular determinant for symbolic matrices, the object computed by the rectangular determinant ABP.","marker":"[10]"}],"fun_headline_variants":["Explicit optimal ABPs for rectangular permanent and determinant","Half-size subset trick gives optimal ABPs for permanent, determinant","Optimal branching programs for noncommutative permanent, determinant","Explicit ABPs match lower bounds for rectangular permanent, determinant","W[1]-hard evaluation but explicit optimal ABPs for determinant"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Explicit optimal ABPs for rectangular permanent and determinant","Half-size subset trick gives optimal ABPs for permanent, determinant","Optimal branching programs for noncommutative permanent, determinant","Explicit ABPs match lower bounds for rectangular permanent, determinant","W[1]-hard evaluation but explicit optimal ABPs for determinant"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000958,"raw_usage":{"total_tokens":4106,"prompt_tokens":991,"completion_tokens":3115,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":607,"completion_tokens_details":{"reasoning_tokens":3030}},"tokens_in":607,"tokens_out":3115,"duration_ms":21868,"temperature":1.0,"reasoning_tokens":3030,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:41:36.369022+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}