TL;DR
This paper investigates the problem of finding an optimal variable ordering for Read-Once Oblivious Algebraic Branching Programs (ROABPs). The authors prove that this problem is NP-hard in the worst case, even for constant-degree polynomials, by reducing it from the CutWidth problem. They also present efficient algorithms for finding such orderings in the average/generic case.
What Problem Does This Paper Address?
Algebraic Branching Programs (ABPs) are a fundamental model in algebraic circuit complexity. Read-Once Oblivious ABPs (ROABPs) are a restricted but still powerful variant that have connections to various areas, including polynomial identity testing and learning algorithms. A key property of ROABPs is that their size and structure can depend heavily on the order in which variables are processed. The "order-finding problem" for ROABPs asks: given a polynomial and a target width, does there exist a variable ordering such that the polynomial can be represented by an ROABP of that width? This problem is crucial for understanding the complexity of ROABPs and for developing efficient algorithms. The paper addresses the computational complexity of this order-finding problem, both in the worst-case and in the average/generic case.
Methods
The paper employs a combination of theoretical tools:
- NP-Hardness Proof: The authors establish NP-hardness for the order-finding problem by constructing a polynomial-time Karp reduction from the CutWidth problem on graphs. This reduction is exact, meaning it preserves the width relationship precisely. This allows them to leverage existing hardness results for CutWidth to prove hardness for ROABP order-finding.
- Algorithmic Approaches: For the average and generic cases, the authors develop algorithms that exploit the algebraic-geometric properties of ROABPs. They leverage Nisan's characterization of ROABP width, which relates it to the rank of specific matrices derived from the polynomial. Their algorithms involve exploring sets of variables that satisfy certain rank conditions and then using these to construct a valid ordering.
- Polynomial Transformations: To prove the existence of a PTAS from a constant-factor approximation algorithm, they introduce a "black-box" transformation that increases the ROABP width multiplicatively. This transformation allows them to boost approximation ratios.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- NP-Hardness for Constant Degree: Perhaps the most surprising result is that the order-finding problem for ROABPs is NP-hard even when the input polynomial has a constant total degree. This implies that even simple polynomials can pose significant challenges for finding optimal orderings.
- Exact Reduction to CutWidth: The precise relationship established between ROABP width and graph CutWidth is a powerful tool. It not only proves hardness but also suggests that insights from graph theory can be directly applied to algebraic complexity.
- Generic Case Efficiency: The paper demonstrates that while the worst-case is hard, the problem becomes tractable for "generic" or "random" polynomials. This is a common theme in algebraic complexity, where special cases often exhibit much simpler behavior.
- PTAS Construction: The method for constructing a PTAS from a constant-factor approximation algorithm is a standard technique but is applied here to the ROABP order-finding problem, showing its broad applicability.
Key Results
- NP-Hardness: The order-finding problem for ROABPs is NP-hard, even for polynomials given in dense representation with constant total degree.
- Algorithmic Efficiency: An algorithm is presented that solves the order-finding problem in randomized time $n^{O(\log w)}$ (or $poly(n, d, w)$ when $w$ is polynomial) for generic/random ROABPs. This is a significant improvement over the naive $n!$ approach.
- PTAS Implication: An $\alpha$-approximation algorithm for ROABP order-finding implies a $(1+\epsilon)$-approximation algorithm (a PTAS) for any constant $\alpha$.
Limitations and Future Work
- Approximation Hardness: While the paper shows that a constant-factor approximation algorithm implies a PTAS, it does not establish a hardness result for constant-factor approximation of ROABP width itself, unlike for the related CutWidth problem (under the SSE conjecture).
- Average Case Field Size: The paper's average-case results rely on large enough fields. An open question is whether Algorithm 1 runs in randomized polynomial time for fields of polynomial size.
- Poly-time Approximation: Another open question is whether there exist efficient algorithms that approximate ROABP width up to a poly$(w, n, d)$ approximation factor.
Summary updated