Authors Rohit Gurjar, Arpita Korwar, Nitin Saxena,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21
www.theoryofcomputing.org
S PECIAL ISSUE : CCC 2016
Identity Testing for Constant-Width, and
Any-Order, Read-Once Oblivious Arithmetic
Branching Programs
Rohit Gurjar∗ Arpita Korwar Nitin Saxena†
Received June 15, 2016; Revised April 9, 2017; Published May 15, 2017
Abstract: We give improved hitting sets for two special cases of Read-once Oblivious
Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known order
of the variables. The best previously known hitting set for this case had size (nw)O(log n)
where n is the number of variables and w is the width of the ROABP. Even for a constant-
width ROABP, nothing better than a quasi-polynomial bound was known. We improve
the hitting-set size for the known-order case to nO(log w) . In particular, this gives the first
polynomial-size hitting set for constant-width ROABP (known-order). However, our hitting
set only works when the characteristic of the field is zero or large enough. To construct the
hitting set, we use the concept of the rank of the partial derivative matrix. Unlike previous
approaches which build up from mapping variables to monomials, we map variables to
polynomials directly.
A conference version of this paper appeared in the Proceedings of the 31st Computational Complexity Conference,
2016 [16].
∗ Supported by DFG grant TH 472/4.
† Supported by DST-SERB.
ACM Classification: F.2.2
AMS Classification: 68Q25, 68W30
Key words and phrases: polynomial identity testing, hitting sets, arithmetic branching programs
© 2017 Rohit Gurjar, Arpita Korwar, and Nitin Saxena
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2017.v013a002
ROHIT G URJAR , A RPITA KORWAR , AND N ITIN S AXENA
The second case we consider is that of polynomials computable by width-w ROABPs
in any order of the variables. The best previously known hitting set for this case had size
d O(log w) (nw)O(log log w) , where d is the individual degree. We improve the hitting-set size to
(ndw)O(log log w) .
1 Introduction
The polynomial identity testing (PIT) problem asks if a given multivariate polynomial is identically
zero. The input to the problem is given via an arithmetic model computing a polynomial, for example,
an arithmetic circuit, which is the arithmetic analogue of a Boolean circuit. The degree of the given
polynomial is assumed to be polynomially bounded in the circuit size. Typically, any such circuit can
compute a polynomial with exponentially many monomials (exponential in the circuit size). Thus,
one cannot hope to write down the polynomial in a sum-of-monomials form. However, given such an
input, it is possible to efficiently evaluate the polynomial at a point in the field. This property enables
a randomized polynomial identity test with one-sided error. It is known that evaluating a small-degree
nonzero polynomial over a random point gives a nonzero value with a good probability [13, 29, 33]. This
gives us a randomized PIT—just evaluate the input polynomial, given as an arithmetic circuit, at random
points.
Finding an efficient deterministic algorithm for PIT has been a major open question in complexity
theory. The question is also related to arithmetic circuit lower bounds [1, 18, 21]. The PIT problem has
been studied in two paradigms: (i) blackbox test, where one can only evaluate the polynomial at chosen
points and (ii) whitebox test, where one has access to the description of the input circuit. A blackbox
test for a family of polynomials is essentially the same as finding a hitting set—a set of points such that
any nonzero polynomial in that family evaluates to a nonzero value on at least one of the points in the
set. This work concerns finding hitting sets for a special model called read-once oblivious arithmetic
branching programs (ROABP).
An arithmetic branching program (ABP) is a specialized arithmetic circuit. It is the arithmetic
analogue of a Boolean branching program (also known as a binary decision diagram). It is a directed
layered graph, with edges going from a layer of vertices to the next layer. The first and the last layers have
one vertex each, called the source and the sink, respectively. Each edge of the graph has a label, which
is a “simple” polynomial, for example, a univariate polynomial. For any path p, its weight is defined
to be the product of labels on all the edges in p. The ABP computes a polynomial which is the sum of
weights of all the paths from the source to the sink. Apart from its size, another important parameter for
an ABP is its width. The width of an ABP is the maximum number of vertices in any of its layers. See
Definition 2.1 for a formal definition of ABP.
ABPs are a strong model for computing polynomials. It is known that for any size-s arithmetic
circuit of degree bounded by poly(s), one can find an ABP of size quasi-poly(s) computing the same
polynomial [32, 31, 7] (see [23] for a complete proof). Even when the width is restricted to a constant,
the ABP model is quite powerful. Ben-Or and Cleve [6] have shown that width-3 ABPs have the same
expressive power as polynomial-sized arithmetic formulas.
An ABP is a read-once oblivious ABP or ROABP if each variable occurs in at most one layer of the
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 2
I DENTITY T ESTING FOR R EAD -O NCE O BLIVIOUS B RANCHING P ROGRAMS
edges and every layer has exactly one variable.1 The read-once property severely restricts the power
of the ABP. There is an explicit family of polynomials that can be computed by simple depth-3 (ΣΠΣ)
circuits but requires exponential-size ROABPs [22] to compute it. The order of the variables in the
consecutive layers is said to be the variable order of the ROABP. The variable order affects the size
of the minimal ROABP computing a given polynomial. There are polynomials which have a small
ROABP in one variable order but require exponential size in another variable order. Nisan [25] gave an
exact characterization of the polynomials computed by width-w ROABPs in a certain variable order. In
particular, he gave exponential lower bounds for this model.2
The question of whitebox identity testing of ROABPs has been settled by Raz and Shpilka [28], who
gave a polynomial-time algorithm for this. However, though ROABPs are a relatively well-understood
model, we still do not have a polynomial-time blackbox algorithm. The blackbox PIT question is studied
with two variations: one where we know the variable order of the ROABP and the other where we do not
know it. For known-order ROABPs, Forbes and Shpilka [15] gave the first efficient blackbox test with
(ndw)O(log n) time complexity, where n is the number of variables, w is the width of the ROABP and d is
the individual-degree bound of each variable. For the unknown-order case, Forbes et al. [14] gave an
nO(d log w log n) -time blackbox test. Observe that the complexity of their algorithm is quasi-polynomial only
when d is small. Subsequently, Agrawal et al. [2] removed the exponential dependence on the individual
degree. They gave an (ndw)O(log n) -time blackbox test for the unknown-order case. Note that these results
remain quasi-polynomial even in the case of constant width. Studying ROABPs has also led to PIT results
for other computational models, for example, subexponential-size hitting sets for depth-3 multilinear
circuits [12] and subexponential-time whitebox test for read-k oblivious ABPs [4].
Another motivation to study ROABPs comes from their Boolean analogues, called read-once ordered
branching programs (ROBP).3 ROBPs have been studied extensively, with regard to the RL versus L
question (randomized log-space versus log-space). The problem of finding hitting sets for ROABP can be
viewed as an analogue of finding pseudorandom generators (PRG) for ROBP. A pseudorandom generator
for a Boolean function f is an algorithm which can generate a probability distribution (with a small
sample space) with the property that f cannot distinguish it from the uniform random distribution (see [5]
for details). Constructing an optimal PRG for ROBP, i. e., with O(log n) seed length or polynomial-size
sample space, would imply RL = L. Although the known pseudorandom generators for ROBPs and
hitting-set generators for ROABPs in similar settings have similar complexity, there is no known way to
translate the construction of one to another. The best known PRG is of seed length O(log2 n) (nO(log n) -size
sample space), when variable order is known [26, 20, 27]. On the other hand, in the unknown-order
case, the best known seed length is of size n1/2+o(1) [19]. Finding an O(log n)-seed PRG even for
constant-width known-order ROBPs has been a challenging open question. Though, some special cases
of this question have been solved—width-2 ROBPs [8], or nearly solved—permutation and regular
ROBPs [9, 10, 24, 11, 30].
Our first result addresses the analogous question in the arithmetic setting. We give the first polynomial-
time blackbox test for constant-width known-order ROABPs. However, it works only for zero or large
1 In a read-once ABP, each variable occurs only once on every source-sink path. An ROABP is a read-once ABP where every
occurrence of a variable is in the same layer.
2 The work of [25] is actually on non-commutative ABPs but the same results apply to ROABP.
3 ROBPs are also known as Ordered Binary Decision Diagrams (OBDDs).
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 3
ROHIT G URJAR , A RPITA KORWAR , AND N ITIN S AXENA
characteristic fields. Our idea is inspired by the pseudorandom generator for ROBPs by Impagliazzo,
Nisan and Wigderson [20]. While their result does not give better PRGs for the constant-width case, we
are able to achieve this in the arithmetic setting.
Theorem (Theorem 3.6). Let C be the class of n-variate, individual-degree-d polynomials in F[x]
computed by a width-w ROABP in the variable order (x1 , x2 , . . . , xn ). Then a hitting set of size dnO(log w)
can be constructed for C, when char(F) = 0 or char(F) > ndwlog n .
When w < n, the size of our hitting set is smaller than the previously known hitting sets. Furthermore,
even in the regime when w ≥ n, the size of our hitting set matches the previously best known hitting sets.
We show that for a nonzero bivariate polynomial f (x1 , x2 ) computed by a width-w ROABP, the univariate
polynomial f (t w ,t w + t w−1 ) is nonzero. For this, we use the notion of rank of the partial derivative matrix
of a polynomial, defined by Nisan [25]. Our argument is that the rank of the partial derivative matrix of
any bivariate polynomial which becomes zero on (t w ,t w + t w−1 ) is more than w, while for a polynomial
computed by a width-w ROABP, this rank is at most w. We use the map (x1 , x2 ) 7→ (t w ,t w + t w−1 )
recursively in log n rounds to achieve the above mentioned hitting set. Our technique has a crucial
difference from the previous works on ROABPs [14, 15, 2]. The starting point in all the previous
techniques is a monomial map, i. e., each variable is mapped to a monomial. On the other hand, we
argue with a polynomial map directly (where each variable is mapped to a univariate polynomial). We
believe that our approach could lead to a polynomial-size hitting set for ROABPs and we now describe
a concrete construction that we conjecture works. The goal would be to obtain a univariate n-tuple
(p1 (t), . . . , pn (t)), such that any polynomial which becomes zero on (p1 (t), . . . , pn (t)) must have rank or
evaluation dimension higher than w. We conjecture that (t r , (t + 1)r , . . . , (t + n − 1)r ) is one such tuple,
where r is polynomially large (Conjecture 3.8).
We believe that these ideas from the arithmetic setting can help in constructing an optimal PRG for
constant-width ROBP.
Our second result is for the class of polynomials which are computable by ROABPs in any variable
order. To be precise, a polynomial f (x) is in this class if for every permutation of the variables, there
exists an ROABP of width-w that computes f (x) in that variable order. This class of polynomials has a
slightly better hitting set than the class of polynomials computed by ROABPs in a particular variable
order, but still no polynomial-size hitting set is known. The previously best known hitting set for them
has size d O(log w) (nw)O(log log w) [14]. We improve this to (ndw)O(log log w) .
Theorem (Theorem 4.9). For n-variate, individual-degree-d polynomials computed by width-w ROABPs
in any order, a hitting set of size (ndw)O(log log w) can be constructed.
To obtain this result we follow the approach of Forbes et al. [14], which used the notion of rank
concentration or low-support concentration, a technique introduced by Agrawal et al. [3]. We achieve
rank concentration more efficiently using the basis isolation technique of Agrawal et al. [2]. The same
technique also yields a more efficient concentration in depth-3 set-multilinear circuits (see Section 2 for
the definition). However, it is not clear if it gives better hitting sets for them. The best known hitting set
for them has size nO(log n) [3].
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 4
I DENTITY T ESTING FOR R EAD -O NCE O BLIVIOUS B RANCHING P ROGRAMS
2 Preliminaries
2.1 Definitions and notation
We write [n] to denote the set {1, 2, . . . , n} and [[d]] to denote the set {0, 1, . . . , d}. The character x
will denote a list of variables, usually the list (x1 , x2 , . . . , xn ). For a field F, we denote the ring of
polynomials over F by F[x], and the field of rational functions over F by F(t). For a set x of n variables
and for an exponent a = (a1 , a2 , . . . , an ) ∈ {0, 1, 2, . . . }n , we denote the monomial ∏ni=1 xiai by xa . The
support of a monomial xa , denoted by Supp(a), is the set of variables appearing in that monomial, i. e.,
{xi | i ∈ [n], ai > 0}. The support size of a monomial is the cardinality of its support, denoted by supp(a).
A monomial is said to be `-support if its support size is ` and (< `)-support if its support size is < `. For
a polynomial P(x), the coefficient of a monomial xa in P(x) is denoted by coefP (xa ).
For a monomial xa , the sum ∑i ai is said to be its degree and ai is said to be its degree in variable xi
for each i. Similarly, for a polynomial P, its degree (or degree in xi ) is the maximum degree (or maximum
degree in xi ) of any monomial in P with a nonzero coefficient. We define the individual degree of P to be
maxi {degxi (P)}, where degxi denotes degree in xi .
To better understand polynomials computed by ROABPs, we often use polynomials over an algebra
A, i. e., polynomials whose coefficients come from A. Matrix algebra is the vector space of matrices
equipped with the matrix product. Fm×n represents the set of all m × n matrices over the field F. Note
that the algebra of w × w matrices, has dimension w2 .
We often view a vector/matrix with polynomial entries, as a polynomial with vector/matrix coefficients.
For example,
1 + x y − xy 1 0 1 0 0 1 0 −1
D(x, y) = = 1+ x+ y+ xy .
x + y 1 + xy 0 1 1 0 1 0 0 1
Here, the coefD operator will return a matrix for any monomial, for example,
0 1
coefD (y) = .
1 0
For a polynomial D(x) ∈ A[x] over an algebra, its coefficient space is the space spanned by its coefficients.
For a matrix R, we denote its entry in the i-th row and j-th column by R(i, j).
As mentioned earlier, a deterministic blackbox PIT is equivalent to constructing a hitting set. A set of
points H ∈ Fn is called a hitting set for a class C of n-variate polynomials if for any nonzero polynomial
P in C, there exists a point in H where P evaluates to a nonzero value.
2.2 Arithmetic branching programs
Definition 2.1 (Arithmetic Branching Program (ABP)). An ABP is a layered directed acyclic graph with
q + 1 layers of vertices {V0 ,V1 , . . . ,Vq } and a source a and a sink b such that all the edges of the graph
only go from a to V0 , Vi−1 to Vi for any i ∈ [q] and Vq to b. The edges have univariate polynomials as their
weights and as a convention, the edges going out of u and the edges going into t have constant weights,
i. e., weights from the field F. The ABP is said to compute the polynomial
f (x) = ∑ ∏ W (e) ,
p∈paths(a,b) e∈p
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 5
ROHIT G URJAR , A RPITA KORWAR , AND N ITIN S AXENA
where W (e) is the weight of the edge e.
The ABP has width-w if |Vi | ≤ w for all i ∈ [[q]]. Without loss of generality we can assume |Vi | = w
for each i ∈ [[q]].
It is well-known that the sum over all paths in a layered graph can be represented by an iterated
matrix multiplication. To see this, let the set of nodes in Vi be {vi, j | j ∈ [w]}. It is easy to see that the
polynomial computed by the ABP is the same as AT (∏qi=1 Di )B, where A, B ∈ Fw×1 and Di is a w × w
matrix for 1 ≤ i ≤ q such that
A(`) = W (a, v0,` ) for 1 ≤ ` ≤ w ,
Di (k, `) = W (vi−1,k , vi,` ) for 1 ≤ `, k ≤ w and 1 ≤ i ≤ q ,
B(k) = W (vq,k , b) for 1 ≤ k ≤ w .
2.2.1 Read-once oblivious ABP
An ABP is called a read-once oblivious ABP (ROABP) if the edge weights in different layers are univariate
polynomials in distinct variables. Formally, there is a permutation π on the set [q] such that the entries in
the ith matrix Di are univariate polynomials over the variable xπ(i) , i. e., they come from the polynomial
ring F[xπ(i) ]. Here, q is the same as n, the number of variables. The order (xπ(1) , xπ(2) , . . . , xπ(n) ) is said to
be the variable order of the ROABP.
Viewing Di (xπ(i) ) ∈ Fw×w [xπ(i) ] as a polynomial over the matrix algebra, we can write the polynomial
computed by an ROABP as
f (x) = AT D1 (xπ(1) )D2 (xπ(2) ) · · · Dn (xπ(n) )B .
An equivalent representation of a width-w ROABP can be
f (x) = D1 (xπ(1) )D2 (xπ(2) ) · · · Dn (xπ(n) ) ,
where D1 ∈ F1×w [xπ(1) ], Di ∈ Fw×w [xπ(i) ] for 2 ≤ i ≤ n − 1 and Dn ∈ Fw×1 [xπ(n) ].
2.2.2 Any-order ROABP
A polynomial f (x) is said to be computed by width-w ROABPs in any order, if for every permutation σ
of the variables, there exists a width-w ROABP in the variable order σ that computes the polynomial
f (x).
2.2.3 Set-multilinear circuits
A depth-3 set-multilinear circuit is a circuit of the form
k
f (x) = ∑ li,1 (x1 ) li,2 (x2 ) · · · li,q (xq ) ,
i=1
where li, j s are linear polynomials and x1 , x2 , . . . , xq form of a partition of the set x of variables. It is known
that these circuits are subsumed by ROABPs [14]. However, the polynomials computed by these circuits
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 6
I DENTITY T ESTING FOR R EAD -O NCE O BLIVIOUS B RANCHING P ROGRAMS
may not be computable by ROABPs in any order. For example, the 2n-variate polynomial (x1 + y1 )(x2 +
y2 ) · · · (xn + yn ) has a linear-size set-multilinear circuit. But, every ROABP in the variable sequence
(x1 , x2 , . . . , xn , y1 , y2 , . . . , yn ) that computes it has width ≥ 2n (follows from Nisan’s characterization [25]).
Note that ROABPs can compute polynomials with individual-degree ≥ 1, but set-multilinear circuits
cannot. It is not known whether all multilinear polynomials computed by ROABPs in any order can also
be computed by polynomial-size set-multilinear circuits.
A set-multilinear circuit has a corresponding polynomial over a commutative algebra. For the
polynomial f (x) above, consider the polynomial over a k-dimensional algebra
D(x) = D1 (x1 )D2 (x2 ) · · · Dq (xq ) ,
where D j = (l1, j , l2, j , . . . , lk, j ) and the algebra product is coordinate-wise product. It is easy to see that
f = (1, 1, . . . , 1) · D. Note that the polynomials Di s are over a commutative algebra, that is, the order of
the Di s in the product does not matter. Hence, some of our techniques for any-order ROABPs also work
for set-multilinear circuits.
3 Hitting set for known-order ROABP
3.1 Bivariate ROABP
To construct a hitting set for ROABPs, we start with the bivariate case. Recall that a bivariate ROABP
is of the form AT D1 (x1 )D2 (x2 )B, where A, B ∈ Fw×1 , D1 ∈ Fw×w [x1 ] and D2 ∈ Fw×w [x2 ]. It is easy to
see that a bivariate polynomial f (x1 , x2 ) computed by a width-w ROABP can be written as f (x1 , x2 ) =
∑wr=1 gr (x1 )hr (x2 ). To construct a hitting set for this polynomial, we will use the notion of a partial
derivative matrix, defined by Nisan [25] in the context of lower bounds. Let the individual degree of the
polynomial f ∈ F[x1 , x2 ] be bounded by d. The partial derivative matrix M f for f is a (d + 1) × (d + 1)
matrix with
M f (i, j) = coef f (x1i x2j ) ∈ F ,
for all i, j ∈ [[d]]. It is known that the rank of the matrix M f equals the smallest possible width of any
ROABP computing f [25].
Lemma 3.1 (rank ≤ width). For any polynomial f (x1 , x2 ) = ∑wr=1 gr (x1 )hr (x2 ), we have rank(M f ) ≤ w.
Proof. Let us define fr = gr hr , for all r ∈ [w]. Clearly, M f = ∑wr=1 M fr , as f = ∑wr=1 fr . We will show
that rank(M fr ) ≤ 1, for all r ∈ [w]. As fr = gr (x1 )hr (x2 ), its coefficients can be written as a product of
coefficients from gr and hr , i. e.,
coef fr (x1i x2j ) = coefgr (x1i ) coefhr (x2j ) .
Now, it is easy to see that
M fr = ur vT
r ,
where ur , vr ∈ Fd+1 with ur = (coefgr (x1i ))di=0 and vr = (coefhr (x2i ))di=0 .
Thus, rank(M fr ) ≤ 1 and rank(M f ) ≤ w.
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 7
ROHIT G URJAR , A RPITA KORWAR , AND N ITIN S AXENA
One can also show that if rank(M f ) = w then there exists a width-w ROABP computing f . We skip
this proof as we will not need it. Now, using the above lemma we give a hitting set for bivariate ROABPs.
Lemma 3.2. Suppose char(F) = 0, or char(F) > d. Let
w
f (x1 , x2 ) = ∑ gr (x1 )hr (x2 )
r=1
be a nonzero bivariate polynomial over F of individual degree d. Then f (t w ,t w + t w−1 ) 6= 0.
Proof. Let f˜(t) be the polynomial after the substitution, i. e., f˜(t) = f (t w ,t w + t w−1 ). Any monomial
x1i x2j will be mapped to the polynomial t wi (t w + t w−1 ) j , under the mentioned substitution. The highest
power of t coming from this polynomial is t w(i+ j) . We will cluster together all the monomials for which
this highest power is the same, i. e., i + j is the same. The set of coefficients corresponding to any such
cluster of monomials will form a diagonal in the matrix M f . The set {M f (i, j) | i + j = k} is defined to
be the k-th diagonal of M f , for all 0 ≤ k ≤ 2d. Let ` be the largest number such that the `-th diagonal has
at least one nonzero element, i. e.,
` = max{i + j | M f (i, j) 6= 0} .
As rank(M f ) ≤ w (from Lemma 3.1), we claim that the `-th diagonal has at most w nonzero elements.
To see this, let {(i1 , j1 ), (i2 , j2 ), . . . , (iw0 , jw0 )} be the set of indices where the `-th diagonal of M f has
nonzero elements, i. e., the set {(i, j) | M f (i, j) 6= 0, i + j = `}. Observe that w0 ≤ d + 1. As M f (i, j) = 0
for any i + j > `, it is easy to see that the rows {M f (i1 ), M f (i2 ), . . . , M f (iw0 )} are linearly independent.
Thus, w0 ≤ rank(M f ) ≤ w.
Now, we claim that there exists an r with w(` − 1) < r ≤ w` such that coef f˜(t r ) 6= 0. To see this, first
observe that the highest power of t to which any monomial x1i x2j with i + j < ` can contribute is t w(`−1) .
Thus, for any w(` − 1) < r ≤ w`, the term t r can come only from the monomials x1i x2j with i + j ≥ `. We
can ignore the monomials x1i x2j with i + j > ` as coef f (x1i x2j ) = M f (i, j) = 0, when i + j > `. Now, for
any i + j = `, the monomial x1i x2j maps to
j
j w`−p
t w(`− j) (t w + t w−1 ) j = t w` (1 + t −1 ) j = ∑ t .
p=0 p
Hence, for any 0 ≤ p < w,
w0
jb
coef f˜(t w`−p ) = ∑ M f (ib , jb ) .
b=1 p
Here we assume that if p > jb , then jpb = 0. Writing the above equation in the matrix form, we get,
coef f˜(t w` )
M f (i1 , j1 )
.. ..
=C ,
. .
coef f˜(t w`−w+1 ) M f (iw0 , jw0 )
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 8
I DENTITY T ESTING FOR R EAD -O NCE O BLIVIOUS B RANCHING P ROGRAMS
jb
where C is a w × w0 matrix with C(a, b) = a−1 , for all a ∈ [w] and b ∈ [w0 ]. If all the columns of C
r
are linearly independent, then clearly, coef f˜(t ) 6= 0 for some w(` − 1) < r ≤ w`. We show the linear
independence of the columns in Claim 3.3. To show this linear independence we need to assume that the
numbers { jb }b are all distinct. Hence, we need the field characteristic to be zero or strictly greater than d,
as jb can be as high as d for some b ∈ [w0 ].
jb
Claim 3.3. Let C0 be the w0 × w0 submatrix of C with C0 (a, b) = a−1 , for all a ∈ [w0 ] and b ∈ [w0 ]. Then
C0 has full rank.
0
Proof. We will show that for any nonzero vector α := (α1 , α2 , . . . , αw0 ) ∈ F1×w , αC0 6= 0. Consider the
polynomial
y y(y − 1) y(y − 1) · · · (y − w0 + 2)
h(y) = α1 + α2 + α3 + · · · + αw0 .
1! 2! (w0 − 1)!
As h(y) is a nonzero polynomial of degree bounded by w0 − 1, it can have at most w0 − 1 roots. Thus,
there exists an b ∈ [w0 ] such that
w0
jb
h( jb ) = ∑ αa 6= 0 .
a=1 a−1
This concludes the proof of Lemma 3.2.
As mentioned above, the hitting-set proof works only when the field characteristic is zero or greater
than d. We given an example over a small characteristic field, which demonstrates that the problem is
not with the proof technique, but with the hitting set itself. Let the field characteristic be 2. Consider the
polynomial f (x1 , x2 ) = x22 + x12 + x1 . Clearly, f has a width-2 ROABP. For a width-2 ROABP, the map in
Lemma 3.2 would be (x1 , x2 ) 7→ (t 2 ,t 2 + t). However, f (t 2 ,t 2 + t) = 0 (over F2 ). Hence, the hitting set
does not work.
Now, we move on to getting a hitting set for an n-variate ROABP.
3.2 n-variate ROABP
Observe that the map given in Lemma 3.2 works irrespective of the degree of the polynomial, as long
as the field characteristic is large enough. We plan to obtain a hitting set for general n-variate ROABP
by applying this map recursively. For this, we use the standard divide and conquer technique. First, we
make pairs of consecutive variables in the ROABP. For each pair (x2i−1 , x2i ), we apply the map from
Lemma 3.2, using a new variable ti . Thus, we go to n/2 variables from n variables. In Lemma 3.4, we
use a hybrid argument to show that after this substitution the polynomial remains nonzero. Moreover,
the new polynomial can be computed by a width-w ROABP. Thus, we can again use the same map on
pairs of new variables. By repeating the halving procedure log n times we get a univariate polynomial. In
each round the degree of the polynomial gets multiplied by w. Hence, after log n rounds, the degree of
the univariate polynomial is bounded by wlog n times the original degree. Without loss of generality, let us
assume that n is a power of 2.
Lemma 3.4 (Halving the number of variables). Suppose char(F) = 0, or char(F) > d. Let f (x) =
D1 (x1 )D2 (x2 ) · · · Dn (xn ) be a nonzero polynomial of individual degree d and computed by a width-w
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 9
ROHIT G URJAR , A RPITA KORWAR , AND N ITIN S AXENA
ROABP, where D1 ∈ F1×w [x1 ], Dn ∈ Fw×1 [xn ] and Di ∈ Fw×w [xi ] for all 2 ≤ i ≤ n − 1. Let the map
φ : x → F[t] be such that for any index 1 ≤ i ≤ n/2,
φ (x2i−1 ) = tiw ,
φ (x2i ) = tiw + tiw−1 .
Then f (φ (x)) 6= 0. Moreover, the polynomial f (φ (x)) ∈ F[t1 ,t2 , . . . ,tn/2 ] is computed by a width-w ROABP
in the variable order (t1 ,t2 , . . . ,tn/2 ).
Proof. Let us apply the map in n/2 rounds, i. e., define a sequence of polynomials ( f = f0 , f1 , . . . , fn/2 =
f (φ (x))) such that the polynomial fi is obtained by replacing (x2i−1 , x2i ) with (φ (x2i−1 ), φ (x2i )) in fi−1
for each 1 ≤ i ≤ n/2. We will show that for each 1 ≤ i ≤ n/2, if fi−1 6= 0 then fi 6= 0. Clearly this proves
the first part of the lemma.
Note that fi−1 is a polynomial over variables {t1 , . . . ,ti−1 , x2i−1 , . . . , xn }. As fi−1 6= 0, there exists a
constant tuple α ∈ Fn−i−1 such that after replacing the variables (t1 , . . . ,ti−1 , x2i+1 , . . . , xn ) with α, the
polynomial fi−1 remains nonzero. After this replacement we get a polynomial fˆi−1 in the variables
(x2i−1 , x2i ). As f is computed by the ROABP D1 D2 · · · Dn , the polynomial fˆi−1 can be written as
AT D2i−1 (x2i−1 )D2i (x2i )B for some A, B ∈ Fw×1 . In other words, fˆi−1 has a bivariate ROABP of width-w.
Thus, fˆi−1 (φ (x2i−1 ), φ (x2i )) is nonzero from Lemma 3.2. But, fˆi−1 (φ (x2i−1 ), φ (x2i )) is nothing but the
polynomial obtained after replacing the variables (t1 , . . . ,ti−1 , x2i+1 , . . . , xn ) in fi with α. Thus, fi is
nonzero. This finishes the proof.
Now, we argue that f (φ (x)) has a width-w ROABP. Let D̃i := D2i−1 (tiw )D2i (tiw + tiw−1 ) for all 1 ≤
i ≤ n/2. Clearly, D̃1 D̃2 · · · D̃n/2 is a width-w ROABP computing f (φ (x)) in variable order (t1 ,t2 , . . . ,tn/2 ),
as D̃1 ∈ F1×w [t1 ], D̃n/2 ∈ Fw×1 [tn/2 ] and D̃i ∈ Fw×w [ti ] for all 2 ≤ i ≤ n/2 − 1.
By applying the map φ in Lemma 3.4, we reduced an n-variate ROABP to an (n/2)-variate ROABP,
while preserving the non-zeroness. The resulting ROABP has same width-w, but the individual degree
goes up to become 2dw, where d is the original individual degree. As our map φ is degree insensitive, we
n/2
can apply a similar map again on the variables {ti }i=1 . That is, for 1 ≤ i ≤ n/4, define φ (t2i−1 ) = swi and
φ (t2i ) = swi + sw−1
i for variables {s1 , s2 , . . . , sn/4 }. Now, we get an (n/4)-variate ROABP of individual
degree 4dw2 . It is easy to see that when the map φ is repeatedly applied in this way log n times, we get a
nonzero univariate polynomial of degree ndwlog n . Next lemma puts it formally. For ease of notation, we
use the variable numbering from 0 to n − 1. Let p0 (t) = t w and p1 (t) = t w + t w−1 .
Lemma 3.5. Suppose char(F) = 0, or char(F) ≥ ndwlog n . Let f ∈ F[x] be a nonzero polynomial of
individual degree d and computed by a width-w ROABP in variable order (x0 , x1 , . . . , xn−1 ). Let the map
φ : {x0 , x1 , . . . , xn−1 } → F[t] be such that for any index 0 ≤ i ≤ n − 1,
φ (xi ) = pi1 (pi2 · · · (pilog n (t))) ,
where ilog n ilog n−1 · · · i1 is the binary representation of i.
Then f (φ (x)) is a nonzero univariate polynomial of degree ndwlog n .
Note that the map φ crucially uses the knowledge of the variable order. In the last round when we
are going from two variables to one, the individual degree is ndwlog n−1 and Lemma 3.2 requires char(F)
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 10
I DENTITY T ESTING FOR R EAD -O NCE O BLIVIOUS B RANCHING P ROGRAMS
to be higher than the individual degree. Thus, having char(F) ≥ ndwlog n suffices. Hence, we get the
following theorem.
Theorem 3.6. Let C be the class of n-variate, individual-degree-d polynomials computed by width-w
ROABPs. Then a hitting set for C of size O(ndwlog n ) can be constructed, when the variable order is
known and the field characteristic is zero or at least ndwlog n .
Proof. Let f (x) be a polynomial in class C. From Lemma 3.5, f (φ (x)) ∈ F[t] is a nonzero univariate
polynomial of degree ndwlog n . Thus, if we substitute 1 + ndwlog n field values for the variable t, one of
them will keep f (φ (x)) nonzero.
From this, we immediately get the following result for constant-width ROABPs. Note that when w is
constant, the lower bound on the characteristic also becomes poly(n).
Corollary 3.7. For the class of n-variate, individual-degree-d polynomials computed by constant width
ROABPs (known variable order), a poly(n, d)-size hitting set can be constructed, when the field charac-
teristic is zero (or larger than poly(n, d)).
As mentioned earlier, our approach can potentially lead to a polynomial-size hitting set for ROABPs.
We make the following conjecture for which we hope to get a proof on the lines of Lemma 3.2.
Conjecture 3.8. Suppose char(F) = 0. Let f (x) ∈ F[x] be an n-variate, degree-d polynomial computed
by a width-w ROABP. Then f (t r , (t + 1)r , . . . , (t + n − 1)r ) 6= 0 for some r bounded by poly(n, w, d).
4 Any-order ROABP
In this section, we give better hitting sets for the class of polynomials computed by ROABPs in any order.
Recall that a polynomial f (x) ∈ F[x] is said to be computed by width-w ROABPs in any order if for any
permutation σ : [n] → [n], f (x) can be written as
AT D1 (xσ (1) )D2 (xσ (2) ) · · · Dn (xσ (n) )B
for some Di ∈ Fw×w [xσ (i) ] for 1 ≤ i ≤ n and A, B ∈ Fw×1 .
We will also consider ROABPs which compute a polynomial over the matrix algebra, that is, polyno-
mials whose coefficients are matrices. D(x) ∈ Fw×w [x] is said to be computed by a width-w ROABP if
D(x) = D1 D2 · · · Dn for some polynomials Di ∈ Fw×w [xσ (i) ] for 1 ≤ i ≤ n.
Forbes et al. [14] gave a hitting set of size d O(log w) (nw)O(log log w) for n-variate, individual-degree-d
polynomials computed by width-w ROABPs in any order. Note that when d is small, this hitting-set size
is much better than that for ROABPs (with a particular variable order), i. e., (ndw)O(log n) [2]. However
when d is Ω(n), the size is comparable to the latter case. We improve the hitting-set size for polynomials
computed by ROABPs in any order to (ndw)O(log log w) . This is significantly better than the case of
polynomials computed by ROABPs in a particular variable order.
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 11
ROHIT G URJAR , A RPITA KORWAR , AND N ITIN S AXENA
4.1 Rank-concentration
Forbes et al. [14] constructed the hitting set using the notion of rank-concentration defined by Agrawal et
al. [3]. Recall that D(x) is a polynomial over an algebra if its coefficients come from the algebra.
Definition 4.1 ([3]). A polynomial D(x) over an algebra is said to be `-concentrated if its coefficients of
(< `)-support monomials span all its coefficients. That is, for all a ∈ {0, 1, 2, . . . }n
coefD (xa ) ∈ span{coefD (xb ) | b ∈ {0, 1, 2, . . . }n , supp(b) < `} . (4.1)
Note that for a nonzero polynomial over a field, `-concentration simply means that one of its
monomials of support < ` has a nonzero coefficient. As we will see later, it is easy to construct hitting
sets for a polynomial which has low-support concentration. However, not every polynomial has a low-
support concentration, for example, consider the following polynomial over a field: f (x) = x1 x2 . . . xn .
Agrawal et al. [3] observed that concentration can be achieved by a shift of variables, e. g., f (x + 1) =
(x1 + 1)(x2 + 1) · · · (xn + 1) has 1-concentration. For a polynomial f (x), shift by a tuple s = (s1 , s2 , . . . , sn )
would mean f (x + s) = f (x1 + s1 , x2 + s2 , . . . , xn + sn ).
To achieve concentration, it is often useful to consider shifts which are polynomials. In particular,
we will be considering shifts by bivariate polynomials, i. e., s(t1 ,t2 ) ∈ F[t1 ,t2 ]n . As ultimately we are
interested in hitting sets, the variables t1 and t2 can later be replaced by field values. The size of the hitting
set, in this case, will be multiplied by δ 2 , where δ is the maximum degree of any si (t1 ,t2 ). Thus, for a
bivariate shift s(t1 ,t2 ), its degree will be viewed as the complexity measure. Note that for a polynomial
D(x) ∈ Fw×w [x], the coefficient of a monomial xa in D(x + s(t1 ,t2 )) will be from F[t1 ,t2 ]w×w . So, when
we talk of low-support concentration in D(x + s(t1 ,t2 )), the span in (4.1) is taken over the field F(t1 ,t2 ).
Forbes et al. [14] construct the hitting set for polynomials computed by ROABPs in any order in two
steps. Let f (x) be an n-variate individual-degree-d polynomial computed by width-w ROABPs in any
order. Their first step is to construct a tuple s(t1 ,t2 ) of bivariate polynomials of degree poly(n)d O(log w)
such that f (x + s) has O(log w)-concentration. We improve this step by constructing a new tuple s(t1 ,t2 )
of degree (ndw)O(log log w) , which has the same property.
We follow the second step of Forbes et al. [14] as it is. It is easy to see that f (x + s) can also
be computed by width-w ROABPs in any order (over the field F(t1 ,t2 )). They show that if a given
polynomial, computed by ROABPs in any order, is `-concentrated then there is a hitting set for it
of size (ndw)O(log `) . This implies a hitting set H of size (ndw)O(log log w) for f (x + s). Clearly, the
set {h + s | h ∈ H} is a hitting set for f (x). One can obtain a hitting set in Fn by replacing t1 and
t2 with sufficiently many field values. By Schwartz-Zippel-DeMillo-Lipton Lemma, it will suffice
to take more than degt1 ,t2 ( f (h + s)) = deg( f ) · deg(s) values. Thus, the final hitting-set size becomes
deg(s) · (ndw)O(log log w) . With our improved bound on deg(s), we get a hitting set of the desired size.
Now, we elaborate the first step of Forbes et al. [14], i. e., the construction of the shift s(t1 ,t2 ). To
achieve concentration they use the idea of Agrawal, Saha and Saxena [3], i. e., achieving concentration in
small sub-ROABPs implies concentration in the given ROABP. For the sake of completeness, we rewrite
the lemma using the terminology of this paper. We first clarify a notation which will be used often: for an
n-tuple s and a polynomial D(x) which only depends variables (xi1 , xi2 , . . . , xi` ), the expression D(x + s)
will denote D(xi1 + si1 , xi2 + si2 , . . . , xi` + si` ).
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 12
I DENTITY T ESTING FOR R EAD -O NCE O BLIVIOUS B RANCHING P ROGRAMS
Lemma 4.2 ([3, 14]). Let ` < n be any number. Let s be the n-tuple such that for any distinct i1 , i2 , . . . , i` ∈
[n] and individual-degree-d polynomial
D(x) = D1 (xi1 )D2 (xi2 ) · · · D` (xi` )
over the matrix algebra Fw×w , D(x + s) is `-concentrated. Then for any individual-degree-d polynomial
f (x) ∈ F[x] computed by width-w ROABPs in any order, f (x + s) is `-concentrated.
Proof. Let f 0 (x) = f (x +s). Consider any monomial xa with support ≥ `. We will show that its coefficient
in f 0 (x) is in the span of smaller support coefficients in f 0 (x). Let S = {xi1 , xi2 , . . . , xi` } be a set of `
variables contained in the support of monomial xa . Let S = {xi`+1 , . . . , xin } be the rest of the variables. Let
us write xa = xb xc with Supp(b) = S and Supp(c) ⊆ S. Since, f (x) is computed by ROABPs in any order,
it has an ROABP in the variable order (xi1 , . . . , xi` , xi`+1 , . . . , xin ). That is,
f (x) = AT D1 (xi1 ) · · · D` (xi` )D`+1 (xi`+1 ) . . . Dn (xin )B
for some D j ∈ Fw×w [xi j ] for 1 ≤ j ≤ n and A, B ∈ Fw×1 . Let
D(x) := D1 (xi1 ) · · · D` (xi` ) and E(x) := D`+1 (xi`+1 ) . . . Dn (xin ) .
Let D0 (x) = D(x + s) and E 0 (x) = E(x + s). Clearly f 0 (x) = AT D0 (x)E 0 (x)B. By the lemma hypothesis,
D0 (x) is `-concentrated. That is,
0
coefD0 (xb ) ∈ span{coefD0 (xb ) | Supp(b0 ) ⊆ S, supp(b0 ) < `} . (4.2)
Note that we have Supp(b0 ) ⊆ S because each monomial in D0 (x) comes from set S. It is easy to see that
0
for any monomial xb with Supp(b0 ) ⊆ S
0 0
coef f 0 (xb xc ) = AT coefD0 (xb ) coefE 0 (xc )B .
Thus, by left multiplying AT and right multiplying coefD0 (xc )B in (4.2), we get
0
coef f 0 (xa ) ∈ span{coef f 0 (xb xc ) | Supp(b0 ) ⊆ S, supp(b0 ) < `} .
Note that supp(b0 ) + supp(c) < supp(b) + supp(c) = supp(a). So, we can write
0
coef f 0 (xa ) ∈ span{coef f 0 (xa ) | supp(a0 ) < supp(a)} .
In other words, for any monomial xa with supp(a) ≥ `, coef f 0 (xa ) is in the span of coefficients of support
smaller than supp(a). This would mean that, in fact, all coefficients of f 0 (x) are in the span of coefficients
with support < `.
Now, for some ` ≤ n, the goal is to construct an n-tuple s such that for any distinct i1 , i2 , . . . , i` ∈ n, shift-
ing by s ensures `-concentration in any `-variate ROABP of the form D(x) = D1 (xi1 )D2 (xi2 ) · · · D` (xi` ).
Note that Lemma 4.2 holds for any value of ` ≤ n. However, one cannot choose ` to be arbitrary small.
The reason is that for an `-variate polynomial over a k-dimensional algebra, one can hope to achieve
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 13
ROHIT G URJAR , A RPITA KORWAR , AND N ITIN S AXENA
`-concentration only when ` ≥ log(k + 1). To see this, consider the polynomial D(x) = ∏`i=1 (1 + vi xi )
over the algebra of k × k diagonal matrices, with k = 2` . Here, 1 stands for the matrix diag(1, 1, . . . , 1).
i−1
Define v1 = diag(α1 , α2 , . . . , αk ) for some distinct αi s. And define vi = v21 for 2 ≤ i ≤ `. It is not hard to
`
see that the 2` coefficients of the polynomial D are {1, v1 , v21 , . . . , v21 −1 }, which are linearly independent.
Note that since shifting is an invertible operation, the 2` coefficients of D(x + s) will also be linearly
independent for any s. But, there are only 2` − 1 monomials with support < `. Hence, the coefficients of
(< `)-support monomials cannot span all the coefficients in D(x + s), for any shift s.
Note that the dimension of the algebra Fw×w is bounded by w2 . To reiterate the goal, given n and
w, we fix ` = dlog(w2 + 1)e and we want to achieve `-concentration in all polynomials computed by an
ROABP of the form D1 D2 · · · D` where D j ∈ Fw×w [xi j ] for 1 ≤ j ≤ `, for some distinct i1 , i2 , . . . , i` ∈ [n].
As now we are dealing with polynomials in a small number of variables, it should be easier to achieve the
concentration.
Towards this goal, Forbes et al. [14] give a bit more general result. For any ` ≥ log(w2 + 1), they
construct a tuple s ∈ F[t1 ,t2 ]n of degree poly(n)d O(`) which has the following property: for any polynomial
D(x) ∈ Fw×w [x] which uses at most ` of the n variables and has individual-degree bound d, D(x + s) has
`-concentration. Here, Forbes et al. [14] do not need that D(x) is computed by an ROABP.
We, on the other hand, use the property that D(x) is computed by a width-w, `-variate ROABP and
reduce the degree of s(t1 ,t2 ) to (ndw)O(log `) . Our construction of s(t1 ,t2 ) comes from the basis isolating
weight assignment for ROABPs from Agrawal et al. [2]. We use the fact that for any polynomial over a
k-dimensional algebra, shift by a basis isolating map achieves log(k + 1)-concentration [17].
4.2 Basis isolation
Let us first recall the definition of a basis isolating weight assignment. Let M denote the set of all
monomials over the variable set x with individual-degree ≤ d. Any function w : x → {0, 1, 2, . . . }
can be naturally extended to the set of all monomials as follows: w(∏ni=1 xi i ) = ∑ni=1 γi w(xi ), for any
γ
(γi )ni=1 ∈ {0, 1, 2, . . . }n . Note that if the variable xi is replaced with t w(xi ) for each i, then any monomial m
just becomes t w(m) . Let Ak denote a k-dimensional algebra.
Definition 4.3 ([2]). A weight function w : x → {0, 1, 2, . . . } is called a basis isolating weight assignment
for a polynomial D(x) ∈ Ak [x], if there exists a set of monomials S ⊆ M (|S| ≤ k) whose coefficients form
a basis for the coefficient space of D(x), such that
– for any m, m0 ∈ S, w(m) 6= w(m0 ) and
– for any monomial m ∈ M \ S,
coefD (m) ∈ span{coefD (m0 ) | m0 ∈ S, w(m0 ) < w(m)} .
Gurjar et al. [17, Lemma 5.2] have shown that shifting by a basis isolating weight assignment achieves
concentration. We write their lemma here without a proof. For a weight function w : x → {0, 1, 2, . . . },
let t w denote the tuple (t w(x1 ) ,t w(x2 ) , . . . ,t w(xn ) ).
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 14
I DENTITY T ESTING FOR R EAD -O NCE O BLIVIOUS B RANCHING P ROGRAMS
Lemma 4.4 (Isolation to concentration). Let D(x) be a polynomial over a k-dimensional algebra. Let w
be a basis isolating weight assignment for D(x). Then D(x + t w ) is `-concentrated (over F(t)), where
` = dlog(k + 1)e.
We now recall the construction complexity of a basis isolating weight assignment for ROABP from [2].
Here, we present a slightly modified version of their Lemma 8 (without proof), which easily follows from
it.
Lemma 4.5. For any numbers `, n, k and d, we can construct a family W of (knd)O(log `) integer weight
assignments on variables {x1 , x2 , . . . , xn } with weights bounded by (knd)O(log `) which has the following
property: Let D(x) be an individual-degree-d polynomial over Ak of the form D1 (xi1 )D2 (xi2 ) · · · D` (xi` )
for some distinct i1 , i2 , . . . , i` ∈ [n]. Then one of the weight assignments in W is basis isolating for D(x).
Let W be the family constructed in Lemma 4.5 with k = w2 and ` = dlog(w2 + 1)e. From Lemma 4.5
and Lemma 4.4, for any D(x) = D1 (xi1 )D2 (xi2 ) · · · D` (xi` ) ∈ Fw×w [x] there exists a weight assignment
w ∈ W such that D(x + t w ) is `-concentrated (over F(t)). However, we want a single tuple s which works
for every D(x). To get a single tuple, we combine the tuples in {t w }w∈W using the standard technique of
Lagrange interpolation (also used in [14, 17]). Let {αw }w∈W be distinct constants. Define
t2 − αw0
s(t1 ,t2 ) = ∑ t1w ∏ .
w∈W α − αw0
w0 ∈W w
w0 6=w
Note that s(t1 , αw ) = t1w . The following claim shows that if D(x + t1w ) is `-concentrated for some w ∈ W,
then D(x + s(t1 ,t2 )) is also `-concentrated.
Claim 4.6. For a polynomial D(x) over an algebra and a constant αw , if D0 (x) = D(x + s(t1 , αw )) has
`-concentration (over F(t1 )) then so does D00 (x) = D(x + s(t1 ,t2 )) (over F(t1 ,t2 )).
Proof. It is easy to see that for any tuple s, coefficients of D(x + s) are linear combinations of coefficients
of D and vice versa (over an appropriate field). And since shifting is an invertible, it preserves the rank of
all coefficients. That is,
rankF {coefD (xa )}xa ∈M = rankF(t1 ) {coefD0 (xa )}xa ∈M = rankF(t1 ,t2 ) {coefD00 (xa )}xa ∈M .
Let this rank be k. Let us represent each coefficient of D as a vector in Fk . Then coefficients of D0
and D00 come from F[t1 ]k and F[t1 ,t2 ]k , respectively. Let M` = {xa ∈ M | supp(a) < `}. Since D0 has
`-concentration,
rankF(t1 ) {coefD0 (xa ) | xa ∈ M` } = k .
Hence, one can form an full rank matrix L(t1 ) ∈ F[t1 ]k×k which is given by
L(t1 ) = coefD0 (xa1 ) coefD0 (xa2 ) . . . coefD0 (xak )
for some xa1 , xa2 , . . . , xak ∈ M` . Define L0 (t1 ,t2 ) ∈ F[t1 ,t2 ]k×k to be the matrix
L0 (t1 ,t2 ) = coefD00 (xa1 ) coefD00 (xa2 ) . . . coefD00 (xak ) .
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 15
ROHIT G URJAR , A RPITA KORWAR , AND N ITIN S AXENA
From the definition of D0 and D00 , it is clear that L0 (t1 , αw ) = L(t1 ). Since det(L) 6= 0, we get that
det(L0 ) 6= 0. Thus,
rankF(t1 ,t2 ) {coefD00 (xa ) | xa ∈ M` } ≥ k .
However, k is the rank of all coefficients of D00 . Hence, D00 has `-concentration.
Now, since s(t1 ,t2 ) has the desired property from Lemma 4.2, f (x + s(t1 ,t2 )) is `-concentrated for any
polynomial f (x) computed by a width-w ROABP. Recall that degt1 (s) is bounded by (ndw)O(log log w) from
the construction in Lemma 4.5. The same bound also holds on degt2 (s) because |W| = (ndw)O(log log w) .
Lemma 4.7. Given n, d, w, one can compute a tuple s(t1 ,t2 ) ∈ F[t1 ,t2 ]n of degree (ndw)O(log log w) such
that for any n-variate, individual-degree-d polynomial f (x) ∈ F[x] computed by width-w ROABPs in any
order, f (x + s(t1 ,t2 )) is O(log w)-concentrated.
As mentioned before, O(log w)-concentration in f (x + s) means that it has an O(log w)-support
monomial with a nonzero coefficient. Lemma 4.7 gives a bivariate tuple s(t1 ,t2 ) for the shift. We argue
that one can substitute field values for t1 and t2 such that any chosen nonzero coefficient in f (x+s) remains
nonzero after the substitution. Note that any coefficient of f (x + s) is a polynomial in t1 and t2 with its
degree being at most deg( f )·deg(s), which is (ndw)O(log log w) . Thus, by Schwartz-Zippel-DeMillo-Lipton
Lemma, substituting (ndw)O(log log w) many field values for t1 and t2 suffices.
Now, we move on to the second step of Forbes, Shpilka and Saptharishi [14]. They give an
(ndw)O(log log w) -size hitting set for an already O(log w)-concentrated polynomial which is computed
by ROABPs in any order. They do this by reducing the PIT question to an O(log w)-variate ROABP [14,
Lemma 7.6].
Lemma 4.8 ([14]). Let f (x) ∈ F[x] be an n-variate, individual-degree-d polynomial computed by width-w
ROABPs in any order. Suppose f (x) has an (≤ `)-support monomial with a nonzero coefficient. Then,
there is a poly(n, w, d)-time computable m-variate map φ : x → F[y1 , y2 , . . . , ym ] such that f (φ (x)) is a
nonzero polynomial of degree < d 2 n4 , where m = O(`2 ). Moreover, f (φ (x)) is computed by width-w,
m-variate ROABPs in any order.
From the results of [15, 2], we know that an m-variate, width-w ROABP has an (mdw)O(log m) -size
hitting set. Combining Lemma 4.7 and Lemma 4.8 with this fact and putting m = O(log2 w), we get the
following.
Theorem 4.9. For the class of n-variate, individual-degree-d polynomials computed by width-w ROABPs
in any order, one can construct a hitting set of size (ndw)O(log log w) .
Concentration in Set-multilinear Circuits. Similar to Theorem 4.9, it would be interesting to achieve
the same size hitting set for set-multilinear circuits. Recall from Section 2.2.3 that a polynomial computed
by a depth-3 set-multilinear circuit can be written as (1, 1, . . . , 1) · D, where D = D1 (x1 )D2 (x2 ) · · · Dq (xq )
is a product of linear polynomials over a commutative algebra of dimension k. Here the partition
x = x1 ∪ x2 ∪ · · · ∪ xq is unknown. Note that the polynomial D can also be expressed as
D = Dσ (1) (xσ (1) )Dσ (2) (xσ (2) ) · · · Dσ (q) (xσ (q) )
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 16
I DENTITY T ESTING FOR R EAD -O NCE O BLIVIOUS B RANCHING P ROGRAMS
for any permutation σ on [q]. Hence, one can follow the same arguments as for polynomials computed by
ROABPs in any order to get concentration in set-multilinear circuits. Hence, we get the following result
analogous to Lemma 4.7.
Corollary 4.10. Given n, k, one can compute an n-tuple s(t1 ,t2 ) of degree (nk)O(log log k) such that for any
n-variate polynomial f (x) computed by a depth-3 set-multilinear circuit with top fan-in k, the polynomial
f (x + s(t1 ,t2 )) is O(log k)-concentrated.
However, it is not clear whether the second step of the hitting-set construction can be done for
set-multilinear circuits, i. e., finding a better hitting set by assuming that the polynomial is already
concentrated (Lemma 4.8).
5 Discussion
For our first result (Theorem 3.6), there are three directions for improvement. Ideally, one would like to
have all three at once.
1. Find a similar hitting set for the unknown-order case. In fact, we conjecture that the same hitting
set (Lemma 3.5) works for the unknown-order case as well.
2. Get a hitting set for all fields (including low-characteristic fields). It is easy to construct examples
over small characteristic fields where our hitting set does not work.
3. Reduce the hitting-set size to polynomial. To achieve this, it seems one has to do away with the
divide and conquer approach.
The map described in Conjecture 3.8 is a possible candidate for a polynomial-size hitting set for ROABPs
and proving this conjecture would resolve two of the points above.
As mentioned earlier, we believe the ideas here may help in finding a better PRG for ROBPs. Studying
such connections would in particular take us closer towards resolving a major open question of finding an
O(log n)-seed-length PRG for constant width ROBPs.
6 Acknowledgements
We thank the anonymous reviewer for suggesting that our techniques in Section 4 might work for a more
general class of polynomials, namely polynomials computed by ROABPs in any order. We are thankful
to Hervé Fournier, Sumanta Ghosh, Ramprasad Saptharishi for helpful discussions on the same.
References
[1] M ANINDRA AGRAWAL: Proving lower bounds via pseudo-random generators. In Proc. 25th
Internat. Conf. on Foundation of Software Tech. and Theoret. Comput. Sci. (FSTTCS’05), volume
3821 of LNCS, pp. 92–105. Springer, 2005. [doi:10.1007/11590156_6] 2
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 17
ROHIT G URJAR , A RPITA KORWAR , AND N ITIN S AXENA
[2] M ANINDRA AGRAWAL , ROHIT G URJAR , A RPITA KORWAR , AND N ITIN S AXENA: Hitting-
sets for ROABP and sum of set-multilinear circuits. SIAM J. Comput., 44(3):669–697, 2015.
[doi:10.1137/140975103, arXiv:1406.7535] 3, 4, 11, 14, 15, 16
[3] M ANINDRA AGRAWAL , C HANDAN S AHA , AND N ITIN S AXENA: Quasi-polynomial hitting-
set for set-depth-∆ formulas. In Proc. 45th STOC, pp. 321–330. ACM Press, 2013.
[doi:10.1145/2488608.2488649, arXiv:1209.2333] 4, 12, 13
[4] M ATTHEW A NDERSON , M ICHAEL A. F ORBES , R AMPRASAD S APTHARISHI , A MIR S HPILKA ,
AND B EN L EE VOLK : Identity testing and lower bounds for read-k oblivious algebraic branching
programs. In Proc. 31st IEEE Conf. on Computational Complexity (CCC’16), pp. 30:1–30:25. IEEE
Comp. Soc. Press, 2016. [doi:10.4230/LIPIcs.CCC.2016.30, arXiv:1511.07136] 3
[5] S ANJEEV A RORA AND B OAZ BARAK: Computational Complexity: A Modern Approach. Cam-
bridge Univ. Press, 1st edition, 2009. [doi:10.1017/CBO9780511804090] 3
[6] M ICHAEL B EN -O R AND R ICHARD C LEVE: Computing algebraic formulas using a constant
number of registers. SIAM J. Comput., 21(1):54–58, 1992. Preliminary version in STOC’88.
[doi:10.1137/0221006] 2
[7] S TUART J. B ERKOWITZ: On computing the determinant in small parallel time using a small number
of processors. Inform. Process. Lett., 18(3):147–150, 1984. [doi:10.1016/0020-0190(84)90018-8] 2
[8] A NDREJ B OGDANOV, Z EEV DVIR , E LAD V ERBIN , AND A MIR Y EHUDAYOFF: Pseudo-
randomness for width-2 branching programs. Theory of Computing, 9(7):283–293, 2013.
[doi:10.4086/toc.2013.v009a007] 3
[9] M ARK B RAVERMAN , A NUP R AO , R AN R AZ , AND A MIR Y EHUDAYOFF: Pseudorandom genera-
tors for regular branching programs. SIAM J. Comput., 43(3):973–986, 2014. Preliminary version
in FOCS’10. [doi:10.1137/120875673] 3
[10] J OSHUA B RODY AND E LAD V ERBIN: The coin problem and pseudorandomness for branching pro-
grams. In Proc. 51st FOCS, pp. 30–39. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.10]
3
[11] A NINDYA D E: Pseudorandomness for permutation and regular branching programs. In Proc. 26th
IEEE Conf. on Computational Complexity (CCC’11), pp. 221–231. IEEE Comp. Soc. Press, 2011.
[doi:10.1109/CCC.2011.23] 3
[12] R AFAEL M ENDES DE O LIVEIRA , A MIR S HPILKA , AND B EN L EE VOLK: Subexponential size
hitting sets for bounded depth multilinear formulas. Comput. Complexity, 25(2):455–505, 2016.
Preliminary version in CCC’15. [doi:10.1007/s00037-016-0131-1, arXiv:1411.7492] 3
[13] R ICHARD A. D EMILLO AND R ICHARD J. L IPTON: A probabilistic remark on algebraic program
testing. Inform. Process. Lett., 7(4):193 – 195, 1978. [doi:10.1016/0020-0190(78)90067-4] 2
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 18
I DENTITY T ESTING FOR R EAD -O NCE O BLIVIOUS B RANCHING P ROGRAMS
[14] M ICHAEL A. F ORBES , R AMPRASAD S APTHARISHI , AND A MIR S HPILKA: Hitting sets for
multilinear read-once algebraic branching programs, in any order. In Proc. 46th STOC, pp. 867–875.
ACM Press, 2014. [doi:10.1145/2591796.2591816] 3, 4, 6, 11, 12, 13, 14, 15, 16
[15] M ICHAEL A. F ORBES AND A MIR S HPILKA: Quasipolynomial-time identity testing of non-
commutative and read-once oblivious algebraic branching programs. In Proc. 54th FOCS, pp.
243–252. IEEE Comp. Soc. Press, 2013. [doi:10.1109/FOCS.2013.34, arXiv:1209.2408] 3, 4, 16
[16] ROHIT G URJAR , A RPITA KORWAR , AND N ITIN S AXENA: Identity testing for constant-width, and
commutative, read-once oblivious ABPs. In Proc. 31st IEEE Conf. on Computational Complexity
(CCC’16), pp. 29:1–29:16. IEEE Comp. Soc. Press, 2016. [doi:10.4230/LIPIcs.CCC.2016.29,
arXiv:1601.08031] 1
[17] ROHIT G URJAR , A RPITA KORWAR , N ITIN S AXENA , AND T HOMAS T HIERAUF: Determin-
istic identity testing for sum of read-once oblivious arithmetic branching programs. Comput.
Complexity, pp. 1–46, 2016. Preliminary version in CCC’15. [doi:10.1007/s00037-016-0141-z,
arXiv:1411.7341] 14, 15
[18] J OOS H EINTZ AND C LAUS P. S CHNORR: Testing polynomials which are easy to compute (extended
abstract). In Proc. 12th STOC, pp. 262–272. ACM Press, 1980. [doi:10.1145/800141.804674] 2
[19] RUSSELL I MPAGLIAZZO , R AGHU M EKA , AND DAVID Z UCKERMAN: Pseudorandomness from
shrinkage. In Proc. 53rd FOCS, pp. 111–119. IEEE Comp. Soc. Press, 2012. Preliminary version in
ECCC. [doi:10.1109/FOCS.2012.78] 3
[20] RUSSELL I MPAGLIAZZO , N OAM N ISAN , AND AVI W IGDERSON: Pseudorandomness for network
algorithms. In Proc. 26th STOC, pp. 356–364. ACM Press, 1994. [doi:10.1145/195058.195190] 3,
4
[21] VALENTINE K ABANETS AND RUSSELL I MPAGLIAZZO: Derandomizing polynomial identity tests
means proving circuit lower bounds. Comput. Complexity, 13(1):1–46, 2004. Preliminary version
in STOC’03. [doi:10.1007/s00037-004-0182-6] 2
[22] N EERAJ K AYAL , V INEET NAIR , AND C HANDAN S AHA: Separation between read-once oblivious
algebraic branching programs (ROABPs) and multilinear depth three circuits. In Proc. 33rd Symp.
Theoretical Aspects of Comp. Sci. (STACS’16), pp. 46:1–46:15. Schloss Dagstuhl, 2016. Preliminary
version in ECCC. [doi:10.4230/LIPIcs.STACS.2016.46] 3
[23] PASCAL KOIRAN: Arithmetic circuits: The chasm at depth four gets wider. Theoret. Comput. Sci.,
448:56–65, 2012. [doi:10.1016/j.tcs.2012.03.041, arXiv:1006.4700] 2
[24] M ICHAL KOUCKÝ , P RAJAKTA N IMBHORKAR , AND PAVEL P UDLÁK: Pseudorandom generators
for group products: extended abstract. In Proc. 43rd STOC, pp. 263–272. ACM Press, 2011.
[doi:10.1145/1993636.1993672] 3
[25] N OAM N ISAN: Lower bounds for non-commutative computation (extended abstract). In Proc. 23rd
STOC, pp. 410–418. ACM Press, 1991. [doi:10.1145/103418.103462] 3, 4, 7
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 19
ROHIT G URJAR , A RPITA KORWAR , AND N ITIN S AXENA
[26] N OAM N ISAN: Pseudorandom generators for space-bounded computation. Combinatorica,
12(4):449–461, 1992. Preliminary version in STOC’90. [doi:10.1007/BF01305237] 3
[27] R AN R AZ AND O MER R EINGOLD: On recycling the randomness of states in space bounded
computation. In Proc. 31st STOC, pp. 159–168. ACM Press, 1999. [doi:10.1145/301250.301294] 3
[28] R AN R AZ AND A MIR S HPILKA: Deterministic polynomial identity testing in non-commutative mod-
els. Comput. Complexity, 14(1):1–19, 2005. Preliminary version in CCC’04. [doi:10.1007/s00037-
005-0188-8] 3
[29] JACOB T. S CHWARTZ: Fast probabilistic algorithms for verification of polynomial identities. J.
ACM, 27(4):701–717, 1980. Preliminary version in EUROSAM’79. [doi:10.1145/322217.322225]
2
[30] T HOMAS S TEINKE: Pseudorandomness for permutation branching programs without the group
theory. Electron. Colloq. on Comput. Complexity (ECCC), 19(83), 2012. Available at ECCC. 3
[31] L ESLIE G. VALIANT: Completeness classes in algebra. In Proc. 11th STOC, pp. 249–261. ACM
Press, 1979. [doi:10.1145/800135.804419] 2
[32] L ESLIE G. VALIANT, S VEN S KYUM , S TUART J. B ERKOWITZ , AND C HARLES R ACKOFF: Fast
parallel computation of polynomials using few processors. SIAM J. Comput., 12(4):641–644, 1983.
Preliminary version in MFCS’81. [doi:10.1137/0212043] 2
[33] R ICHARD Z IPPEL: Probabilistic algorithms for sparse polynomials. In Proc. Internat. Symp.
Symbolic and Algebraic Comput. (EUROSAM’79), pp. 216–226. Springer, 1979. [doi:10.1007/3-
540-09519-5_73] 2
AUTHORS
Rohit Gurjar
Postdoctoral fellow
Tel Aviv University
Tel Aviv, Israel
rohitgurjar0 gmail com
http://www.cse.iitk.ac.in/users/rgurjar
Arpita Korwar
Ph. D. student
Indian Institute of Technology Kanpur
Kanpur, India
arpk cse iitk ac in
http://www.cse.iitk.ac.in/users/arpk
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 20
I DENTITY T ESTING FOR R EAD -O NCE O BLIVIOUS B RANCHING P ROGRAMS
Nitin Saxena
Associate professor
Indian Institute of Technology Kanpur
Kanpur, India
nitin cse iitk ac in
http://www.cse.iitk.ac.in/users/nitin
ABOUT THE AUTHORS
ROHIT G URJAR is currently a postdoctoral fellow at Tel Aviv University, working with
Amir Shpilka. His previous postdoc was at Aalen University (2015-16) with Thomas
Thierauf. Before that he was at Indian Institute of Technology Kanpur for 10 long years
for his B. Tech.-M. Tech. (2005-10) and Ph. D. (2010-15). He was very fortunate to
have Manindra Agrawal and Nitin Saxena as his Ph. D. supervisors. His Ph. D. thesis
was chosen for the ACM India Doctoral Dissertation Award, 2017. He is in general
interested in theoretical computer science, and in particular in computational complexity
and derandomization. Some problems on which he has worked are polynomial identity
testing, perfect matching, and matrix completion. He likes hiking, cycling and listening
to music.
A RPITA KORWAR is a Ph. D. student at IIT Kanpur advised by Manindra Agrawal and Nitin
Saxena. Her work has also been influenced by Somenath Biswas. Her interests are in
the theoretical aspects of computer science, especially in using algebraic techniques for
computational complexity. Currently she is working on polynomial identity testing and
arithmetic lower bounds with Hervé Fournier and Guillaume Malod at the University of
Paris Diderot. She visited Thomas Thierauf at the University of Ulm a couple of times
during her Ph. D. studies. She likes the outdoors and sports!
N ITIN S AXENA received his Ph. D. from the Indian Institute of Technology Kanpur in 2006.
He was truly fortunate to have Manindra Agrawal for his supervisor. He also spent
stints at Princeton University (2003-04) and at the National University of Singapore
(2004-05). He was a postdoc at the Centrum voor Wiskunde en Informatica Amsterdam
(2006-08) and a faculty at the Hausdorff Center for Mathematics Bonn (2008-13). Nitin’s
long-term interests are in algebra-flavored computational complexity problems. He has
contributed to primality testing, polynomial identity testing, polynomial independence,
polynomial factoring and polynomial equivalence problems. Some of these works have
been awarded the Gödel prize, Fulkerson prize, CCC best paper (2006), and ICALP
best paper (2011) awards. He enjoys interacting with enthusiastic young researchers.
In his spare (& non-spare) time he enjoys listening to music, watching movies, reading
non-fiction, swimming and traveling.
T HEORY OF C OMPUTING, Volume 13 (2), 2017, pp. 1–21 21