PaperlayerView exact revision on arXiv

Source-linked AI summary

Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs

Michael A. Forbes, Amir Shpilka

arXiv:1209.2408v2cs.CC

TL;DR

The paper addresses the lack of black-box PIT for read-once oblivious ABPs despite a known white-box algorithm. It constructs quasi-polynomial hitting sets, with a stronger bound for constant-width programs.

  • Problem

    Before this work, ABPs had known white-box PIT but no sub-exponential black-box counterpart; deterministic PIT is also connected to circuit lower bounds.

    Source: §1 · p. 2

  • Method

    The paper constructs hitting sets using degree reduction based on linear spaces of transformations rather than monomial matching.

    Source: §1.4 · p. 11

  • Results

    Hitting sets have size poly(D,n,r)^O(lg D), improving to poly(D,n)^O(lg D/lg lg D) at constant width; related circuit classes are also covered.

    Source: §1 · p. 3, §1.2 · pp. 4–5

  • Takeaways & Limitations

    The work transfers PIT algorithms using partial derivatives to the black-box setting for several restricted algebraic models.

    Source: §7 · p. 32

    The black-box algorithms still have quasi-polynomial overhead over corresponding known white-box algorithms.

    Source: §7 · p. 32

Abstract

from arXiv · show

We study the problem of obtaining deterministic black-box polynomial identity testing algorithms (PIT) for algebraic branching programs (ABPs) that are read-once and oblivious. This class has an deterministic white-box polynomial identity testing algorithm (due to Raz and Shpilka), but prior to this work there was no known such black-box algorithm. The main result of this work gives the first quasi-polynomial sized hitting sets for size S circuits from this class, when the order of the variables is known. As our hitting set is of size exp(lg^2 S), this is analogous (in the terminology of boolean pseudorandomness) to a seed-length of lg^2 S, which is the seed length of the pseudorandom generators of Nisan and Impagliazzo-Nisan-Wigderson for read-once oblivious boolean branching programs. Our results are stronger for branching programs of bounded width, where we give a hitting set of size exp(lg^2 S/lglg S), corresponding to a seed length of lg^2 S/lglg S. This is in stark contrast to the known results for read-once oblivious boolean branching programs of bounded width, where no pseudorandom generator (or hitting set) with seed length o(lg^2 S) is known. In follow up work, we strengthened a result of Mulmuley, and showed that derandomizing a particular case of the Noether Normalization Lemma is reducible to black-box PIT of read-once oblivious ABPs. Using the results of the present work, this gives a derandomization of Noether Normalization in that case, which Mulmuley conjectured would difficult due to its relations to problems in algebraic geometry. We also show that several other circuit classes can be black-box reduced to read-once oblivious ABPs, including set-multilinear ABPs (a generalization of depth-3 set-multilinear formulas), non-commutative ABPs (generalizing non-commutative formulas), and (semi-)diagonal depth-4 circuits (as introduced by Saxena).

1 Introduction

The introduction presents the paper’s quasi-polynomial black-box PIT results for read-once oblivious ABPs, their reductions to related circuit classes, and connections to bounded-width pseudorandomness and Noether Normalization. It also outlines a variable-merging method and a change in recursion branching factor that improves hitting-set size for bounded-width ABPs.

1 Introduction

  • PIT asks whether a circuit computes the zero polynomial; derandomizing its randomized evaluation test is a central open problem linked to circuit lower bounds and algorithmic questions.Before this work, non-commutative formulas and ABPs, and set-multilinear ABPs, lacked efficient white-box counterparts with sub-exponential black-box algorithms.Source: §1 · p. 2

1.1 The model

  • An ABP sums source-to-sink path products, with edge labels multiplied in path order; read-once oblivious ABPs use univariate labels for the variable assigned to each layer.Set-multilinear ABPs instead assign each layer homogeneous linear forms from its corresponding variable set; the two models are interconvertible by reindexing variables.Source: §1.1 · pp. 3–4

1.2 Our results

  • For |F| ≥ poly(D, n, r), width-r, depth-D read-once oblivious ABPs have explicit hitting sets of size ≤ poly(D, n, r)^O(lg D); bounded width improves this to poly(D, n)^O(lg D / lg lg D).Both results assume individual degree < n; the bounded-width theorem assumes r ≤ O(1) and |F| ≥ poly(D, n).Source: §1.2 · pp. 4–5
  • The main theorem yields quasi-polynomial black-box PIT for set-multilinear ABPs with a known variable partition, and for non-commutative ABPs without a variable-order assumption.The non-commutative hitting set evaluates on vectors of (D+1) × (D+1) matrices.Source: §1.2 · p. 5
  • Reductions from diagonal circuits to read-once oblivious ABPs give quasi-polynomial black-box PIT for diagonal and semi-diagonal depth-4 circuits over fields of arbitrary characteristic.The diagonal-circuit result makes no variable-order assumption; the semi-diagonal hitting set has size ≤ poly(n, d, k, e)^O(lg n).Source: §1.2 · p. 5
  • A deterministic polynomial-time learning algorithm extends to read-once oblivious, set-multilinear, non-commutative, and semi-diagonal models using membership and equivalence queries.For semi-diagonal circuits, the algorithm outputs a read-once oblivious ABP hypothesis; the queries can be implemented in randomized polynomial or deterministic quasi-polynomial time.Source: §1.2 · p. 6

1.3 Related work

  • The algebraic hitting sets correspond to seed length O(lg^2 S), while the bounded-width result gives O(lg^2 S / lg lg S), unlike the known constant-width boolean case with no o(lg^2 S) seed length.The paper notes similarities between its recursive technique and boolean generators, but leaves formal connections between algebraic and boolean pseudorandomness open.Source: §1.3 · pp. 6–7
  • Using Theorem 3.22, the authors’ follow-up shows that PIT for read-once oblivious ABPs suffices to construct an explicit generating set of size poly(n, r)^log r for the stated invariant ring.This improves Mulmuley’s reduction for that Noether Normalization case; the paper’s diagonal-circuit hitting sets also make some of his weaker results unconditional.Source: §1.3 · p. 7
  • The paper gives an algebraic analogue of Nisan’s generator and uses an interpolation trick to control degree growth, achieving exp(lg^2 S) rather than exp(lg^3 S).The trick potentially removes the primary obstacle to an algebraic analogue of GGM, though it does not alone yield that construction.Source: §1.3 · p. 8
  • The work turns the low-dimensional partial-derivative property used by Raz and Shpilka into a small black-box hitting set, extending the method to models including set-multilinear and non-commutative ABPs.Previously, the property supported white-box testing, while a black-box algorithm was known for low-rank tensors but not the more general set-multilinear ABPs.Source: §1.3 · p. 8
  • For non-commutative ABPs, Theorem 4.6 gives a hitting set of size ≈s^lg s without unproven assumptions, using an improved reduction to set-multilinear computation.The reduction uses (D + 1) × (D + 1) strictly upper-triangular matrices for depth-D ABPs.Source: Non-commutative ABPs · p. 9
  • Unlike the top-down method of, which relies on reorderable commutative layers, this work merges adjacent ABP layers bottom-up and then reduces degree.For depth-3 set-multilinear circuits, however, has a polynomially smaller hitting set.Source: Non-commutative ABPs · pp. 9–10

1.4 Proof overview

  • A rank-extractor-based degree reduction preserves the span of transformations induced by adjacent ABP layers, enabling variable merging with curves of degree less than r^2.The span is zero exactly when the corresponding matrix-valued polynomial is zero, so preserving it retains the information needed for identity testing.Source: §1.4 · p. 11
  • Recognizing known function compositions lets the recursion lift extractor points back to the original variables, avoiding the degree blow-up of generic repeated composition.The resulting curves have degree poly(r), which remains stable across recursive merges because the ABP width does not change.Source: §1.4 · p. 12
  • For width r = O(1), choosing branching factor B = log_r D gives a hitting set of size poly(n, D)^O(lg D / lglg D).This choice uses lg D / lglg D · lg r seeds, with poly(n, D) values tried per seed.Source: §1.4 · p. 12

2 Notation

This section establishes the paper’s indexing conventions for sets, vectors, matrices, and polynomial coefficients. It also defines homogeneous parts and ordered non-commutative products.

2 Notation

  • [n] denotes {1, . . . , n}, while JnK denotes {0, . . . , n −1}; ⊔ denotes disjoint union.The indicator function 1_P denotes membership in a set or event P.Source: §2 · p. 13
  • Vectors and matrices are indexed from zero unless stated otherwise; [n] marks indexing from one.I denotes the identity matrix, and M_i,• and M_•,j denote row i and column j.Source: §2 · p. 13
  • The notation C_x^α(f) extracts a monomial coefficient, while H_k(f) denotes the degree-k homogeneous part.The section also defines polynomial-vector powers, matrix degree and span, and coefficients when polynomials in y have coefficients in x.Source: §2 · p. 13
  • Non-commutative matrix products proceed left to right in increasing index order, with indexed products over bit vectors ordered lexicographically.The least-significant bit is the rightmost bit.Source: §2 · p. 13

3 Hitting Set for Read-Once Oblivious ABPs

This section develops explicit hitting sets for read-once oblivious ABPs and set-multilinear ABPs through recursive constructions. It also gives a smaller hitting set for constant-width read-once oblivious ABPs.

3.1 Derandomized Kronecker Product for the Span of an ABP

  • Recursively splitting matrix products into variable-disjoint halves and replacing each half by an equal-span family enables a derandomized Kronecker product while preserving the full product span.Lagrange interpolation constructs curves through the required evaluation points, but the resulting span is generally only contained in the original span; the induction arranges nested spans to recover equality.Source: §3.1 · pp. 14, 16, 17

3.2 The Generator for Read-Once Oblivious ABPs

  • The generator preserves the span of matrix evaluations, so zero testing reduces to testing its composition on a finite grid, using the degree bound deg_αi(f ◦ Gd) < Dn^2r^4.Its coordinates are computable by width-r^2, depth-(d+1) read-once oblivious ABPs, though closure under composition—and thus direct recursive use—remains unclear.Source: §3.2 · pp. 18, 19, 21
  • Lemma 3.7 permits fewer than D^2n^2r^6 bad parameter values, whereas Lemma 3.21 needs only Dn^2r^4; the direct improvement is left unresolved.The authors note that it is unclear how to sharpen Lemma 3.7 to obtain the smaller bound directly.Source: §3.2 · p. 20
  • A poly(D,n,r)-explicit hitting set of size at most (2Dn^2r^4)^(⌈lg D⌉+1) exists when |F| ≥ (2Dnr^3)^2.The result applies to width-r, depth-D read-once oblivious ABPs with individual degree less than n.Source: §3.2 · p. 21
  • Set-multilinear ABPs have a poly(D, n, r)-explicit hitting set of size at most (2Dn^2r^4)^(⌈lg D⌉+1) when |F| ≥ (2Dnr^3)^2.The theorem covers width-r, depth-D ABPs over a known partition into D variable sets of n variables each.Source: §3.2 · p. 21
  • The set-multilinear result follows by replacing each variable set with one variable, yielding a read-once oblivious ABP with individual degrees < n.This transformation preserves the width and depth, and a bijection between monomials supports the reduction.Source: §3.2 · p. 21

3.3 Small width read-once oblivious ABPs

  • For constant-width read-once oblivious ABPs, the hitting set has size at most poly(D, n)^O(lg D / lg lg D) when |F| ≥ poly(D, n).The theorem assumes width r ≤ O(1), depth D, and individual degree < n.Source: §3.3 · p. 21
  • For constant width, the recursion merges B = log_r D variables at once, using rank-extractor points and curves to keep seed degrees polynomial in D and n.This yields log_B D seeds and the stated poly(D, n)^O(lg D / lg lg D) hitting-set size.Source: §3.3 · pp. 21–22

4 Non-commutative ABPs

The section reduces black-box identity testing for non-commutative ABPs to testing set-multilinear polynomials using matrix substitutions. The resulting construction gives explicit quasi-polynomial hitting sets, with the matrix dimension chosen to preserve degree-D behavior.

4 Non-commutative ABPs

  • The construction substitutes upper-triangular matrices with commutative-variable entries so nonzero non-commutative polynomials induce nonzero commutative polynomials.The induced polynomials are set-multilinear, enabling use of the set-multilinear ABP hitting set.Source: §4 · pp. 23–24
  • The reduction does not extend directly to general non-commutative circuits, because reused subcomputations obstruct a consistent global variable ordering.ABPs retain a source-to-sink layer order, allowing the reduction to control the transformed computation.Source: §4 · p. 24
  • Theorem 4.6 transfers a hitting set for the corresponding set-multilinear ABPs into a hitting set for width-r, depth-D non-commutative ABPs.The matrix evaluation points are obtained from the set-multilinear hitting-set points by the construction’s matrix substitution.Source: §4 · p. 25
  • For a width-r, depth-D non-commutative ABP, homogeneous components yield set-multilinear ABPs of width at most rD and depth at most D.The construction relies on ABP layer order to transform homogeneous edge labels into variables indexed by layer.Source: §4 · p. 25
  • Corollary 4.7 gives NC, the class of n-variate non-commutative polynomials computable by width r, depth D ABPs, a poly(D,n,r)-explicit hitting set over (D+1)×(D+1) matrices of size ≤(2(D+1)^4 n^2 r^3)^(⌈lg D⌉+1).The field-size condition is |F| ≥ (2(D+1)^5 n r^4)^2.Source: §4 · p. 26
  • Matrices of dimension D + 1 are necessary for this construction: smaller strictly upper-triangular matrices annihilate x^D.The paper notes that x^D is computable by a depth-D ABP.Source: §4 · p. 26

5 Diagonal Circuits

This section gives black-box PIT for diagonal and semi-diagonal depth-4 circuits by reducing them to read-once oblivious ABPs. Its duality works over arbitrary characteristic, and the resulting hitting sets have quasi-polynomial size.

5 Diagonal Circuits

  • The reduction gives diagonal-circuit black-box PIT with quasi-polynomial overhead over Saxena’s white-box runtime by applying read-once oblivious ABP hitting sets.It is a polynomial-time black-box reduction and uses a fixed variable order.Source: §5 · pp. 26, 30
  • The duality works over all fields and extends the earlier approach to positive characteristic using individual degree and Frobenius automorphisms.The paper also notes that this duality lets Agrawal, Saha, and Saxena’s results apply over any characteristic.Source: §5 · pp. 27, 30
  • A depth-4 diagonal circuit with k product gates has a read-once oblivious ABP of depth n and width at most k · maxi∈[k] |e_i|×, with edge-label degrees at most s-deg(f).The construction uses coefficient extraction from products whose j-th factor involves only x_j, then merges the ABPs for the product gates.Source: §5 · p. 29
  • For diagonal depth-4 circuits, if |F| ≥ (2ndk3e4)2, there is a poly(n, k, e, d)-explicit hitting set of size ≤ (2nd2k4e6)⌈lg n⌉+1.The circuit parameters satisfy |e_i|× ≤ e and deg(P_i,j) ≤ d.Source: §5 · p. 30

5.1 Semi-diagonal Depth-4 circuits

  • The same reduction handles semi-diagonal circuits because multiplying a product gate by one monomial preserves its variable-disjoint product structure while increasing degree.This extends the diagonal-circuit result to the semi-diagonal model, where each product gate may include an arbitrary monomial.Source: §5.1 · p. 30
  • For semi-diagonal depth-4 circuits, if |F| ≥ (4ndk3e4)2, there is a poly(n, k, e, d)-explicit hitting set of size ≤ (8nd2k4e6)⌈lg n⌉+1.Here each product gate may also include a monomial of degree at most d.Source: §5.1 · p. 30

6 Evaluation dimension

This section relates evaluation dimension to read-once oblivious ABPs and black-box PIT. It also distinguishes evaluation dimension from partial-derivative-space dimension, for which only a one-way implication is given.

6 Evaluation dimension

  • A partial-derivative space of dimension at most r implies evaluation dimension at most r, but the converse need not hold.The paper notes a polynomial example demonstrating that the converse is not necessary.Source: §6 · p. 31
  • The construction converts small evaluation dimension into a small-width read-once oblivious ABP, which can then be tested using the paper’s hitting-set result.The section applies Theorem 3.22 to obtain the black-box PIT corollary.Source: §6 · p. 31
  • An n-variate degree-<n polynomial of evaluation dimension at most r has a read-once oblivious ABP of depth D and width at most rn2, in any variable ordering.The ABP also has degree < n.Source: §6 · p. 31
  • Polynomials of evaluation dimension at most r have black-box PIT running in time poly(n, d, r)O(lg n).This is the stated corollary for n-variate degree-d polynomials.Source: §6 · p. 31

7 Discussion

The discussion identifies remaining gaps between white-box and black-box PIT and points to combining this work with results for set-multilinear formulas. It notes that current black-box algorithms still have quasi-polynomial overhead.

7 Discussion

  • Combining this work with results for set-multilinear formulas is proposed as a route toward PIT for set-multilinear ABPs when their partition is unknown.The discussion frames this as an interesting direction, not a result established here.Source: §7 · p. 32
  • Across the models studied here and in, known black-box algorithms have quasi-polynomial overhead over corresponding white-box runtimes; polynomial overhead remains an open goal.The discussion also asks whether an analogue of Theorem 3.24 can be obtained in the Boolean setting.Source: §7 · p. 32
Loading 1209.2408v2…