Pith. sign in

REVIEW 2 major objections 6 minor 1 cited by

The Complexity of Order-Finding for ROABPs

T0 review · 2 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read Finding an ROABP's best variable order is NP-hard

desk verdict Solid worst-case hardness and a genuinely new generic-case algorithm for ROABP order-finding; the two flagged typos are real but cosmetic. read the letter →

arxiv 2411.18981 v1 pith:5LCMS5QD submitted 2024-11-28 cs.CC

Vishwas Bhargava , Pranjal Dutta , Sumanta Ghosh , Anamay Tengse This is my paper · ORCID
classification cs.CC MSC 68Q1768Q2568W20
keywords read-onceobliviousalgebraicbranchingprogramsorder-findingNP-hardnessCutWidthNisanmatricesgenericalgorithmsMCSPapproximationscheme
open problems 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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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

Editorial extensions

If this is right

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

Reading between the lines

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

  • 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.
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 / 6 minor

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.

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 (2)
  1. [Lemma 6.7 and Lemma 6.4] 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).
  2. [Theorems 6.6 and 6.12, running-time proof] 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.
minor comments (6)
  1. [Lemma 3.12] 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.
  2. [Theorems 6.6 and 6.12] The inequality (1-2^{-n})^2 >= 1 - 2n^{-1} is not meaningful as written; it should be 1 - 2^{1-n}.
  3. [Lemma 4.3] 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).
  4. [Theorem 7.1, algorithm] 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.
  5. [Section 5] 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).
  6. [Lemma 6.7] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the hardness proof is an exact Karp reduction from the external CutWidth problem, and the algorithmic results rest on Nisan's characterization and Schwartz-Zippel, not on their own conclusions.

full rationale

The paper's central claims are self-contained relative to independent external inputs. The NP-hardness of order-finding is established by a direct polynomial-time reduction from CutWidth (Lemma 4.3), with the exact identity RO-width_sigma(f_G) = 2 + CutWidth_sigma(G) proven by an explicit rank calculation on Nisan matrices. The hardness therefore inherits only the external NP-hardness of CutWidth, cited to [GJ79, MS88]. The generic/random-case algorithm uses Nisan's characterization (Theorem 3.6) to characterize width, Lemma 6.4 to show that bad sets form a proper subvariety via an explicit witness polynomial, and Schwartz-Zippel for the finite-field probability bound. No parameter is fitted to the target result and no prediction is derived from the conclusion. The PTAS result is a conditional implication: it assumes an alpha-approximation algorithm and proves, via the black-box width-tensoring transformation of Lemma 7.2, that this yields a (1+epsilon)-approximation. This is not circular because the transformation is proven directly from the rank behavior of Kronecker products. The paper's caveats, such as the dependence on the promise in Definition 3.7, the condition n >= 3 log_{d+1} w, and the explicit admission in Section 7 that no unconditional PTAS-impossibility for CutWidth is known, are external limitations rather than circular reasoning. Minor typographical issues (e.g., the identity-test count in Theorems 6.6 and 6.12) do not affect the core derivation. Overall, no self-citation is load-bearing, and no step reduces to its own input by construction.

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

The paper introduces no fitted parameters and no new entities. It relies on standard theorems (Nisan, Schwartz-Zippel), external NP-hardness of CutWidth, elementary algebraic geometry, and the stated random ROABP model. The SSE conjecture appears only in the conditional approximation-hardness corollary.

assumptions (6)
  • standard math Nisan's characterization (Theorem 3.6): optimal ROABP width in an order equals max Nisan rank over prefixes.
    This is the backbone of both the reduction and the algorithm; it is cited from Nisan 1991 and used throughout Sections 3 to 7.
  • standard math Schwartz-Zippel lemma (Lemma 3.1).
    Used for all randomized PIT steps and for the average-case probability bounds.
  • standard math CutWidth is NP-hard for general graphs and for planar graphs of maximum degree 3.
    External hardness results cited as [GJ79] and [MS88]; the reduction transfers this hardness to ROABP order-finding.
  • standard math Algebraic geometry facts: the image of an irreducible variety under a polynomial map is irreducible, and a finite union of proper subvarieties cannot cover an irreducible variety.
    Used in Lemma 6.5 to show generic points avoid bad subvarieties.
  • domain assumption Small Set Expansion conjecture (for the hardness-of-approximation transfer).
    Used in Section 7 to claim cutwidth is hard to approximate within any constant; this is conditional, not proved.
  • domain assumption Random ROABP model (Definition 3.7) samples all coefficient-matrix entries uniformly.
    Defines the average-case input distribution for the generic algorithm.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Complexity of Order-Finding for ROABPs." pith.science (2026). https://pith.science/paper/5LCMS5QD

@misc{pith2026241118981,
  author       = {Pith},
  title        = {Pith review of: The Complexity of Order-Finding for ROABPs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5LCMS5QD}},
  note         = {Machine review of arXiv:2411.18981}
}
abstract

We study the \emph{order-finding problem} for Read-once Oblivious Algebraic Branching Programs (ROABPs). Given a polynomial $f$ and a parameter $w$, the goal is to find an order $\sigma$ in which $f$ has an ROABP of \emph{width} $w$. We show that this problem is NP-hard in the worst case, even when the input is a constant degree polynomial that is given in its dense representation. We provide a reduction from CutWidth to prove these results. Owing to the exactness of our reduction, all the known results for the hardness of approximation of Cutwidth also transfer directly to the order-finding problem. Additionally, we also show that any constant-approximation algorithm for the order-finding problem would imply a polynomial time approximation scheme (PTAS) for it. On the algorithmic front, we design algorithms that solve the order-finding problem for generic ROABPs in polynomial time, when the width $w$ is polynomial in the individual degree $d$ of the polynomial $f$. That is, our algorithm is efficient for most/random ROABPs, and requires more time only on a lower-dimensional subspace (or subvariety) of ROABPs. Even when the individual degree is constant, our algorithm runs in time $n^{O(\log w)}$ for most/random ROABPs. This stands in strong contrast to the case of (Boolean) ROBPs, where only heuristic order-finding algorithms are known.

Figures

Figures reproduced from arXiv: 2411.18981 by the authors.

Figure 1
Figure 1. Examples of good (top) and bad (bottom) choices for (i1, j1) and (i2, j2). Proof. Let k = j log(d+1) w k + 1, so that k ≤ |T| ≤ n/2. We will define a polynomial f that depends only on 2k of the n variables, split into two sets: L and R of size k each. For L = {i1, i2, . . . , ik} and R = {j1, j2, . . . , jk}, we will then define f(x) = ∏ ℓ∈[k]  1 + xiℓ xjℓ + x 2 iℓ x 2 jℓ + · · · + x d iℓ x d jℓ  The idea here is … view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. On Closure Properties of Read-Once Oblivious Algebraic Branching Programs

    cs.CC 2025-09 conditional novelty 7.0 of 10

    Read-once oblivious algebraic branching programs are not closed under factoring, powering, or composing with elementary symmetric polynomials.

Reference graph

Works this paper leans on

49 extracted references · 31 canonical work pages · cited by 1 Pith paper

  1. [1]

    write newline toupdate empty

    " write newline toupdate empty "" write " toupdate(" cite * "): " * toupdate * " " * write if "" before.all 'output.state := FUNCTION fin.entry.original add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sen...

  2. [2]

    Hitting-sets for ROABP and Sum of Set-Multilinear circuits

    Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. http://dx.doi.org/10.1137/140975103 Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits . SIAM Journal of Computing , 44(3):669--697, 2015. Pre-print available at http://arxiv.org/abs/1406.7535 arXiv:1406.7535

    work page Pith review arXiv 2015

  3. [3]

    http://dx.doi.org/10.1137/080729256 Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut

    Christoph Amb\" u hl, Monaldo Mastrolilli, and Ola Svensson. http://dx.doi.org/10.1137/080729256 Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut . SIAM Journal on Computing , 40(2):567--596, 2011

    doi:10.1137/080729256

  4. [4]

    http://dx.doi.org/10.1007/978-3-642-32512-0\_2 Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems

    Per Austrin, Toniann Pitassi, and Yu Wu. http://dx.doi.org/10.1007/978-3-642-32512-0\_2 Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambrid...

    doi:10.1007/978-3-642-32512-0

  5. [5]

    Equivalence of-algebras and cubic forms

    Manindra Agrawal and Nitin Saxena. Equivalence of-algebras and cubic forms. In Annual Symposium on Theoretical Aspects of Computer Science , pages 115--126. Springer, 2006

    work page 2006

  6. [6]

    http://dx.doi.org/10.4230/LIPICS.ICALP.2024.16 NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials

    Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha. http://dx.doi.org/10.4230/LIPICS.ICALP.2024.16 NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials . In 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia , volume 297 of LIPIcs , pages 16:...

    work page doi:10.4230/lipics.icalp.2024.16 2024

  7. [7]

    Kulikov, Ivan Mihajlin, and Denil Sharipov

    Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, and Denil Sharipov. http://dx.doi.org/10.1137/1.9781611977554.CH124 Polynomial formulations as a barrier for reduction-based hardness proofs . In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 , pages 3245--3281. SIAM , 2023

    work page doi:10.1137/1.9781611977554.ch124

  8. [8]

    http://dx.doi.org/10.4230/LIPICS.APPROX/RANDOM.2022.21 Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case

    Vishwas Bhargava, Ankit Garg, Neeraj Kayal, and Chandan Saha. http://dx.doi.org/10.4230/LIPICS.APPROX/RANDOM.2022.21 Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022, September 19-21, 2022, University of Illinois,...

    work page doi:10.4230/lipics.approx/random.2022.21 2022

Show all 49 references
  1. [9]

    Randal E. Bryant. http://dx.doi.org/10.1109/TC.1986.1676819 Graph-Based Algorithms for Boolean Function Manipulation . IEEE Transactions on Computers , 35(8):677–691, 1986

    1986

  2. [10]

    http://dx.doi.org/10.1145/3406325.3451096 Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits

    Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich. http://dx.doi.org/10.1145/3406325.3451096 Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits . In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 2...

  3. [11]

    http://dx.doi.org/10.48550/ARXIV.2407.10143 Explicit Commutative ROABPs from Partial Derivatives

    Vishwas Bhargava and Anamay Tengse. http://dx.doi.org/10.48550/ARXIV.2407.10143 Explicit Commutative ROABPs from Partial Derivatives . CoRR , abs/2407.10143, 2024. Pre-print available at http://arxiv.org/abs/2407.10143 arXiv:2407.10143

    2024 doi arXiv

  4. [12]

    The complexity of boolean formula minimization

    toupdate(BU11): doi David Buchfuhrer and Christopher Umans. The complexity of boolean formula minimization. Journal of Computer and System Sciences , 77(1):142--153, 2011

    2011

  5. [13]

    Improving the variable ordering of OBDDs is NP-complete

    toupdate(BI96): doi Beate Bollig and Ingo Wegener. Improving the variable ordering of OBDDs is NP-complete. IEEE Transactions on computers , 45(9):993--1002, 1996

    1996

  6. [14]

    http://dx.doi.org/10.4230/LIPICS.ITCS.2024.25 Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning

    Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, and Tanmay Sinha. http://dx.doi.org/10.4230/LIPICS.ITCS.2024.25 Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning . In 15th Innovations in Theoretical Com...

    2024 doi

  7. [15]

    http://dx.doi.org/10.4230/LIPIcs.STACS.2023.22 On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts

    Suryajith Chillara, Coral Grichener, and Amir Shpilka. http://dx.doi.org/10.4230/LIPIcs.STACS.2023.22 On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts . In 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-9, 2023...

    2023 doi

  8. [16]

    http://dx.doi.org/10.1007/978-0-387-35651-8 Ideals, Varieties and Algorithms

    David A.\ Cox, John B.\ Little, and Donal O'Shea. http://dx.doi.org/10.1007/978-0-387-35651-8 Ideals, Varieties and Algorithms . Undergraduate texts in mathematics. Springer, 2007

    2007 doi

  9. [17]

    https://www.cse.iitk.ac.in/users/nitin/papers/border-depth3.pdf Demystifying the border of depth-3 algebraic circuits

    Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena. https://www.cse.iitk.ac.in/users/nitin/papers/border-depth3.pdf Demystifying the border of depth-3 algebraic circuits . In 2021 , 2021

    2021

  10. [18]

    http://dx.doi.org/10.4230/LIPICS.CCC.2021.11 Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits

    Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena. http://dx.doi.org/10.4230/LIPICS.CCC.2021.11 Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits . In 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (V...

    2021 doi

  11. [19]

    DeMillo and Richard J

    Richard A. DeMillo and Richard J. Lipton. http://dx.doi.org/10.1016/0020-0190(78)90067-4 A Probabilistic Remark on Algebraic Program Testing . Information Processing Letters , 7(4):193--195, 1978

    1978 doi

  12. [20]

    http://dx.doi.org/10.1145/568522.568523 A survey of graph layout problems

    Josep D\' az, Jordi Petit, and Maria Serna. http://dx.doi.org/10.1145/568522.568523 A survey of graph layout problems . ACM Comput. Surv. , 34(3):313–356, September 2002

    2002

  13. [21]

    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 2013 , pages 243--252, 2013. 1209.2408

    2013 arXiv

  14. [22]

    Forbes, Ramprasad Saptharishi, and Amir Shpilka

    Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka. http://dx.doi.org/10.1145/2591796.2591816 Hitting sets for multilinear read-once algebraic branching programs, in any order . In 2014 , pages 867--875, 2014

    2014

  15. [23]

    Garey and David S

    Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness . W. H. Freeman & Co., USA, 1979

    1979

  16. [24]

    http://dx.doi.org/10.4086/toc.2017.v013a002 Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs

    Rohit Gurjar, Arpita Korwar, and Nitin Saxena. http://dx.doi.org/10.4086/toc.2017.v013a002 Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs . Theory of Computing , 13(1):1--21, 2017. 2016 . arXiv:1601.08031

    2017 arXiv

  17. [25]

    Learning sums of powers of low-degree polynomials in the non-degenerate case

    toupdate(GKS20): doi Ankit Garg, Neeraj Kayal, and Chandan Saha. Learning sums of powers of low-degree polynomials in the non-degenerate case. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020 , pages 889--899. I...

    2020

  18. [26]

    http://dx.doi.org/10.1007/s00037-016-0141-z Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs

    Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. http://dx.doi.org/10.1007/s00037-016-0141-z Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs . Computational Complexity , 26(4):835--880, 2017. 2015 . arXiv:1411.7341

    arXiv

  19. [27]

    http://dx.doi.org/10.1016/0196-6774(90)90014-6 Tensor Rank is NP-Complete

    Johan H stad. http://dx.doi.org/10.1016/0196-6774(90)90014-6 Tensor Rank is NP-Complete . J. Algorithms , 11(4):644--654, 1990

    1990 doi

  20. [28]

    http://dx.doi.org/10.1109/FOCS54457.2022.00095 NP-Hardness of Learning Programs and Partial MCSP

    Shuichi Hirahara. http://dx.doi.org/10.1109/FOCS54457.2022.00095 NP-Hardness of Learning Programs and Partial MCSP . In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022 , pages 968--979. IEEE , 2022

    2022

  21. [29]

    Oliveira, and Rahul Santhanam

    Shuichi Hirahara, Igor C. Oliveira, and Rahul Santhanam. http://dx.doi.org/10.4230/LIPICS.CCC.2018.5 NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits . In 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA , volume 102 o...

    2018 doi

  22. [30]

    http://dx.doi.org/10.1109/FOCS52979.2021.00050 The Minimum Formula Size Problem is (ETH) Hard

    Rahul Ilango. http://dx.doi.org/10.1109/FOCS52979.2021.00050 The Minimum Formula Size Problem is (ETH) Hard . In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022 , pages 427--432. IEEE , 2021

    2021

  23. [31]

    http://dx.doi.org/10.1137/1.9781611973082.108 Efficient algorithms for some special cases of the polynomial equivalence problem

    Neeraj Kayal. http://dx.doi.org/10.1137/1.9781611973082.108 Efficient algorithms for some special cases of the polynomial equivalence problem . In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, Janu...

    doi

  24. [32]

    http://eccc.hpi-web.de/report/2015/154/ Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits

    Neeraj Kayal, Vineet Nair, and Chandan Saha. http://eccc.hpi-web.de/report/2015/154/ Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits . Electronic Colloquium on Computational Complexity (ECCC) , 22:154, 2015

    2015

  25. [33]

    Klivans and Amir Shpilka

    Adam R. Klivans and Amir Shpilka. http://dx.doi.org/10.4086/toc.2006.v002a010 Learning Restricted Models of Arithmetic Circuits . Theory of Computing , 2(10):185--206, 2006. 2003

    2006 doi

  26. [34]

    Reconstruction of non-degenerate homogeneous depth three circuits

    toupdate(KS19b): doi Neeraj Kayal and Chandan Saha. Reconstruction of non-degenerate homogeneous depth three circuits. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019 , pages 413--424. ACM , 2019

    2019

  27. [35]

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

    Nutan Limaye, Srikanth Srinivasan, and S \' e bastien Tavenas. http://dx.doi.org/10.1145/3611094 Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits . Communications of the ACM , 67(2):101--108, 2024. 2021

    2024 doi

  28. [36]

    toupdate(M79): doi W. J. Masek. Some NP-complete set covering problems . Unpublished Manuscript , 1979

    1979

  29. [37]

    http://dx.doi.org/https://doi.org/10.1016/j.jsc.2011.12.018 Dimension-dependent bounds for Gr \"o bner bases of polynomial ideals

    Ernst W Mayr and Stephan Ritscher. http://dx.doi.org/https://doi.org/10.1016/j.jsc.2011.12.018 Dimension-dependent bounds for Gr \"o bner bases of polynomial ideals . Journal of Symbolic Computation , 49:78--94, 2013

    2011 doi

  30. [38]

    Monien and I.H

    B. Monien and I.H. Sudborough. http://dx.doi.org/https://doi.org/10.1016/0304-3975(88)90028-X Min cut is NP-complete for edge weighted trees . Theoretical Computer Science , 58(1):209--229, 1988

    1988 doi

  31. [39]

    Algorithms and Data Structures in VLSI Design: OBDD-foundations and applications

    toupdate(MT98): doi Christoph Meinel and Thorsten Theobald. Algorithms and Data Structures in VLSI Design: OBDD-foundations and applications . Springer Science & Business Media, 1998

    1998

  32. [40]

    http://dx.doi.org/10.1145/100216.100242 Psuedorandom Generators for Space-Bounded Computation

    Noam Nisan. http://dx.doi.org/10.1145/100216.100242 Psuedorandom Generators for Space-Bounded Computation . In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA , pages 204--212. ACM , 1990

    1990

  33. [41]

    http://dx.doi.org/10.1145/103418.103462 Lower bounds for non-commutative computation

    Noam Nisan. http://dx.doi.org/10.1145/103418.103462 Lower bounds for non-commutative computation . In 1991 , pages 410--418, 1991. Available on citeseer:10.1.1.17.5067 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.5067

    1991

  34. [42]

    U ber h \

    ystein Ore. \" U ber h \" o here Kongruenzen. Norsk Mat. Forenings Skrifter , 1(7):15, 1922

    1922

  35. [43]

    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 of Computing , 2(1):121--135, 2006. 2004 . Pre-print available at TR04/042

    2006 doi

  36. [44]

    http://dx.doi.org/10.1007/s00037-005-0188-8 Deterministic polynomial identity testing in non-commutative models

    Ran Raz and Amir Shpilka. http://dx.doi.org/10.1007/s00037-005-0188-8 Deterministic polynomial identity testing in non-commutative models . Computational Complexity , 14(1):1--19, 2005. 2004

    2005 doi

  37. [45]

    Schwartz

    Jacob T. Schwartz. http://dx.doi.org/10.1145/322217.322225 F ast P robabilistic A lgorithms for V erification of P olynomial I dentities . Journal of the ACM , 27(4):701--717, 1980

    1980

  38. [46]

    http://arxiv.org/abs/1611.01559 How hard is the tensor rank? , 2016

    Yaroslav Shitov. http://arxiv.org/abs/1611.01559 How hard is the tensor rank? , 2016. Pre-print available at http://arxiv.org/abs/1611.01559 arXiv:1611.01559

    2016 arXiv

  39. [47]

    The nonapproximability of OBDD minimization

    toupdate(S02): doi Detlef Sieling. The nonapproximability of OBDD minimization. Information and Computation , 172(2):103--138, 2002

    2002

  40. [48]

    Branching programs and binary decision diagrams: theory and applications

    toupdate(W00): doi Ingo Wegener. Branching programs and binary decision diagrams: theory and applications . SIAM, 2000

    2000

  41. [49]

    http://dx.doi.org/10.1007/3-540-09519-5_73 Probabilistic algorithms for sparse polynomials

    Richard Zippel. http://dx.doi.org/10.1007/3-540-09519-5_73 Probabilistic algorithms for sparse polynomials . In Symbolic and Algebraic Computation, EUROSAM '79, An International Symposiumon Symbolic and Algebraic Computation , volume 72 of Lecture Notes in Computer Science , p...

    doi

Pith tools

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