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

Introduction

One interesting property of the above randomized algorithm of Schwartz-Zippel is that the algorithm does not need to “see” the circuit $C$. Namely, the algorithm only uses the circuit to compute the evaluations $f(\alpha_{1},\ldots,\alpha_{n})$. Such an algorithm is called a black-box algorithm. In contrast, an algorithm that can access the internal structure of the circuit $C$ is called a white-box algorithm. Clearly, the designer of the algorithm has more resources in the white-box model and so one can expect that solving PIT in this model should be a simpler task than in the black-box model.

The problem of derandomizing PIT has received a lot of attention in the past few years. In particular, many works examine a particular class of circuits $\mathcal{C}$, and design PIT algorithms only for circuits in that class. One reason for this attention is the strong connection between deterministic PIT algorithms for a class $\mathcal{C}$ and lower bounds for $\mathcal{C}$. This connection was first observed by Heintz and Schnorr [HS80] (and also by Agrawal [Agr05]) for the black-box model and by Kabanets and Impagliazzo [KI04] for the white-box model (see also Dvir, Shpilka and Yehudayoff [DSY09]). Another motivation for studying the problem is its relation to algorithmic questions. Indeed, the famous deterministic primality testing algorithm of Agrawal, Kayal and Saxena [AKS04] is based on derandomizing a specific polynomial identity. Finally, the PIT problem is, in some sense, the most general problem that we know today for which we have randomized $\coRP$ algorithms but no polynomial time algorithms, thus studying it is a natural step towards a better understanding of the relation between $\RP$ and $\P$. For more on the PIT problem we refer to the survey by Shpilka and Yehudayoff [SY10].

Although the white-box model seems to be simpler than the black-box model, for most models for which a white-box PIT algorithm is known, a black-box PIT algorithm is also known, albeit sometimes with worse parameters. Such examples include depth-2 circuits (also known as sparse polynomials) [BOT88, KS01], depth-3 $\Sigma\Pi\Sigma(k)$ circuits [SS11], Read-$k$ formulas [AvMV11] and depth-3 tensors (also known as depth-3 set-multilinear circuits) [RS05, FS12]. While the running time of the algorithms for depth-2 circuits and $\Sigma\Pi\Sigma(k)$ circuits are essentially the same in the white-box and black-box models, for Read-$k$ formulas and set-multilinear depth-3 circuits we encounter some loss that results in a quasi-polynomial running time in the black-box model compared to a polynomial time algorithm in the white-box model.

Until this work, the only model for which an efficient white-box algorithm was known without a (sub-exponential) black-box counterpart was the model of non-commutative algebraic formulas, or, more generally, the models of non-commutative algebraic branching programs (ABPs) and set-multilinear algebraic branching programs [RS05] (see Subsection 1.1 for definitions).

The main result in this paper is a quasi-polynomial time PIT algorithm in the black-box model for read-once oblivious algebraic branching programs. Equivalently, we give a hitting set of size $2^{\mathcal{O}(\lg^{2}S)}$ for size $S$ circuits from this model. By tuning parameters in our recursion, we obtain hitting sets of size $2^{\mathcal{O}(\lg^{2}S/\lg\lg S)}$ when the branching programs are also of bounded width. Using our main result we obtain black-box algorithms of similar running times for the models of set-multilinear ABPs, non-commutative ABPs, as well as for diagonal circuits as defined by Saxena [Sax08]. Although exponential lower bounds are known for these models, we note that the algebraic hardness-versus-randomness result of Kabanets and Impagliazzo [KI04] (as well as the extension of this result by Dvir, Shpilka and Yehudayoff [DSY09] to low-depth circuits) does not imply a black-box PIT algorithm for the model, since their technique does not work for the restricted models studied here.

The algebraic circuit models considered in this work, though restricted, have received significant attention in existing work on lower bounds and pseudorandomness, and are strong enough to capture non-trivial derandomization questions arising elsewhere. In Subsection 1.1 we define these models, and state our results in Subsection 1.2. In Subsection 1.3 we discuss various work concerning these models, and explain relations to other areas such as (boolean) space-bounded derandomization, the Noether Normalization Lemma from algebraic geometry, and an algebraic analogue of the natural proofs barrier in boolean lower bounds. In Subsection 1.4, we outline the main proof ideas of the hitting set for read-once ABPs.

The model that we consider in this paper is that of set-multilinear algebraic branching programs. In fact, we will work with a slightly more general model, but we first describe the model of set-multilinear ABPs.

Algebraic branching programs were first defined in the work of Nisan [Nis91] who proved exponential lower bounds on the size of non-commutative ABPs computing the determinant or permanent polynomials.

An algebraic branching program (ABP) is a directed acyclic graph with one vertex of in-degree zero, which is called the source, and one vertex of out-degree zero, which is called the sink. The vertices of the graph are partitioned into levels numbered $0,\ldots,D$. Edges may only go from level $i-1$ to level $i$ for $i=1,\ldots,D$. The source is the only vertex at level and the sink is the only vertex at level $D$. Each edge is labeled with a affine function in the input variables. The width of an ABP is the maximum number of nodes in any layer, and the size of the ABP is the number of vertices.

Each directed source-sink path in the ABP computes a polynomial, which is a product of the labels on the edges in that path. As this work concerns non-commutative computation, we specify that the product of the labels is in the order of the path, from source to sink. The ABP itself computes the sum of all such polynomials.

We consider a slight variation of this model which we call set-multilinear ABP, in line with the term coined by Nisan and Wigderson [NW96]. In the set-multilinear scenario the variables are partitioned into sets

A set-multilinear monomial is a monomial of the form

A set-multilinear algebraic branching program (ABP) in the variable set $X=X_{1}\sqcup X_{2}\sqcup\cdots\sqcup X_{D}$ is an ABP of depth $D$, such that each edge between layer $i-1$ and layer $i$ is labeled with a (homogeneous) linear function in the variable set $X_{i}$.

It is clear from the definition that a set-multilinear ABP computes a set-multilinear polynomial. It is also not hard to see that any set-multilinear polynomial can be computed by a set-multilinear ABP.

In fact, our result holds for the following model, that we call read-once oblivious ABPs, as well.

A read-once oblivious ABP in the variable set $X=\{x_{1},\ldots,x_{D}\}$ is an ABP of depth $D$, such that each edge between layer $i-1$ and layer $i$ is labeled with a univariate polynomial in $x_{i}$ of degree $<n$.

Note that unlike previous definitions, in read-once oblivious ABPs we allow edges to be labeled with arbitrary univariate polynomials (with a bound of $n$ on the degree) and not just with linear forms. Observe that the mapping $x_{i,j}\leftrightarrow x_{i}^{j}$ transforms any set-multilinear ABP into a read-once oblivious ABP and vice versa (when we index $j$ starting at zero).

2 Our results

A black-box PIT algorithm is also known as an explicit hitting set, which we now define. We phrase the definition in generality to capture the notion of hitting sets for non-commutative polynomials, generalizing the usual notion.

The hitting set $\mathcal{H}$ is $t(n)$-explicit if given an index into $\mathcal{H}$, the corresponding element of $\mathcal{H}$ can be computed in $t(n)$-time.

Our main result is a quasi-polynomial time black-box PIT algorithm for read-once oblivious ABPs.

This theorem plays a crucial role in future work by the authors ([FS13]), were we give a derandomization of Noether’s Normalization Lemma in a certain case. In Subsection 1.4 we explain our proof technique and give an overview of the proof. Our technique also yields an improved derandomization when the branching program has small width, which we now state.

Using Theorem 3.22 we obtain black-box PIT algorithms for several related models. We first observe that PIT for set-multilinear ABPs is an immediate corollary of Theorem 3.22. As with read-once oblivious ABPs, we assume that we know the partition of the variables into the $D$ sets, and our results do not hold under permutation of the variables.

Next, we consider the model of non-commutative ABPs (see Section 4). Raz and Shpilka [RS05] gave a polynomial time white-box PIT algorithm for this model and we obtain a quasi-polynomial time black-box PIT algorithm. The evaluation points in our hitting set are vectors of $(D+1)\times(D+1)$ matrices for ABPs of depth $D$. We explain this choice in Section 4. In contrast to the above two results, this result for non-commutative ABPs makes no assumption about the variable ordering, and thus still holds under permutation of the variables.

Saxena [Sax08] defined the model of diagonal circuits (see Section 5 for definition) in an attempt to capture some of the complexity of depth-4 circuits. Relying on the algorithm of [RS05], Saxena obtained a polynomial time white-box PIT algorithm for this model (for a certain setting of the parameters). Saha, Saptharishi and Saxena [SSS11], with the essentially same techniques, later extended Saxena’s white-box results to the so-called semi-diagonal model. Simultaneously and independently of our work, Agrawal, Saha and Saxena [ASS12] gave a black-box PIT algorithm for semi-diagonal depth-4 circuits that runs in quasi-polynomial time in the runtime of the known white-box algorithm, and works over fields of large characteristic.

Using our main theorem and a new reduction from diagonal circuits to read-once oblivious ABPs (Lemma 5.8) we obtain a PIT algorithm for diagonal circuits that runs in time quasi-polynomial in the white-box algorithm given by Saxena. Further, we do so over any characteristic in a unified way. As with our result on non-commutative ABPs, this result makes no assumptions about variable order. With essentially no modification, we obtain similar results for semi-diagonal circuits.

Ramprasad Saptharishi [Sap12] showed that a new notion called evaluation dimension extends the partial derivative technique as used in [Sax08] and that our hitting set holds for this model as well, thus obtaining an alternate proof of Theorem 5.11. We discuss this in Section 6.

Klivans and Shpilka [KS06] gave a polynomial-time learning algorithm for read-once oblivious ABPsThe terminology used in [KS06] is that of learning by multiplicity automata, but these are completely equivalent to read-once oblivious ABPs, as shown in [KS06]., given membership and equivalence queries. That is, they give a deterministic algorithm that can learn an unknown $f$ computed be a small read-once oblivious ABP, given a oracle that evaluates $f$ (“membership query”), as well an oracle such that for any hypothesis $h$ computed by a small read-once oblivious ABP with $h\neq f$, the oracle returns an evaluation point $\vec{x}$ such that $h(\vec{x})\neq f(\vec{x})$ (“equivalence query”). Membership queries can be implemented deterministically given black-box access to $f$, and equivalence queries can be implemented using random queries. That is, by appealing to the Schwartz-Zippel algorithm, distinguishing $h\neq f$ can be done using random evaluations.

Our above results construct hitting sets for read-once oblivious ABPs, and as these are closed under subtraction (that is, for equivalence queries, $h-f$ is also a small read-once oblivious ABP), our hitting set will always contain a distinguishing evaluation for $h$ and $f$, if $h\neq f$. Thus, we can derandomize the equivalence queries needed for [KS06]. Further, our results on set-multilinear ABPs, non-commutative ABPs and semi-diagonal depth-4 circuits, all rely on reductions to read-once oblivious ABPs, and these reductions also hold in the learning setting. We omit further details, and state the following result.

There is a deterministic polynomial-time learning algorithm from membership and equivalence queries that can learn each of the following models: read-once oblivious ABPs, set-multilinear ABPs, non-commutative ABPs and semi-diagonal depth-$4$ circuits. In the first three models the algorithm outputs an hypothesis from the same class as the unknown function, but in the case of semi-diagonal depth-$4$ circuits the outputted hypothesis is a read-once oblivious ABP. Given such query access, the running time of the algorithm is polynomial in the sizeFor convenience here, we define the “size” of a semi-diagonal depth-4 circuit to be some $\poly(n,k,e,d)$, using the notation of Theorem 5.11, even though the actual circuit could be much smaller. of the underlying branching program or circuit.

Furthermore, such membership and equivalence queries can be implemented in randomized-polynomial time, or in deterministic quasi-polynomial time, for any of the classes mentioned above.

3 Related work

This work fits into the research program of derandomizing PIT, in particular derandomizing black-box PIT. However, for many of the models of algebraic circuits studied, there are corresponding boolean circuit models for which derandomization questions can also be asked. In particular, for a class $\mathcal{C}$ of boolean circuits, we can seek to construct a pseudorandom generator $\mathcal{G}:\{0,1\}^{s}\to\{0,1\}^{n}$ for $\mathcal{C}$, such that for any circuit $C\in\mathcal{C}$ on $n$ inputs, we have the $\epsilon$-closeness of distributions $C(\mathcal{G}(U_{s}))\approx_{\epsilon}C(U_{n})$, where $U_{k}$ denotes the uniform distribution on $\{0,1\}^{k}$. Nisan [Nis92] studied pseudorandom generators for space-bounded computation, and for space $S$ computation gave a generator with seed length $s=\mathcal{O}(\lg^{2}S)$. Impagliazzo, Nisan and Wigderson [INW94] later gave a different construction with the same seed length. Randomized space-bounded computation can be modeled with read-once oblivious (boolean) branching programs, and these generators apply to this model of computation as well.

Our work, at its core, studies read-once oblivious (algebraic) branching programs, and we achieve a quasi-polynomial-sized hitting set, corresponding to a seed length of $\mathcal{O}(\lg^{2}S)$ for ABPs of size $S$. Aside from the similarities in the statements of these results, there are some similarities in the high-level techniques as well. Indeed, an interpretation by Raz and Reingold [RR99] argues that the [INW94] generator for space-bounded computation can be seen as recursively partitioning the branching program, using an (boolean) extractor to recycle random bits between the partitions. Similarly, in our work, we use an (algebraic rank) extractor between the partitions.

However, despite the similarities to the boolean regime, our results improve when the branching programs have bounded width. Specifically, our hitting sets (Theorem 3.24) achieve a seed length of $\mathcal{O}(\lg^{2}S/\lg\lg S)$, and it has been a long-standing open problem (see [Vad12, Open Problem 8.6]) to achieve a seed length (for pseudorandom generators, or even hitting sets) of $o(\lg^{2}S)$ for boolean read-once oblivious branching programs of constant width. Despite much recent work (see [BDVY13, SZ11, GMR+12, BRRY10, BV10, KNP11, De11, Ste12]), such seed-lengths are only known for branching programs that are restricted even further, such as regular or permutation branching programs. It is an interesting question as to whether any insights of this paper can achieve a similar seed length in the boolean regime, or in general whether there are any formal connections between algebraic and boolean pseudorandomness for read-once oblivious branching programs.

Derandomizing Noether Normalization:

Mulmuley [Mul12a] (see the full version [Mul12b]) recently showed that the Noether Normalization Lemma (of commutative algebra and algebraic geometry) can in a sense be made constructive, assuming that PIT can be derandomized. This lemma shows, roughly, that in any commutative ring $R$, there is a smaller subring $S\subseteq R$ that captures many of the interesting properties of $R$. The usual proof of this lemma is to take the subring $S$ to be generated by a sufficiently large set of “random” elements from $R$. Thus, one can hope to get a constructive version of this lemma by invoking the appropriate derandomization hypothesis from complexity theory, and Mulmuley shows that derandomization of PIT suffices.

In this work, we give a quasi-polynomial hitting sets for diagonal circuits (Theorem 5.9), making some of Mulmuley’s weaker results unconditional. More interestingly, in follow-up work ([FS13]), we improved Mulmuley’s reduction from Noether Normalization to PIT in the case of the above ring $R$ of invariants, and showed that derandomizing PIT for read-once oblivious ABPs is sufficient for finding any explicit set $T^{\prime}$ of invariants generating the desired subring $S$. By using the results of this paper (Theorem 3.22), one can construct an explicit set $T^{\prime}$ of size $\poly(n,r)^{\log r}$, despite the conjectured hardness of this problem.

Algebraically Natural Proofs:

Razborov and Rudich [RR97] defined the notion of a natural proof, and showed that no natural proof can yield strong lower bounds for many interesting boolean models of computation, assuming widely believed conjectures in cryptography about the existence of pseudorandom functions. Further, they showed that this barrier explains the lack of progress in obtaining such lower bounds, as essentially all of the lower bound techniques known are natural in their sense.

In algebraic complexity, there is also a notion of an algebraically natural proof, and essentially all known lower bounds are natural in this sense (see [Aar08] and [SY10, \defaultS3.9]). However, there is no formal evidence to date that algebraically natural proofs cannot prove strong lower bounds, as there are no candidate constructions for (algebraic) pseudorandom functions. The main known boolean construction, by Goldreich, Goldwasser and Micali [GGM86], does not work in the algebraic regime as the construction uses repeated function composition, which results in a polynomial of exponential degree and as such does not fit in the framework of algebraic complexity theory, which only studies polynomials of polynomial degree.

In this work, we give limited informal evidence that some variant of the GGM construction could yield an algebraically natural proofs barrier. That is, Naor (see [Rei13]) observed that the GGM construction is superficially similar to Nisan’s [Nis92] pseudorandom generator, in that they both use recursive trees of function composition. In this work, we give an algebraic analogue of Nisan’s [Nis92] boolean pseudorandom generator, and as such use repeated function composition. As in the naive algebraization of the GGM construction, a naive implementation of our proof strategy would incur a degree blow-up. While the blow-up would only be quasi-polynomial, it would ultimately result in a hitting set of size $\exp(\lg^{3}S)$ for read-once oblivious ABPs of size $S$, instead of the $\exp(\lg^{2}S)$ that we achieve. To obtain this better result, we introduce an interpolation trick that allows us to control the degree blow-up, even though we use repeated function composition. While this trick alone does not yield the desired algebraic analogue of the GGM construction, it potentially removes the primary obstacle to constructing an algebraic analogue of GGM.

The Partial Derivative Method:

Besides the natural goal of obtaining the most general possible PIT result, the problem of obtaining a black-box version of the algorithm of Raz and Shpilka [RS05] is interesting because of the technique used there. Roughly, the PIT algorithm of [RS05] works for any model of computation that outputs polynomials whose space of partial derivatives is (relatively) low-dimensional. Set-multilinear ABPs, non-commutative ABPs, low-rank tensors, and so called pure algebraic circuits (defined in Nisan and Wigderson [NW96]) are all examples of algebraic models that compute polynomials with that property, and so the algorithm of [RS05] works for them. In some sense using information on the dimension of partial derivatives of a given polynomial is the most applicable technique when trying to prove lower bounds for algebraic circuits (see e.g., [Nis91, NW96, Raz06, Raz09, RSY08, RY09]) and so it was an interesting problem to understand whether this powerful technique could be carried over to the black-box setting. Prior to this work it was not known how to use this low-dimensional property in order to obtain a small hitting set, and this paper achieves this goal. Earlier, in [FS12], we obtained a black-box algorithm for the model of low-rank tensors, but could not prove that it also works for the more general case of set-multilinear ABPs (we still we do not know whether this is the case or not — we discuss the similarities and differences between this and our new algorithm below), so this work closes a gap in our understanding of such low-dimensional models.

Non-commutative ABPs:

While the primary focus of algebraic complexity are polynomials over commutative rings, it has proved challenging to prove lower bounds in sufficiently powerful circuit models because any lower bound would have to exclude any possible “massive cancellation”. Thus, in recent years, attention has turned to non-commutative computation, in the hopes that strong lower bounds would be easier to obtain (see [Nis91, CS07, AJS09, AS10, HWY10a, CHSS11, HWY10b, HY12]).

Similarly, the PIT problem has also been studied in the non-commutative model. While the work of Raz and Shpilka [RS05] establishes a white-box PIT algorithm for non-commutative ABPs, the black-box PIT question for this model is more intricate since one cannot immediately apply the usual Schwartz-Zippel algorithm over non-commutative domains. However, Bogdanov and Wee [BW05] showed how, leveraging the ideas in the Amitsur-Levitzki theorem [AL50], one can reduce non-commutative black-box PIT questions to commutative black-box PIT questions. By then appealing to Schwartz-Zippel, they give the first randomized algorithm for non-commutative PIT. They also discussed the possibility of derandomizing their result and raise a conjecture that if true would lead to a hitting set of size $\approx s^{\lg^{2}s}$ for non-commutative ABPs of size $s$. Our Theorem 4.6 gives a hitting set of size $\approx s^{\lg s}$ and does not require unproven assumptions.

In particular, their conjecture asked about the minimal size of an ABP required to computed a polynomial identity of $n\times n$ matrices. Recall that a polynomial identity of matrices is a non-zero polynomial $f(\vec{x})$ such that no matter which $n\times n$ matrices we substitute for the variables $x_{i}$, $f$ evaluates to the zero matrix. Our work bypasses this conjecture, as we instead give an improved reduction from non-commutative to commutative computation, such that for ABPs the resulting computation is set-multilinear. Our construction consists of $(D+1)\times(D+1)$ strictly-upper-triangular matrices for depth $D$ non-commutative ABPs. It is also not hard to see that there is a non-commutative formula of depth $D+1$ which is a polynomial identity for the space of $(D+1)\times(D+1)$ strictly-upper-triangular matrices. Thus, our result is tight in that it also illustrates that if we go just one dimension up above what is obviously necessary then we can already construct a hitting set.

In [AMS10], Arvind, Mukhopadhyay and Srinivasan gave a deterministic black-box algorithm for identity testing of sparse non-commutative polynomials. The algorithm runs in time polynomial in the number of variables, degree and sparsity of the unknown polynomial. This is similar to the running time achieved in the commutative setting for sparse polynomials (see e.g., [BOT88, KS01]) and in particular it is better than our quasi-polynomial time algorithm. On the other hand our algorithm is more general and works for any non-commutative polynomial that is computed by a small ABP.

We note that in the aforementioned [AMS10], the authors showed how to deterministically learn sparse non-commutative polynomials in time polynomial in the number of variables, degree and sparsity. In contrast, for such polynomials our deterministic algorithm requires quasi-polynomial time. For general non-commutative ABPs [AMS10] also obtained a deterministic polynomial time learning algorithm, but here they need to have the ability to query the ABP also at internal nodes and not just at the output node. Our deterministic algorithm runs in quasi-polynomial time but it does not need to query the ABP at intermediate computations.

Previous Work:

In a previous paper [FS12] we gave a hitting set of quasi-polynomial size for the class of depth-$3$ set-multilinear polynomials. That result is mostly subsumed by the generality of Theorem 3.23, but the previous work has a better dependence on some of the parameters. More importantly, it is interesting to note that the proof in [FS12] is also based on the same intuitive idea of preserving dimension of linear spaces while reducing the number of variables, but in order to prove the results in this paper we had to take a different approach. At a high level the difference can be described as follows. We now summarize the algorithm of [FS12]. First the case of degree $2$ is solved. In this case the tensor is simply a bilinear map. For larger $D$, the algorithm works by first reducing to the bivariate case using the Kronecker substitution $x_{i}\leftarrow x^{n^{i}}$ for $i\leq D/2$ and $x_{i+D/2}\leftarrow y^{n^{i}}$ for $1\leq i\leq D/2$. Appealing now to the bivariate case, we can take $y$ to be some multiple of $x$, and then undo the Kronecker substitution (and applying some degree reduction) to recover a tensor on $D/2$ variables. If we try to implement this approach with ABPs then we immediately run into problems, as the previous work requires that the layers of the ABP are commutative, in that we can re-order the layers. While this is true for depth-3 set-multilinear computation, it is not true for general ABPs. To generalize the ideas to general ABPs, this work respects the ordering of the layers in the ABP. In particular, while the previous work had a top-down recursion, this work follows a bottom-up recursion. We merge variables in adjacent levels of the ABP and then reduce the degree of the resulting polynomial using an (algebraic rank) extractor. We do this iteratively until we are left with a univariate polynomial. Perhaps surprisingly, this gives a set that is simpler to describe as compared to the hitting set in [FS12]. On the other hand, if we restrict ourselves to set-multilinear depth-$3$ circuits then the hitting set of [FS12] is polynomially smaller than the set that we construct here.

Independently and simultaneously with this work, Agrawal, Saha and Saxena [ASS12] obtained results on black-box derandomization of PIT for small-depth set-multilinear formulas, when the partition of the variables into sets is unknown. They obtained a hitting set of size $\exp((2h^{2}\lg(s))^{h+1})$, for size $s$ formulas of multiplicative-depth $h$. We note that their model is both stronger and weaker compared to the models that we consider here. On the one hand, this model does not assume knowledge of the partition of the variables, whereas our model assumes this knowledge. On the other hand, they only handle small-depth formulas, and indeed, the size of their hitting grows doubly-exponentially in the depth, whereas our results handle arbitrary set-multilinear formulas, according to their definition, if we know the partition, and the size of the hitting set grows quasi-polynomially with the depthTheir definition of set-multilinear formulas is actually that of a pure formula (see [NW96]). It is not hard to see that pure formulas form a sub-model of the set-multilinear ABPs we examine in this paper. That is, the usual transformation from formulas to ABPs can be done preserving set-multilinearity.. Using their results for set-multilinear formulas, Agrawal, Saha and Saxena [ASS12] also give a quasipolynomial-sized hitting set for semi-diagonal circuits over large characteristic fields. Our results, in particular our extension of Saxena’s [Sax08] duality to all fields, can help extend the results of [ASS12] to small characteristics as well.

We also mention that in [JQS09, JQS10] Jansen, Qiao and Sarma studied black-box PIT in various models related to algebraic branching programs. Essentially, all these models can be cast as a problem of obtaining black-box PIT for read-once oblivious branching programs where each variable appears on a small number of edges. Their result gives a hitting set of size (roughly) $n^{\mathcal{O}(k\lg(k)\lg(n))}$ when $k$ is an upper bound on the number of edges that a variable can label and the ABP is of polynomial size. In comparison, our Theorem 3.22 gives a hitting set of size $n^{\mathcal{O}(\lg(n))}$ and works for $k=\poly(n)$ (as long as the size of the ABP is polynomial in $n$). Our techniques are very different from those of [JQS09], which follows the proof technique of [SV09]. The later paper [JQS10] use an algebraic analogue of the Impagliazzo-Nisan-Wigderson [INW94] generator, as we do, but the details are different.

4 Proof overview

The first step in our proof is to work with a normal form for read-once oblivious ABPs. Specifically, 3.1 shows that any polynomial $f$ computed in this model can be written asWe use ${\llbracket{n}\rrbracket}$ to denote $\{0,\ldots,n-1\}$. $f(\vec{x})=(\prod_{i\in{\llbracket{D}\rrbracket}}M_{i}(x_{i}))_{(0,0)}$, where each $M_{i}$ is a matrix whose entries are univariate polynomials in the variable $x_{i}$. Next, we observe that for purposes of a stronger inductive hypothesis, we work with matrix-valued polynomials computed as $f(\vec{x})=\prod_{i\in{\llbracket{D}\rrbracket}}M_{i}(x_{i})$. With this view in mind, we can now consider the recursion scheme.

At a high level, our hitting set can be viewed as a repeated application (in parallel) of a “derandomized Kronecker product”. That is, the usual Kronecker product allows us to merge two variables (that is, we merge $x$ and $y$ by taking $y\leftarrow x^{m}$ for large enough $m$) of a polynomial without losing any information. Once a single variable remains, one can resort to full-interpolation of this univariate polynomial. However, this generic transformation rapidly increases the degree of the polynomial and thus the final interpolation step requires too many evaluations to yield a good hitting set.

To find such curves, we use a (seeded) rank extractor. That is, the $n^{2}$ matrices defined by the coefficients of $M(x)N(y)$ live in an $r^{2}$-dimensional space, so we seek to map these $n^{2}$ vectors to a smaller space while preserving rank. Gabizon and Raz [GR08] established such a lemma, and our prior work [FS12] improved the parameters in their lemma. Crucially, these rank extractors have the form such that the maps they define correspond to polynomial evaluations. Thus, these extractors establish (for most values of the seed) an explicit small set of evaluation points where the span of $M(x)N(y)$ is preserved.

While the strategy above will succeed, it will be deficient as the resulting hitting set will be quasi-polynomially larger than desired, and each point in the hitting set will be quasi-polynomially explicit, instead of being polynomially explicit. This deficiency arises from repeated function composition, as we now explain by example. Consider a depth 4, read-once oblivious ABP, written as $M(x,y,z,w):=A(x)B(y)C(z)D(w)$, where $A,B,C,D$ are $r\times r$ matrices with entries that are univariate polynomials degree $<n$. After the first step we have $A(x)B(y)C(z)D(w)\approx A(f(x^{\prime}))B(g(x^{\prime}))C(f(y^{\prime}))D(g(y^{\prime}))$ for two new variables $x^{\prime}$ and $y^{\prime}$. Viewing this matrix product as a read once oblivious ABP in the two variables $x^{\prime}$ and $y^{\prime}$, we can repeat the variable merging procedure, to obtain

for a new variable $x^{\prime\prime}$. While this reduction is desirable, as we can now fully interpolate the single final variable $x^{\prime\prime}$ to obtain a hitting set, the degree in the final $x^{\prime\prime}$ is $r^{2}\cdot r^{2}=r^{4}$, instead of remaining $r^{2}$. That is, to reduce from $D$ variables to a single variable, we will use at least $\lg D$ compositions of the $f,g$ polynomials, yielding a degree of at least $r^{\Omega(\lg D)}$. As there are $\lg D$ levels of recursion, and each requires a seed matching the degree of the ABPs, this will imply that the resulting hitting set is of size $r^{\Omega(\lg^{2}D)}$, which is larger than what we achieve in this work. Further, this hitting set is not even polynomially explicit, as computing it requires evaluating polynomials of quasipolynomial degree, which potentially requires quasipolynomial bit-length when computing over the rationals.

To achieve better results when the width $r$ of the ABP is small, we keep the paradigm from above, but change the branching factor of the recursion. That is, in the above recursion we merged pairs of variables at each level, so that if we start with $D$ variables we need $\lg D$ levels of recursion, and the curves involved will have $\poly(r)$ degree. By changing to a branching factor of $B$, we use $\log_{B}D$ levels of recursion, and the curves involved will have $\approx\poly(r)^{B}$ degree. As the number of levels in the recursion equals the number of seeds we use, and the degree of the curves (along with the degree $n$ of the ABP) governs the number of values to try for each seed, we can see that choosing $B=\log_{r}D$ yields $\lg D/\lg\lg D\cdot\lg r$ seeds, and each seed will take $\poly(n,D)$ values. For $r=\mathcal{O}(1)$, this yields a hitting set of size $\poly(n,D)^{O(\lg D/\lg\lg D)}$.

In the boolean regime, changing the branching factor of recursion in the pseudorandom generators of Nisan [Nis92] or Impagliazzo-Nisan-Wigderson [INW94] is not known to achieve such savings. This seems to be because each application of the extractor (viewed as an averaging sampler) has a sample complexity that depends on the total number of variables in the branching program, which is needed so the error does not become too large. It follows that increasing the branching factor simply multiples the seed length by $B/\lg B$, which only becomes worse as $B$ increases. In contrast, the rank extractor used here has a sample complexity that depends only on the width of the ABP, and the number of total variables only affects the extractor in the number of seeds needed. Thus, the seed-length grows as $(B\lg r+\lg n+\lg D)\lg D/\lg B$, which allows us to balance parameters by taking $B\lg r\approx\lg D$.

Notation

Hitting Set for Read-Once Oblivious ABPs

In this section, we construct a hitting set for read-once oblivious ABPs. To make the questions more amenable to study, we give the following normal form for read-once oblivious ABPs.

Conversely, any such function can be computed by a width $r$, depth $D$, read-once oblivious ABP.

matrices$\implies$ ABP: This is similar to the above. ∎

Thus, instead of talking about such ABPs, we will be discussing products of matrices $\prod_{i}M_{i}(x_{i})$. For induction purposes we will not be restricting ourselves to the $(0,0)$-th entry, but will consider the full matrices. Such products naturally correspond to multi-source multi-sink ABPs.

We will begin the formal statements of this section by giving lemmas on the span of matrices, and how preserving the span of linear transformations can be used for PIT. We begin by showing that the span of ABPs can be preserved in a recursive fashion.

As $\mathcal{M}\cdot\mathcal{N}\subseteq\operatorname{span}(\mathcal{M})\cdot\operatorname{span}(\mathcal{N})$ we see that $\operatorname{span}(\mathcal{M}\cdot\mathcal{N})\subseteq\operatorname{span}(\operatorname{span}(\mathcal{M})\cdot\operatorname{span}(\mathcal{N}))$ by linearity. To show the other direction, consider any $A\in\operatorname{span}(\operatorname{span}(\mathcal{M})\cdot\operatorname{span}(\mathcal{N}))$. Then $A=\sum_{i}c_{i}(\sum_{j}a_{i,j}M_{j})(\sum_{k}b_{i,k}N_{k})$, for $M_{j}\in\mathcal{M}$ and $N_{k}\in\mathcal{N}$. Thus, by bilinearity of the matrix product, $A=\sum_{i,j,k}c_{i}a_{i,j}b_{i,k}M_{j}N_{k}$, where $M_{j}N_{k}\in\mathcal{M}\cdot\mathcal{N}$, and thus $A\in\operatorname{span}(\mathcal{M}\cdot\mathcal{N})$, yielding the first claim.

The second claim follows from the first, by observing that $\operatorname{span}(\mathcal{M}\cdot\mathcal{N})=\operatorname{span}(\operatorname{span}(\mathcal{M})\cdot\operatorname{span}(\mathcal{N}))=\operatorname{span}(\operatorname{span}(\mathcal{M}^{\prime})\cdot\operatorname{span}(\mathcal{N}^{\prime}))=\operatorname{span}(\mathcal{M}^{\prime}\cdot\mathcal{N}^{\prime})$. ∎

We will use this as follows. By 3.1 we can restrict our attention to matrix-valued functions of the form $f(\vec{x})=\prod_{i\in{\llbracket{D}\rrbracket}}M_{i}(x_{i})$, and we work in this level of generality for ease of induction. As such, $f$ defines a space of matrices $\mathcal{A}$ by evaluating the polynomial on all possible inputs. Crucially for PIT, we see that $\operatorname{span}(\mathcal{A})$ is zero iff $f$ is zero. By breaking the matrix product in $f$ into variable disjoint left- and right-halves (each on $\approx D/2$ variables), we can see that this space of matrices factorizes into $\mathcal{A}=\mathcal{A}_{0}\cdot\mathcal{A}_{1}$, corresponding to the evaluations of the separate halves of the ABP. Now, because these halves are variable disjoint, we can in parallel find smaller spaces of matrices such that $\operatorname{span}(\mathcal{A}^{\prime}_{c})=\operatorname{span}(\mathcal{A}_{c})$ for $c\in\{0,1\}$. From the above lemma, we now see that $\operatorname{span}(\mathcal{A})=\operatorname{span}(\mathcal{A}^{\prime}_{0}\cdot\mathcal{A}^{\prime}_{1})$. The operation “$\mathcal{A}^{\prime}_{0}\cdot\mathcal{A}^{\prime}_{1}$” squares the number of matrices under consideration, so to complete the picture we “derandomize” this Kronecker product to yield a “small” family of matrices $\mathcal{A}^{\prime}$ such that $\operatorname{span}(\mathcal{A})=\operatorname{span}(\mathcal{A}^{\prime})$. It follows then that PIT of the original function $f$ reduces to testing each matrix in $\mathcal{A}^{\prime}$ for non-zeroness, which will correspond to fully interpolating a univariate polynomial.

To implement the above program, our main challenge is to thus construct the derandomized Kronecker product. To do so, our next lemma shows that the span of a layer of a read-once oblivious ABP can be viewed either as the span of the evaluations of that layer, or of the (finite) number of (matrix-valued) coefficients of that layer. We will use both characterizations of the span of a layer.

$\subseteq$: Note that $M(\alpha)=\sum_{i=0}^{\deg(M)}\operatorname{\mathfrak{C}}_{x^{i}}(M)\cdot\alpha^{i}$, and thus is in $\operatorname{span}\{\operatorname{\mathfrak{C}}_{x^{i}}(M)\}_{i=0}^{\deg(M)}$, for any $\alpha$.

We now cite a dimension reduction lemma that shows how we can map a vector space of rank $\leq r$, in a large ambient dimension $n$, to a vector space of the same rank in an ambient dimension $r$ (and thus, is a “rank extractor”). A lemma of this sort was first established by Gabizon and Raz [GR08]. That lemma would also work for us, but the version we cite has slightly better parameters.

We now apply this dimension reduction to read-once oblivious ABPs, by observing that even though the result $M(x)N(x^{n})$ of the Kronecker product induces a linear space of transformations most naturally parameterized by the $\approx n^{2}$ coefficients of this polynomial (as in 3.3), each transformation is an $r\times r$ matrix, and so this linear space of transformations more naturally lives in an $r^{2}$-dimensional vector space. Thus, by applying dimension reduction, we make a first step in getting a derandomized Kronecker product.

and except for $<n^{2}r^{2}$ values of $\alpha$,

We now use these polynomials to construct curves passing through the evaluation points shown in 3.5, to yield a reduction of a two-layer read-once oblivious ABP to a one-layer read-once oblivious ABP. We will phrase the result more generally, so that we can apply induction.

Putting equations (3.8), (3.9), and (3.10) together yields the claim. ∎

Nevertheless, this lemma is enough for constructing a hitting set, as the resulting span is still inside that of $\prod_{i}M_{i}(x_{i})\cdot\prod_{i}N_{i}(y_{i})$, which is ultimately the polynomial whose span we are trying to replicate. In such applications, we will start off (by induction) with $f_{i}$ and $g_{i}$ such that

and so as the “$\subseteq$” in 3.7 nests between the two terms in this equality, we will in fact get “$=$” in the lemma in this case, so will not turn zero polynomials into non-zero polynomials.

2 The Generator for Read-Once Oblivious ABPs

In this section we construct the hitting set for read-once oblivious ABPs. The hitting set is more naturally presented as a generator, which we now define. See also the survey [SY10] for more on generators.

Given a generator $\mathcal{G}$, one can show that $\mathcal{G}(S^{t})$ is a hitting set for $\mathcal{C}$ as long as $|S|$ is polynomially large in the relevant parameters. We present this formally in 3.21. Given this relation to hitting sets, we now proceed to the construction of our generator, and then prove the requisite properties.

We now establish properties of this construction. We first prove an easy lemma that gives an upper bound on the degrees of the variables $\alpha_{i}$ in $\mathcal{G}$.

Assume the setup of 3.13. Let $\vec{b}\in\{0,1\}^{\llbracket{d}\rrbracket}$.

For $i\in{\llbracket{d}\rrbracket}$, $\deg_{\alpha_{i}}(\mathcal{G}_{d,\vec{b}}(\vec{\alpha}))\leq Dnr^{4}$.

For $i=d$, $\deg_{\alpha_{d}}(\mathcal{G}_{d,\vec{b}}(\vec{\alpha}))\leq r^{2}\leq Dnr^{4}$.

The next lemma demonstrates the recursive structure of $\mathcal{G}$.

Assume the setup of 3.13. For $\vec{b}\in\{0,1\}^{\llbracket{d-1}\rrbracket}$, $b_{d-1}\in\{0,1\}$, and $\vec{\alpha}$ denoting the variables $\alpha_{i}$ for $i\in{\llbracket{d-1}\rrbracket}$,

This claim follows from the definitions, with some rearrangement of terms.

We now show that the generator can be efficiently computed.

by the properties of matrix multiplication. By 3.1 we see that this matrix product can be computed by a width $r^{2}$, depth $d+1$, read-once oblivious ABP, and the degree bound follows from 3.16. ∎

We now turn to proving that our construction is indeed a generator for read-once oblivious ABPs. In particular, we first show the generator preserves span.

d>0𝑑0d>0:

We will split the span into the multiplication of two different spans, and then appeal to 3.7 to merge these two spans.

Similarly, for $c\in\{0,1\}$, and $\vec{\alpha}$ being the vector of variables $\alpha_{i}$ for $i\in{\llbracket{d-1}\rrbracket}$, denote

It follows from definition that $\mathcal{M}=\mathcal{M}_{0}\cdot\mathcal{M}_{1}$, and by induction, we have that $\operatorname{span}\mathcal{M}_{c}=\operatorname{span}\mathcal{M}^{\prime}_{c}$. Thus, 3.2 implies that $\operatorname{span}\mathcal{M}=\operatorname{span}(\operatorname{span}(\mathcal{M}^{\prime}_{0})\cdot\operatorname{span}(\mathcal{M}^{\prime}_{1}))=\operatorname{span}(\mathcal{M}^{\prime}_{0}\cdot\mathcal{M}^{\prime}_{1})$. Observe that $\operatorname{span}\mathcal{M}^{\prime}\subseteq\operatorname{span}\mathcal{M}=\operatorname{span}(\mathcal{M}^{\prime}_{0}\cdot\mathcal{M}^{\prime}_{1})$, so the claim will follow from showing that $\operatorname{span}(\mathcal{M}^{\prime}_{0}\cdot\mathcal{M}^{\prime}_{1})\subseteq\operatorname{span}\mathcal{M}^{\prime}$.

Thus taking this for each $\vec{\alpha}$ we get $\operatorname{span}(\mathcal{M}^{\prime}_{0}\cdot\mathcal{M}^{\prime}_{1})\subseteq\operatorname{span}\mathcal{M}^{\prime}$, implying $\operatorname{span}\mathcal{M}^{\prime}=\operatorname{span}\mathcal{M}$ as desired. ∎

The next lemma concludes that the span-preservation property shows that we indeed have a generator, and can thus construct a hitting set.

We note that Theorem 3.23 is an immediate corollary.

By the degree bounds, the Kronecker map $x_{i,j}\leftarrow x_{i}^{j}$ induces a bijection among the monomials, and takes the original set-multilinear ABP to a read-once oblivious ABP, where we replace the set of variables $\vec{X}_{i}$ with the single (new) variable $x_{i}$. Structurally, this is still an width $r$, depth $D$ ABP, and as we index from zero, the individual degrees are $<n$. Appealing to Theorem 3.22 gives the result. ∎

3 Small width read-once oblivious ABPs

The proof of Theorem 3.22 used a recursion scheme that merges pairs of variables in each level of the recursion. By merging variables in larger groups, we can achieve better results when the width $r$ of the ABP is small.

The details are similar to that of Theorem 3.22, except that instead of merging pairs of variables at once, we merge $B=\log_{r}D$ variables at once. The merging of Theorem 3.22 first merges variables via the Kronecker product, and then reduces to a single variable via the rank extractor. However, this would create degrees in the $\alpha$’s of $\geq(Dn)^{B}$, which would not give any savings in the $r\leq\mathcal{O}(1)$ case.

Instead, to merge $B$ variables together, we first apply the rank extractor to each variable to find $\poly(r)$ (seeded) points that preserve the span. We can then pass curves in a new variable through the Cartesian product of these points, and this will yield a new ABP in a single variable with the same span. As constructed, this requires curves of degree $\poly(r)^{B}$ in the generator, and when composed with the ABP itself will induce degrees of only $\poly(D,n,r^{B})$ in the seeds $\alpha$. By using this new merging scheme in our recursion, it follows then that when $r\leq\mathcal{O}(1)$ we can take $B=\log_{r}D$ and the $\alpha_{i}$ will all have $\poly(n,D)$-degree, and we have $\log_{B}D$ such $\alpha_{i}$, resulting in a hitting set of size $\poly(D,n)^{\mathcal{O}(\lg D/\lg\lg D)}$. ∎

Non-commutative ABPs

We proceed, by giving a family of matrices with entries consisting of commutative variables, such that any non-zero non-commutative polynomial $f$ over these matrices induces a non-zero family of commutative polynomials over the commutative variables. Further, we show that if $f$ is computable by a small non-commutative ABP, then the resulting commutative polynomials are computable by small set-multilinear ABPs. We can then appeal to the hitting set for this class of polynomials, shown in Theorem 3.23. We first illustrate the construction of our matrices.

Define the vector $\vec{X}_{D}:=(X_{i,D})_{i\in{\llbracket{n}\rrbracket}}$.

Thus, pictorially, we have that the matrices $X_{i,D}$ look as follows.

These matrices are quite similar to the matrices used in [BW05] (see their Lemma 3.2), but they achieve a smaller dimension (in fact, matching the best possible, as seen by the Amitsur-Levitzki theorem). However, their construction does not seem to give the reduction to set-multilinear computation that we need. We now establish properties of our construction. In particular, we relate the evaluations of $f$ on the matrices $X_{i}$, to the commutative polynomial $\varphi(f)$.

We now use this to give the black-box reduction from non-commutative polynomials to set-multilinear polynomials.

We now show that for ABPs as the above lemma outputs (those with only homogeneous linear forms on the edges) there is a clear connection between the ABP complexity of $f$ and $\varphi(f)$.

By linearity, it is enough to prove the claim for a single path in the ABP $A$. The path computes the product of its labels, and thus yields the product of linear forms

Similarly, the same path in $A^{\prime}$ computes

which equals $\varphi(g)$ by linearity, as desired. Finally, we see that the edges from layer $j-1$ to layer $j$ only involve the variables $x_{\bullet,j}$, so the ABP is indeed set-multilinear. ∎

Combining the above results, we can now give the full reduction.

Plugging in our hitting set for set-multilinear ABPs from Theorem 3.23, we obtain the following corollary.

The use of $(D+1)\times(D+1)$ strictly upper-triangular matrices in the above results is optimal, in the sense that if we used $m\times m$ strictly upper-triangular matrices for $m<D+1$ then no such result is possible, as any such matrix $X$ has $X^{D}=0$, and the monomial $x^{D}$ is computable by a depth $D$ ABP.

Diagonal Circuits

The model of diagonal circuits was first defined by Saxena [Sax08] in order to better understand depth-4 circuits. Much previous PIT research focused on small-depth circuits with restricted top fan-in. In contrast, the diagonal model allows unbounded top fan-in, but each multiplication gate only has few distinct factors (but the factors can have high multiplicity).

A diagonal depth-4 circuit has the form $\Phi=\sum_{i=1}^{k}\Psi_{i}$, where each product gate $\Psi_{i}$ is of the form $\Psi_{i}=\vec{P}_{i}^{\vec{e}_{i}}$, and each $P_{i,j}(\vec{x})$ is a sum of univariate polynomials, $P_{i,j}=\sum_{m=1}^{n}g_{i,j,m}(x_{m})$. The syntactic degree of the polynomial computed by the circuit is $\operatorname{s-deg}(\Phi)=\max_{i}\deg(\Psi_{i})$, where $\deg(\Psi_{i})=\sum_{j}e_{i,j}\deg(P_{i,j})$ (i.e. the syntactic degree of $\Phi$ is the maximal degree of a multiplication gate $\Psi_{i}$ in $\Phi$).

Saxena [Sax08] proved the following theorem, establishing a white-box PIT algorithm for diagonal depth-4 circuits.

There is a deterministic algorithm that, given as input a diagonal depth-4 circuit $\Phi$, runs in time $\poly(nk\cdot\operatorname{s-deg}(\Phi),\max_{i\in[k]}{|\vec{e}_{i}|_{\times}})$ and decides whether $\Phi\equiv 0$.

We give a black-box PIT algorithm for diagonal depth-4 circuits whose running time is quasi-polynomial in the runtime established by Saxena. Saxena gave a white-box reduction from diagonal depth-4 circuits to non-commutative PIT over algebras, and claimed that the Raz-Shpilka [RS05] algorithm can be extended to handle this case. Our result uses a poly-time black-box reduction from diagonal depth-4 circuits to read-once oblivious ABPs. We follow Saxena’s duality idea, but “pull” the complexity of the algebras he works with into the ABP itself. We can then apply our hitting sets on read-once oblivious ABPs, which incurs the quasi-polynomial overhead.

Note that this is a formal identity, that is, there is no notion of convergence needed as each coefficient in the power series of $\exp(f(\vec{x},\vec{c})z)$ is the sum of finitely many non-zero terms. It follows then that

Even though the above proof used the exponential function, which has no exact analogue in positive characteristic, the final statement is just one of polynomials, and thus transfers to any field of sufficiently large characteristic. In particular, the characteristic must be $>|\vec{e}\>\!|_{\infty}$, the maximum exponent. We now transfer this duality to any field. We will abuse notation and treat the characteristic zero case as working over characteristic $p$, where $p=\infty$. Note that the “base-$\infty$” expansion of any integer is just that integer itself, followed by zeroes.

Write $e_{j}$ in its base-$p$ expansion, so that $e_{j}=\sum_{k\in{\llbracket{n_{j}}\rrbracket}}a_{j,k}p^{k}$ with $a_{j,k}\in{\llbracket{p}\rrbracket}$. Denote $Q_{j,k}(\vec{x}):=\sum_{m}g_{j,m}(x_{m})^{p^{k}}$ and $\vec{Q}^{\vec{a}}:=\prod_{j}\prod_{k}Q_{j,k}^{a_{j,k}}$. Then, $\vec{P}^{\vec{e}}=\vec{Q}^{\vec{a}}$ and

and $|\vec{a}|_{\times}\leq|\vec{e}|_{\times}$.

$\vec{P}^{\vec{e}}=\vec{Q}^{\vec{a}}$: This follows from the Frobenius automorphism, that $(x+y)^{p^{k}}=x^{p^{k}}+y^{p^{k}}$ for any $k\geq 0$, in any field of characteristic $p$. That is,

$|\vec{a}|_{\times}\leq|\vec{e}\>\!|_{\times}$: As $|\vec{e}\>\!|_{\times}=\prod_{j}(1+e_{j})$ and $|\vec{a}|_{\times}=\prod_{j}\prod_{k\in{\llbracket{n_{j}}\rrbracket}}(1+a_{j,k})$, it is sufficient to prove that $\prod_{k}(1+a_{k})\leq 1+e$, for $e=\sum_{k}a_{k}p^{k}$ with $a_{k}\in{\llbracket{p}\rrbracket}$. To see this, first define $T:=\{e^{\prime}:0\leq e^{\prime}\leq e\}$ and note that $|T|=1+e$. Second, let $S=\{e^{\prime}:e^{\prime}=\sum_{k}a^{\prime}_{k}p^{k},0\leq a^{\prime}_{k}\leq a_{k}\}$. Observe that $S\subseteq T$, and $|S|=\prod_{k}(1+a_{k})$, so $\prod_{k}(1+a_{k})=|S|\leq|T|=1+e$. ∎

To use this lemma, we first need a structural result about ABPs. In this lemma we broaden the notion of an ABP to have arbitrary labels from a commutative ring $\mathcal{R}[\vec{x}]$, and will specialize this to our setting later.

Further, the edge labels between layers $i-1$ and $i$ in $A^{\prime}$ occur as coefficients of the edge labels between layers $i-1$ and $i$ in $A$.

For each edge $(v\times(i-1),v^{\prime}\times i)$ in $A$ with label $g\in\mathcal{R}[\vec{z}]$, and each $\vec{a},\vec{a}^{\prime}\in S$ with $\vec{a}\leq\vec{a}^{\prime}$, define the edge label $(v\times\vec{a}\times(i-1),v^{\prime}\times\vec{a}^{\prime}\times i)$ to be $\operatorname{\mathfrak{C}}_{\vec{z}^{\vec{a}^{\prime}-\vec{a}}}(g)$. Letting the source of $A$ be denoted $s\times 0$, and the sink denotes $t\times D$, we define the source of $A^{\prime}$ to be $s\times\vec{0}\times 0$ and the sink to be $t\times\vec{e}\times D$. After removing nodes that belong to no source-sink path, it is clear that $A^{\prime}$ is a layered ABP, with depth $D$, width $\leq r\cdot|\vec{e}|_{\times}$. Further, the edge labels between layers $i-1$ and $i$ in $A^{\prime}$ are coefficients of the edge labels between layers $i-1$ and $i$ in $A$ as desired. It remains to show that $A^{\prime}$ computes as desired, which follows from an induction on layers. Specifically, one can see that the paths from the source of $A^{\prime}$ to $v\times\vec{a}\times i$ compute $\operatorname{\mathfrak{C}}_{\vec{z}^{\vec{a}}}(f_{v\times i})$, where $f_{v\times i}$ is the polynomial computed by the paths from the source in $A$ to $v\times i$. ∎

We now apply this structural result, along with Saxena’s dual form, to show that depth-4 diagonal circuits can be computed by small read-once oblivious ABPs.

Now, observe that the read-once oblivious ABPs for the $\Psi_{i}$ can be summed by merging all sources and merging all sinks, and that the resulting ABP $A$ is read-once oblivious, as the variable ordering of $\vec{x}$ is consistent amongst the $A_{i}$. It follows that $A$ has the desired properties. ∎

As the above lemma is constructive, it follows that white-box access to $f$ implies white-box access to the read-once oblivious ABP $A$, and thus we could run the white-box algorithm of Raz-Shpilka [RS05] to derive a white-box PIT algorithm, in order to rederive Saxena’s result (over any field). However, as we also have black-box PIT algorithms for read-once oblivious ABPs (and the above uses the fixed variable order $x_{1}<\cdots<x_{n}$), and the above reduction does not need access to $f$, we can combine these results to deduce the following black-box PIT result for diagonal depth-4 circuits.

From 5.8 we get that any $\Phi\in\mathcal{DC}$ can be computed by a read-once oblivious ABP on variable order $x_{1}<\cdots<x_{n}$, of depth $n$, width $\leq ke$, with each edge label being a univariate of degree $\leq\operatorname{s-deg}(\Psi)$. Noting that $\operatorname{s-deg}(\vec{P}_{i}^{\vec{e}_{i}})\leq|\vec{e}_{i}|_{1}\cdot d<|\vec{e}_{i}|_{\times}\cdot d$, we invoke Theorem 3.22 to finish the claim. ∎

We remark here that the concurrent work of Agrawal, Saha and Saxena [ASS12] also obtain a quasi-polynomial hitting set for diagonal depth-4 circuits (when they assume each product gate is over a constant number of factors), but only over large characteristic, as they rely on the duality statements of Saxena [Sax08] (and later exposited by Saha, Saptharishi, and Saxena [SSS11]) which only hold over large characteristic. Over small characteristic, [Sax08] and [SSS11] gave more cumbersome duality statements working over prime-power characteristic, and [ASS12] do not extend their work to this case.

Our duality statements work any characteristic, and as such can show that the work of [ASS12] also implies results for diagonal circuits over any characteristic. In particular, instead of using 5.5 to construct an ABP, one can interpolate the coefficient $\vec{z}^{\vec{e}}$ in 5.5, and this can be done in depth-3, although the resulting formula is inherently larger than the resulting ABP would be.

In Saha, Saptharishi, and Saxena [SSS11] the model of semi-diagonal depth-4 circuits was introduced as a small extension of diagonal depth-4 circuits. The modification is that one is allowed to multiply each product gate $\Psi_{i}=\vec{P}^{\vec{e}}$ by an arbitrary monomial. [SSS11] used that the duality result of Saxena [Sax08] can also be shown to work in this setting. The concurrent work of Agrawal, Saha and Saxena [ASS12] thus present their results for semi-diagonal depth-4 circuits, as opposed to just diagonal depth-4 circuits. For ease of comparison, we also state our result for this model. As multiplication by a single monomial in 5.5 preserves the variable disjoint product structure (but increases the degree), it follows that we can still convert semi-diagonal circuits to read-once oblivious ABPs, as stated in 5.8. Thus, as the details are the same, we conclude the following result.

Evaluation dimension

The content of this section was communicated to us by Ramprasad Saptharishi [Sap12].

We leave the proofs of the next lemmas to the reader.

If the dimension of the partial derivative space of $f$ is bounded by $r$, then $\operatorname{evaldim}(f)\leq r$.

Note that the converse is not necessarily true as demonstrated by the polynomial $(\sum_{i=1}^{n}x_{i}^{2})^{n}$.

Depth-$4$ diagonal circuits (as given in 5.1) have $\poly(nk\cdot\operatorname{s-deg}(\Phi),\max_{i\in[k]}{|\vec{e}_{i}|_{\times}})$ evaluation dimension.

Saptharishi [Sap12] observed that our proof technique for constructing hitting sets for read-once oblivious ABPs can be applied also to polynomials with small evaluation dimension. We give here an alternate proof of that fact, showing that any polynomial with small evaluation dimension can be computed by a small width read-once oblivious ABP.

Let $f$ be an $D$-variate, degree $<n$ polynomial, of evaluation dimension $\leq r$. Then $f$ can be computed by a width $\leq rn^{2}$, depth $D$, degree $<n$ read-once oblivious ABP (in any variable ordering).

One can note, by polynomial interpolation, that for any set $S\subseteq[n]$, the dimension

is equal to the rank of the partial derivative matrix of the variable partition $[n]=S\sqcup\bar{S}$, as defined by Nisan [Nis91] in the context of non-commutative computation. Now fix an arbitrary variable ordering. As read-once oblivious ABPs invoke variables in this fixed ordering, they can be seen as non-commutative ABPs with all monomials respecting the variable ordering. Nisan showed that for a homogeneous non-commutative polynomial $f$, one can construct a non-commutative ABP computing $f$ whose width is equal to the maximum rank of a partial derivative matrix of $f$, where the partition $S\sqcup\bar{S}$ respects the non-commutative multiplication. Applying this result to read-once oblivious ABPs we observe that, by standard homogenization, each homogeneous part of the target polynomial $f$ has evaluation dimension at most $rn$, so can be computed by a width $rn$ read-one oblivious ABP. Summing up the $n$ homogeneous parts gives the result. ∎

Applying this result with Theorem 3.22 we get the following corollary.

The class of $n$-variate degree-$d$ polynomials of evaluation dimension bounded by $r$ has a black-box PIT running in time $\poly(n,d,r)^{\mathcal{O}(\lg n)}$.

Finally, we mention that Saptharishi [Sap12] also showed that evaluation dimension can be used in the white box setting to obtain new PIT algorithms for semi-diagonal depth-$4$ circuits.

Discussion

This work closes some gap in our understanding of white-box PIT vs. black-box PIT by transferring algorithms that used the partial derivative technique to the black-box world. The recent work of [ASS12] made another significant step by considering set-multilinear formulas (of small depth) where the partition is unknown. It will be very interesting to try and combine these two works to obtain a PIT algorithm for set-multilinear ABPs when the underlying partition is not known.

Another interesting goal is to truly close the gap between white-box and black-box. Specifically, all black-box algorithms for the models studied in this paper (as well as in [ASS12]) run with a quasi-polynomial overhead over the run-times of the corresponding known white-box algorithms. Ideally, this overhead could be made polynomial.

Finally, it will be interesting to understand whether analog of Theorem 3.24 can be obtained in the Boolean setting using our ideas.

Acknowledgments

Much of this work was done when the first author was visiting the second author at the Technion, some while the first author was an intern at Microsoft Research Silicon Valley. We would like to thank Andy Drucker, Omer Reingold, Ramprasad Saptharishi, Ilya Volkovich and Sergey Yekhanin for some helpful conversations. We thank Ketan Mulmuley for sharing [Mul12a] with us. We thank Ramprasad for allowing us to include his result on evaluation dimension (see Section 6) here. We also thank Avi Wigderson for raising the question of whether our technique could yield better results for the bounded width case.

References