{"id":"5c004c61-0032-45a9-b0bd-1d7dbd5e28b0","arxiv_id":"2411.18981","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Order-finding for ROABPs is NP-hard in the worst case, but efficient for generic and random instances, with approximation hardness transferring from cutwidth.","lead":"Researchers prove that finding the variable order that minimizes the width of a read-once oblivious algebraic branching program for a given polynomial is NP-hard, even for constant-degree polynomials. They also give an algorithm that finds the order quickly for most random or generic polynomials, where the Boolean version only has heuristics.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the exact CutWidth reduction and the generic/random algorithm arguments are internally sound; the reader-flagged typos are repairable and do not threaten the central claims.","rationale":"The reader's conditional verdict is reasonable because the paper contains two concrete proof typos: Lemma 3.12 says 'with probability at least' where a failure probability is meant, and Theorems 6.6/6.12 undercount the number of identity tests by a factor of n. Both are repairable without changing the stated results, so they do not constitute a load-bearing concern. I checked the core technical claims: the exact rank identity in Claim 4.4 follows by decomposing f_G into A-only, B-only, and cross terms, with the cross terms forming a permutation submatrix and the A-only/constant rows giving the extra two dimensions; the generic-case Lemma 6.7 constructs a polynomial with width w by ensuring every prefix leaves at least one of the two extreme pairs unseparated, and Lemma 6.9 correctly handles arbitrary sets via complement and reversal; the average-case Lemma 6.10 applies Schwartz-Zippel to a nonzero composed minor. The remaining dependence on external NP-hardness of CutWidth is inherited and not a flaw, and the random/generic promise is explicitly scoped. Thus I do not see a reason to move the reader's verdict, only to keep the requested corrections in mind.","tokens_in":27582,"tokens_out":35383,"duration_ms":341480,"concrete_test":"As a sanity check, brute-force Lemma 4.3 on all graphs with at most 7 vertices over GF(2): for every order sigma, compute the Nisan rank of each prefix of f_G and compare max_{prefix} rank(M_prefix(f_G)) with 2 + CutWidth_sigma(G); if any mismatch is found, re-examine Claim 4.4.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I read the hardness reduction and the generic/random-order algorithm in good faith and did not find a load-bearing gap. Lemma 4.3's rank identity is supported by the permutation-submatrix argument and by the rank-1 contributions of the A-only and B-only parts; the small typos in Lemma 3.12 (success/failure probability) and in the identity-test count in Theorems 6.6 and 6.12 (a missing factor of n) are genuine but cosmetic, and the corrected count remains within n^{O(log(d+1) w)}. The main caveat is external: the reduction inherits NP-hardness of CutWidth, and the average-case theorem is explicitly conditional on a generic/random ROABP promise, which the paper states. Neither of these is an internal inconsistency or a defect in the central argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the order-finding problem for read-once oblivious algebraic branching programs (ROABPs): given a polynomial f and a width parameter w, decide whether there is a variable order in which f has an ROABP of width at most w. The main results are: (1) NP-hardness of the decision problem even for constant-degree polynomials given in dense representation, proved by an exact polynomial-time reduction from CutWidth with the identity RO-width_sigma(f_G) = 2 + CutWidth_sigma(G); (2) transfer of cutwidth approximation hardness and a black-box theorem showing that any constant-factor approximation algorithm for order-finding yields a PTAS; (3) a randomized algorithm for generic and random ROABPs that runs in polynomial time when w = poly(d) and in time n^{O(log w)} when d is constant, based on Nisan's characterization, algebraic-geometric genericity, and Schwartz-Zippel arguments. The hardness and PTAS parts are clean and largely self-contained; the generic/random algorithmic part is the most delicate and, as written, has proof gaps.","tokens_in":27690,"tokens_out":40492,"duration_ms":343627,"significance":"If the algorithmic claims can be made fully rigorous, the paper makes a substantial contribution: it gives an exact worst-case hardness reduction for a natural algebraic meta-complexity problem, transfers cutwidth approximation hardness, and provides the first nontrivial average/generic-case algorithm for order-finding in ROABPs, contrasting with the Boolean ROBP setting where only heuristics are known. The exact identity with cutwidth is elegant and falsifiable, and the PTAS boosting argument is a clean black-box transformation. The paper is likely to be of interest to algebraic complexity and meta-complexity audiences.","major_comments":[{"comment":"Lemma 6.7 is false as stated when k = 1, which occurs whenever w <= d. The construction in the proof is then a single factor 1 + x_{i1}x_{j1} + ... + x_{i1}^d x_{j1}^d. For a prefix of the identity order that contains i1 but not j1, the Nisan matrix has rank d+1 > w, so the polynomial does not have ROABP width w in order id. The condition n >= 3 log_{d+1} w does not exclude this regime. In fact, for w = 1 the claim of Lemma 6.4 is false: every width-1 ROABP polynomial is a product of univariate polynomials and has Nisan rank 1 for every partition, so V_{1,sigma} is contained in V_{1,T} for every T and the strict inclusion V_{1,sigma} cap V_{1,T} subsetneq V_{1,sigma} cannot hold. The proofs of Theorems 6.6 and 6.12 therefore do not cover w <= d as stated. The authors should either restrict the theorems to w > d or provide a separate argument for the small-width regime (noting that w = 1 is trivially solvable by outputting any order).","section":"Lemma 6.7 and Lemma 6.4"},{"comment":"The identity-test count in the proofs of Theorems 6.6 and 6.12 is incorrect. Algorithm 1 as written runs the PIT of Lemma 3.12 on every candidate set, including all sets of size up to log_{d+1} w; there are sum_{i <= log_{d+1} w} binom(n,i) = n^{Theta(log w)} such sets. The displayed bound [2(n-2 log_{d+1}w) + 2 log_{d+1}w * binom(n, log_{d+1}w)] < 2n is therefore false. Consequently, the subsequent union bound over 'at most 2n' tests with per-test failure probability 2^{-2n} does not establish the claimed success probability. This is repairable: the algorithm can skip PIT for sets T with |T| <= log_{d+1}w or n-|T| <= log_{d+1}w (their rank is automatically at most w), and the field size / sampling set S must be chosen large enough to union-bound over the resulting number of tests. As written, the proof of the running-time guarantee of the central algorithmic theorem is not sound.","section":"Theorems 6.6 and 6.12, running-time proof"}],"minor_comments":[{"comment":"The probability statement is inverted: the determinant is nonzero with probability at least 1 - nd(w+1)^2/|S|, not nd(w+1)^2/|S|. Later proofs use the correct failure probability, so this is a typo, but it should be fixed.","section":"Lemma 3.12"},{"comment":"The inequality (1-2^{-n})^2 >= 1 - 2n^{-1} is not meaningful as written; it should be 1 - 2^{1-n}.","section":"Theorems 6.6 and 6.12"},{"comment":"The statement 'There is an ROABP of width w+2 in an order sigma if and only if the linear arrangement of G in the order sigma has CutWidth w' should read 'width at most w+2' and 'CutWidth at most w', consistent with the exact identity RO-width_sigma(f_G) = 2 + CutWidth_sigma(G).","section":"Lemma 4.3"},{"comment":"Step 4 of WidthPTAS says 'return hat{w}', but the promised output of the approximation problem is an order sigma, not a width. The algorithm should return the order produced by ApproxWidth; hat{w} is only the width bound for that order.","section":"Theorem 7.1, algorithm"},{"comment":"The text says Algorithm 2 runs in deterministic time 2^{O(n)} poly(d,w), but Algorithm 1 uses the randomized PIT of Lemma 3.12; the algorithm should be described as randomized (as it is in Section 6).","section":"Section 5"},{"comment":"The claim that 'As T is left-heavy, i1 < n/2' is not always true (for example n=6 and T={3,4}); the needed conclusion i1 < j2 follows from i1 <= n/2 and j2 > n/2, so the strict inequality should be weakened.","section":"Lemma 6.7"}],"recommendation":"major_revision","confidential_remarks":"The reader's stress-test note treats the identity-test count as cosmetic, but I find it combined with the k=1 gap to be a genuine proof deficiency in the central algorithmic theorems; the stated theorem does not follow from the proof as written. The hardness and PTAS parts are solid, and the algorithmic claims are likely fixable, so I recommend major revision rather than rejection. The authors should also check whether the small-width regime w <= d can be handled by a straightforward argument or requires an additional construction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper settles the worst-case complexity of ROABP order-finding (NP-hard, even for constant-degree dense polynomials) and gives the first generic/random-case polynomial-time algorithm. The exact CutWidth reduction is the right tool, and the rank identity is clean. I read the reduction carefully; the permutation-submatrix argument checks out. The generic algorithm's dimension argument via varieties is also sound, and the contrast with Boolean OBDDs, where only heuristics are known, is fair and interesting.\n\nWhat is genuinely new: no prior work proved NP-hardness of ROABP order-finding, and the dense-representation hardness for constant-degree polynomials is a nice bonus that gives algebraic MCSP hardness for ROABPs. The width-amplification trick for the PTAS implication is simple and works.\n\nSoft spots: the typos the reader found are real. Lemma 3.12 states the success probability as the failure probability (should be 1 - nd(w+1)^2/|S|), and Theorems 6.6 and 6.12 count identity tests as fewer than 2n when the term 2 log(d+1) w * C(n, log(d+1) w) should have an n factor per test. These are repairable and do not change the conclusions; the runtime bound still holds. Also, the hardness inherits the external NP-hardness of CutWidth, and because the reduction is exact, the hardness theorems collapse if CutWidth is in P—that is not a flaw, just a fact about the reduction. The average-case guarantee is explicitly for random/generic ROABPs as defined, and the width condition n >= 3 log_{d+1} w matters; for adversarial inputs the worst-case remains 2^n, which is consistent with NP-hardness.\n\nThe citation pattern looks fine: they credit the Boolean OBDD hardness and Sieling's boosting, and self-citations are for actual related prior work. I do not see circularity.\n\nWho this is for: algebraic complexity researchers working on ROABPs, PIT, and learning, plus meta-complexity people interested in algebraic MCSP. A serious referee should see this.\n\nRecommendation: accept into peer review, conditional on the authors fixing the stated typos and re-checking the counting in Theorems 6.6 and 6.12.","headline":"Solid worst-case hardness and a genuinely new generic-case algorithm for ROABP order-finding; the two flagged typos are real but cosmetic.","tokens_in":28266,"tokens_out":1664,"would_cite":true,"duration_ms":14755,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Finding an ROABP's best variable order is NP-hard","keywords":["read-once oblivious algebraic branching programs","order-finding","NP-hardness","CutWidth","Nisan matrices","generic algorithms","algebraic MCSP","approximation scheme"],"falsifier":"A polynomial-time exact algorithm for DenseROwidth-d for any fixed $d \\ge 6$, run on dense coefficient vectors, would contradict the NP-hardness claim (unless P=NP), since the exact identity would then solve CutWidth on maximum-degree-3 planar graphs. For the average-case claim, one can sample random ROABPs per Definition 3.7 with $n \\ge 3\\log_{d+1} w$ and check whether the algorithm's running time stays within $n^{O(\\log w)}$ and returns a correct order with probability at least $1-2^{-n}$; a concrete counterexample would be a sampled polynomial on which the algorithm exceeds the promised time or outputs a wrong order.","tokens_in":27356,"feed_emoji":"🧮","tokens_out":10099,"duration_ms":83333,"temperature":0.7,"pith_summary":"Given a polynomial and a target width, deciding whether there is some ordering of the variables in which the polynomial can be computed by a read-once oblivious algebraic branching program (ROABP) of that width is NP-hard, even when the polynomial has constant degree and is given by its full list of coefficients. The hardness comes from an exact reduction from the graph CutWidth problem: for every graph $G$ the paper constructs a polynomial $f_G$ whose ROABP width in every order $\\sigma$ is exactly $2 + \\operatorname{CutWidth}_\\sigma(G)$, so any optimal ordering for one is an optimal ordering for the other. Because the identity is exact, existing hardness-of-approximation results for CutWidth transfer to order-finding, and any constant-factor approximation algorithm would in fact yield a polynomial-time approximation scheme. On the algorithmic side, the paper shows that random (generic) ROABPs are tractable: with black-box access, a correct order can be recovered in polynomial time when the width is polynomial in the individual degree, and in $n^{O(\\log w)}$ time when the individual degree is constant. This contrasts with the Boolean analogue of ordered binary decision diagrams, for which only heuristic order-finding methods are known.","feed_headline":"ROABP order-finding is NP-hard even for constant degree","feed_subtitle":"Exact CutWidth reduction proves NP-hardness; generic ROABPs still yield to a fast order-finding algorithm.","key_machinery":"The argument rests on the standard characterization of ROABP width by ranks of Nisan matrices: the optimal width of $f$ in an order $\\sigma$ is the maximum rank of $M_T(f)$ over prefixes $T$ of $\\sigma$. The reduction's gadget is the polynomial $f_G = \\sum_{v} x_v^{\\Delta+1} + \\sum_{uv \\in E} x_u^{n_u(v)} x_v^{n_v(u)}$, where $n_u(v)$ is a distinct exponent identifying $v$ among the neighbours of $u$; for every partition $A \\sqcup B$, the rank of $M_A(f_G)$ equals $2 + c_G(A,B)$, the number of cut edges plus two. This exact rank-to-cut correspondence carries both the NP-hardness and the transfer of approximation hardness. For the average-case algorithm, the key mechanism is the claim that for a generic polynomial with an ROABP of width $w$ in order $\\sigma$, any set $T$ that is not a prefix of $\\sigma$ (or the complement of one) forces $\\operatorname{rank}(M_T(f)) > w$, except on a strictly lower-dimensional subvariety; the algorithm therefore explores the graph of low-rank prefixes and finds the true order in $n^{O(\\log w)}$ steps.","core_discovery":"On the paper's own terms, the central result is that order-finding for ROABPs is NP-complete in the worst case, proved by a Karp reduction from CutWidth that is exact at the level of widths: for any graph $G$ and any variable order $\\sigma$, the minimum ROABP width of the auxiliary polynomial $f_G$ in order $\\sigma$ equals $2 + \\operatorname{CutWidth}_\\sigma(G)$. Because CutWidth is NP-hard even for maximum-degree-3 planar graphs, the decision problem is NP-hard for constant-degree polynomials in their dense representation, and the algebraic minimum-circuit-size problem for ROABPs is NP-hard as well. For the average case, the paper gives a randomized algorithm that, given black-box access to a random ROABP of width $w$, outputs an order achieving width $w$ with high probability, in time $\\mathrm{poly}(n,d,w)$ when $w = d^{O(1)}$ and $n^{O(\\log w)}$ when $d$ is constant. It also proves that any constant-factor approximation algorithm for the search version would imply a PTAS, using a transformation that raises the ROABP width of every order to the $k$-th power.","pith_inferences":["Because the reduction outputs sparse polynomials with unit coefficients, the same gadget plausibly yields NP-hardness for other ROABP-related reconstruction tasks, such as finding an order minimizing ROABP size rather than width, although the paper does not state this.","The generic-case algorithm shows that, within the natural random-ROABP distribution, hard order-finding instances form a measure-zero subvariety; any average-case hardness result would therefore need a different input distribution.","The paper's contrast with Boolean OBDDs suggests that the rank-based algebraic structure of Nisan matrices, rather than the combinatorial subfunction structure, is what makes generic order-finding tractable; this hints that a similar generic result for Boolean OBDDs may be impossible.","The PTAS-boosting transformation is black-box and oblivious to the polynomial, so it would also apply to any future approximation algorithm for parameters that behave multiplicatively under the same variable-blocking lift."],"forward_implications":["The algebraic circuit-minimization problem for ROABPs is NP-hard, so finding the smallest-width ROABP for a polynomial given as a circuit is intractable in the worst case.","For every fixed individual degree $d \\ge 6$, the algebraic minimum-circuit-size problem for ROABPs is NP-hard when the input is the dense coefficient vector, matching the Boolean MCSP hardness that is known for restricted circuit classes.","Under the Small Set Expansion conjecture (a complexity assumption about graph partitioning), or any hardness-of-approximation for CutWidth, order-finding cannot be approximated within any constant factor better than 1 in polynomial time.","Any constant-factor approximation algorithm for the search version implies a PTAS, so the approximation threshold is either $(1+\\varepsilon)$ for every $\\varepsilon$ or no fixed constant at all.","Random and generic ROABPs are tractable: with black-box access, a correct order is recoverable in polynomial time when the width is polynomial in the individual degree, and in $n^{O(\\log w)}$ time when the individual degree is constant."],"supporting_citations":[{"why":"Supplies the rank characterization that equates ROABP width in an order with the maximum rank of Nisan matrices over prefixes; both the reduction and the algorithm use it.","marker":"[Nis91]"},{"why":"Standard reference for NP-hardness of CutWidth and graph-layout problems, the problem reduced from.","marker":"[GJ79]"},{"why":"Proves CutWidth NP-hard even for maximum-degree-3 graphs, which yields constant-degree hard instances in dense representation.","marker":"[MS88]"},{"why":"Shows OBDD order-finding is NP-complete via graph layout; the paper adapts this idea to ROABPs using Nisan rank.","marker":"[BW96]"},{"why":"Gives constant-factor inapproximability and boosting ideas for OBDD order-finding that the paper re-derives for ROABPs through an algebraic width-powering transformation.","marker":"[Sie02]"},{"why":"Provides hardness of approximation for CutWidth under the Small Set Expansion conjecture, transferred directly by the exact reduction.","marker":"[APW12]"},{"why":"The Schwartz-Zippel lemma bounds the probability that random evaluations certify a Nisan rank bound, underpinning the average-case algorithm.","marker":"[Sch80]"}],"fun_headline_variants":["ROABP order-finding NP-hard even for constant degree","Order-finding for ROABPs NP-hard via exact CutWidth reduction","Constant-factor approximation for ROABP order-finding yields PTAS","Generic ROABPs: order-finding in polynomial time","Worst-case ROABP order-finding NP-hard, average-case poly"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The hardness results inherit the external NP-hardness of the graph CutWidth problem, so if CutWidth were solvable in polynomial time, the NP-hardness theorems would collapse; the average-case algorithm's guarantees additionally require the input to be a random (or generic) ROABP with $n \\ge 3\\log_{d+1} w$.","fun_headline_variants_meta":{"raw":{"variants":["ROABP order-finding NP-hard even for constant degree","Order-finding for ROABPs NP-hard via exact CutWidth reduction","Constant-factor approximation for ROABP order-finding yields PTAS","Generic ROABPs: order-finding in polynomial time","Worst-case ROABP order-finding NP-hard, average-case poly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000422,"raw_usage":{"total_tokens":2237,"prompt_tokens":1082,"completion_tokens":1155,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":698,"completion_tokens_details":{"reasoning_tokens":1064}},"tokens_in":698,"tokens_out":1155,"duration_ms":9909,"temperature":1.0,"reasoning_tokens":1064,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:42:11.884373+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A polynomial-time exact algorithm for DenseROwidth-d for any fixed $d \\ge 6$, run on dense coefficient vectors, would contradict the NP-hardness claim (unless P=NP), since the exact identity would then solve CutWidth on maximum-degree-3 planar graphs. For the average-case claim, one can sample random ROABPs per Definition 3.7 with $n \\ge 3\\log_{d+1} w$ and check whether the algorithm's running time stays within $n^{O(\\log w)}$ and returns a correct order with probability at least $1-2^{-n}$; a concrete counterexample would be a sampled polynomial on which the algorithm exceeds the promised time or outputs a wrong order.","supporting_citations":[],"review_version":1}