Authors Amir Shpilka, Ilya Volkovich,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514
www.theoryofcomputing.org
On Reconstruction and Testing of
Read-Once Formulas
Amir Shpilka∗ Ilya Volkovich∗
Received June 18, 2012; Revised July 18, 2014; Published December 26, 2014
Abstract: An arithmetic read-once formula (ROF for short) is a formula (a circuit whose
underlying graph is a tree) in which the operations are {+, ×} and each input variable labels
at most one leaf. A preprocessed ROF (PROF for short) is a ROF in which we are allowed
to replace each variable xi with a univariate polynomial Ti (xi ). We obtain a deterministic
non-adaptive reconstruction algorithm for PROFs, that is, an algorithm that, given black-box
access to a PROF, constructs a PROF computing the same polynomial. The running time
of the algorithm is (nd)O(log n) for PROFs of individual degrees at most d. To the best of
our knowledge our results give the first subexponential-time deterministic reconstruction
algorithms for ROFs.
Another question that we study is the following generalization of the polynomial identity
testing (PIT) problem. Given an arithmetic circuit computing a polynomial P(x̄), decide
whether there is a PROF computing P(x̄), and find one if one exists. We call this question
the read-once testing problem (ROT for short). Previous (randomized) algorithms for
reconstruction of ROFs imply that there exists a randomized algorithm for the ROT problem.
An extended abstract appeared in the Proceedings of the 40th Annual Symposium on Theory of Computing (STOC 2008),
pages 507-516 [40].
∗ Research supported by the Israel Science Foundation (grant number 339/10) and the European Community’s Seventh
Framework Programme (FP7/2007-2013) under grant agreement number 257575.
ACM Classification: F.2.2
AMS Classification: 68Q25
Key words and phrases: read-once formulas, identity testing, reconstruction, arithmetic circuits,
bounded-depth circuits
© 2014 Amir Shpilka and Ilya Volkovich
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2014.v010a018
A MIR S HPILKA AND I LYA VOLKOVICH
In this work we show that most previous PIT algorithms be strengthened to yield algorithms
for the ROT problem. In particular we give ROT algorithms for the following circuit classes:
depth-2 circuits (circuits computing sparse polynomials), depth-3 circuits with bounded top
fan-in, and sum of k ROFs. The running time of the ROT algorithm is essentially the same
as the running time of the corresponding PIT algorithm for the class.
The main tool in most of our results is a new connection between PIT and reconstruction
of ROFs. Namely, we show that in any model that satisfies some “nice” closure properties
(for example, a partial derivative of a polynomial computed by a circuit in the model, can
also be computed by a circuit in the model) and that has an efficient deterministic polynomial
identity testing algorithm, we can also answer the read-once testing problem.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 466
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
Contents
1 Introduction 469
1.1 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
1.1.1 Reconstruction of preprocessed read-once formulas . . . . . . . . . . . . . . . . 470
1.1.2 Read-once testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
1.3 Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
1.4 Subsequent work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
1.5 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
2 Preliminaries 475
2.1 Partial derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
2.2 Commutator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
2.3 Polynomials and circuit classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
3 Our model 479
3.1 ROFs and ROPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
3.2 The gate-graph of ROFs and ROPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
3.3 Factors of ROPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
3.4 Commutators of ROPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
3.5 PROPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
4 Auxiliary algorithms 488
4.1 From PIT to justifying assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
4.2 ROF graph-related algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
4.2.1 Factoring a ROF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
4.2.2 Counting the number of monomials in a PROP . . . . . . . . . . . . . . . . . . 490
5 Reconstruction of a PROF 491
5.1 Reconstruction of a 0̄-justified PROF . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
5.1.1 Learning the preprocessing and var0 (P) . . . . . . . . . . . . . . . . . . . . . . 492
5.1.2 Constructing the gate-graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493
5.1.3 Top gate “+” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
5.1.4 Top gate “×” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
5.1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
5.2 Reconstruction of a general PROF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
5.2.1 Randomized PROF reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . 498
5.2.2 Deterministic PROF reconstruction . . . . . . . . . . . . . . . . . . . . . . . . 499
5.2.3 Non-adaptive PROF reconstruction . . . . . . . . . . . . . . . . . . . . . . . . 499
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 467
A MIR S HPILKA AND I LYA VOLKOVICH
6 Read-once testing 500
6.1 Generic scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
6.2 Read-once verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
6.3 Proof of Theorem 1.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504
7 ROT for specific models 504
7.1 Sparse polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
7.2 Depth-3 circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
7.3 Multilinear depth-4 circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
7.4 Multilinear read-k formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
8 Acknowledgments 507
A Proof of Lemma 3.10 507
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 468
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
1 Introduction
Let F be a field and C a class of arithmetic circuits. The reconstruction problem for the class C is defined
as follows. Given black-box (i. e., oracle) access to a polynomial P ∈ F[x1 , x2 , . . . , xn ], computable by an
arithmetic circuit from the class C, construct a circuit C ∈ C that computes P. A reconstruction algorithm
is efficient if the number of queries it makes to the polynomial and its running time are polynomial
in the size of the representation of P in the class C. The reconstruction problem can be considered
as the algebraic analog of the learning problem. A special case of the problem is the interpolation
problem, where the goal is to find the monomial representation of the circuit. This can be seen to be the
reconstruction problem when C is the class of depth-2 circuits (see, e. g., [29]).
The reconstruction problem is tightly connected to the Polynomial Identity Testing (PIT for short)
problem, in which we need to determine whether a given arithmetic circuit C(x̄) computes the zero1
polynomial. There are two common models for studying the PIT problem. In the white-box model
the algorithm is given access to the circuit itself. In particular, the algorithm can take into account the
underlying graph of the circuit, etc. In the black-box model, the algorithm is not given access to the
circuit and instead it can only query the value of the circuit on different inputs. Thus, a deterministic
black-box PIT algorithm for a circuit class C has to compute a hitting-set for that class, that is, a set of
points H such that if a circuit from C evaluates to zero over H then it must compute the zero polynomial.
Note that if F is a small field, e. g., F = F2 , then a hitting set does not necessarily exist. Indeed, over F2
we have that x2 = x, but they are not equal as polynomials. Thus, to construct a hitting set we may need
to use inputs from a polynomially large extension field. One of the main properties of a hitting set H is
that the values of any circuit from C on H describe the polynomial computed by that circuit uniquely, in
the sense that two circuits that agree on H must compute the same polynomial since their difference2
evaluates to zero over H. Yet, such a set does not provide us with an efficient algorithm for reconstructing
circuits from C. On the other hand, it is easy to see that a deterministic reconstruction algorithm can be
used as a black-box PIT algorithm. For more information on the reconstruction problem and on PIT we
refer the reader to the survey [44].
Several works have shown that efficient deterministic PIT algorithms imply lower bounds for arith-
metic circuits [19, 21, 1]. Thus, the deterministic reconstruction problem is at least as hard as proving
circuit lower bounds. In view of the difficulty of the problem for general arithmetic circuits, research
focused on restricted models such as: sparse polynomials [29], depth-3 circuits with bounded top fan-
in [39, 24], non-commutative formulas [6, 28] and multilinear depth-4 circuits with top fan-in 2 [17].
The motivation to study restricted models is two fold. One reason is that many restricted models are
interesting by themselves. Another reason is that we hope to gain insight from restricted models for the
general problem.
The focus of this paper is on models related to arithmetic read-once formulas. An arithmetic read-once
formula (ROF for short) is a formula (a circuit in which the fan-out of every gate is at most 1) in which
the operations are {+, ×} and such that every input variable labels at most one leaf. A preprocessed
ROF (PROF for short) is a ROF in which we are allowed to replace each variable xi with a univariate
1 As usual in this case, we ask whether C(x̄) is the identically zero polynomial and not the zero function over F.
2 In fact, this statement requires an additional assumption that given C ,C in C the circuit C −C is in the class as well. But
1 2 1 2
this assumption holds true for most natural classes.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 469
A MIR S HPILKA AND I LYA VOLKOVICH
polynomial Ti (xi ). Although read-once formulas form a very restricted model of computation, they
received a lot of attention in both the Boolean and the algebraic models. Over the Boolean domain,
[22, 4, 11] gave efficient learning algorithms for several classes of Boolean read-once formulas. In the
algebraic model, [18, 10, 8, 9] gave efficient randomized reconstruction algorithms for ROFs. However,
prior to this work, no deterministic sub-exponential time reconstruction algorithm for ROFs was known.
This state of affairs implies that if we want to give efficient deterministic algorithms for bounded-depth
multilinear circuits or for multilinear formulas then we should first try to find such algorithms for ROFs.
In view of this, we focus in this work on ROFs and, as a result, give the first deterministic sub-exponential
time reconstruction algorithm for PROFs.
1.1 Our results
Our results require that the underlying field is of polynomial size. In case that |F| is too small we
make queries to a polynomial-sized extension field. This is common to many (all) PIT algorithms, see
discussions in [29, 44]. The running time of our algorithms is polynomial in log |F| when F is finite, and
is polynomial in the bit-size of the field elements appearing in the formula, for general fields. We now
state our results formally.
1.1.1 Reconstruction of preprocessed read-once formulas
Theorem 1.1. There is a deterministic (nd)O(log n) time algorithm that given black-box access to a PROF
Φ, on n variables and individual degrees (of the preprocessing) at most d, over a field F, reconstructs Φ,
i. e., it constructs a PROF that computes the same polynomial. If |F| ≤ n2 d then the algorithm may make
queries from an extension field of F of size larger than n2 d.
Moreover, there is an algorithm that performs this task in a non-adaptive manner, that is, when each
query to the black-box is independent of the results of the previous ones, with roughly the same running
time.
Theorem 1.2. There is a deterministic (nd)O(log n) time algorithm that given black-box access to a PROF
Φ, on n variables and individual degrees (of the preprocessing) at most d, over a field F, reconstructs
Φ. Moreover, the algorithm queries Φ on a fixed set of points of size (nd)O(log n) . If |F| ≤ n3 d then the
algorithm may make queries from an extension field of F of size larger than n3 d.
We also re-establish the result of [10] that gives a randomized polynomial-time reconstruction
algorithm for ROFs. In fact, we show that a similar approach will work for PROFs as well.
Theorem 1.3. There is a polynomial-time randomized algorithm that given black-box access to a PROF
Φ, on n variable and individual degrees (of the preprocessing) at most d, reconstructs Φ with high
probability. If |F| ≤ 4n2 d then the algorithm may make queries from an extension field of F of size larger
than 4n2 d.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 470
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
1.1.2 Read-once testing
In addition to reconstruction of preprocessed read-once formulas we are also interested in a generalization
of the problem that we call the read-once testing problem (ROT for short).3
Problem 1.4 (ROT). Given a circuit C (maybe as a black-box) computing some polynomial P(x̄), decide
whether P can be computed by a PROF, and if the answer is positive then compute a PROF for it.
Similarly to the PIT problem, there is an efficient randomized algorithm for the ROT problem. Indeed,
by the results of [10] (or Theorem 1.3), there is a randomized algorithm for reconstructing a given
black-box ROF. Thus, given access to the circuit C we can run the reconstruction algorithm to get a
candidate PROF and then, invoking the Schwartz-Zippel randomized identity testing algorithm [46, 38],
we can check whether the ROF that we computed earlier, computes the same polynomial as the one in the
black-box. This results in a two-sided error algorithm. A simpler, one-sided error algorithm follows for
the recent result of [45], which provides a characterization of polynomials computed by ROFs.
The main question is then whether we can find an efficient deterministic algorithm for the ROT
problem. Clearly, this is a generalization of the PIT problem, as the zero polynomial is computable by
a ROF. We show that if we are given an efficient deterministic PIT algorithm for a circuit class C, that
satisfies some “nice” closure properties, then we can also solve the ROT problem for that class efficiently.
Moreover, the reduction works both in the black-box and in the white-box models, depending on the PIT
algorithm at hand.
An argument similar to the above one shows that an efficient randomized reconstruction algorithm
for a circuit class C implies an efficient randomized algorithm for the corresponding “C-testing” problem
(i. e., checking whether a given arithmetic circuit can be implemented within the class C). Yet, no such
connection is known in the deterministic setting. For example deterministic “sparsity-testing” (i. e.,
determining whether a given circuit C computes a sparse polynomial) is a long standing open question
posed by von zur Gathen (see, e. g., [15]).
Our main result for ROT is given in the following theorem.
Theorem 1.5. Let C be a class of arithmetic circuits. Denote by L(C) the class of all circuits of the form
α ·C + β for α, β ∈ F and C ∈ C (see Definition 2.18). Denote with CV the class of circuits that contains
all circuits of the form
C1 +C2 +C3 ×C4
where the Ci ’s are circuits from L(C) and C2 , C3 and C4 are pairwise variable disjoint. Suppose that there
is a deterministic PIT algorithm A that runs in time T (n, d, s), when given access (white-box or black-box)
to a circuit in n-variables, of size s and degree d, that belongs to CV . Then, there is a deterministic
algorithm B, that uses A as a subroutine, such that when given access (white-box or black-box) to an
n-variate circuit of size s and degree d from C, solves the ROT problem in time poly(n, d, s, T (n, d, s)). If
|F| ≤ nd then the algorithm may make queries from an extension field of size > nd. Similarly, if the given
PIT algorithm puts an additional requirement on the size of the field (a lower bound) then we allow our
algorithm to make queries from an appropriate extension field of F.
3 It may be more accurate to denote this problem as preprocessed read-once testing and reconstructing, but for brevity we
use read-once testing.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 471
A MIR S HPILKA AND I LYA VOLKOVICH
Note that C1 may share variables with C2 ,C3 and C4 . The requirement that we have a PIT for the
class CV may seem odd at first, but it is explained by the way our algorithm works: it first constructs a
?
candidate ROF and then makes several tests of the form C1 = C2 +C3 ×C4 , thinking of C2 ,C3 and C4 as
“disjoint parts” of a ROF C1 , which is a restriction of the ROF that we constructed at the first step. For
more details see the discussion in Section 6.2.
We note that for most of the circuit classes C for which we have efficient deterministic PIT algorithms,
we also have such algorithms for their “closure,” CV . As a corollary we get that all previous PIT algorithms
can be generalized to yield algorithms for ROT. We demonstrate this point in the next theorem.
Theorem 1.6. Let F be a multilinear read-k formula (i. e., a multilinear formula in which each variable
appears at most k times) over F[x1 , x2 , . . . , xn ]. Then:
• There is a deterministic algorithm that given white-box access to F solves the ROT problem for F
O(k)
in time nk .
• There is a deterministic algorithm that given black-box access to F solves the ROT problem for F
O(k)
in time nk +O(k log n) .
If |F| ≤ n2 then the algorithm may make queries from an extension field of F of size larger than n2 .
This result generalizes both the black-box and the white-box PIT algorithms for multilinear read-k
formulas of [3].
Our next result strengthens many reconstruction algorithms that were obtained for the model of sparse
polynomials ([7, 16, 29] to name just a few). The result uses the black-box PIT algorithm for sparse
polynomials of [29], yet any of the above algorithms can be used instead. As was communicated to us by
Lisa Hellerstein [20], for the case where P is a multilinear polynomial a similar result was proved in [30].
Theorem 1.7. There is a deterministic polynomial time algorithm that given black-box access to an n-
variate polynomial P, of degree d with m monomials (i. e., a polynomial computed by a depth-2 arithmetic
circuit with m multiplication gates), solves the ROT problem for P. The running time of the algorithm is a
polynomial in n, m and d. If |F| ≤ (nd)6 then the algorithm may make queries from an extension field of
F of size larger than (nd)6 .
Our next result solves the ROT problem for depth-3 and depth-4 circuits, with bounded top fan-in
(see formal definition in Sections 7.2 and 7.3). It generalizes the results of [12, 27, 26, 25, 33, 36] and
others, who gave deterministic PIT algorithms for these models. The theorem uses the black-box PIT
algorithm for ΣΠΣ(k) circuits of [36].
Theorem 1.8. There is a deterministic algorithm that given black-box access to a depth-3 circuit C, of
top fan-in k (i. e., a ΣΠΣ(k) circuit), solves the ROT problem for the polynomial computed by the circuit.
The running time of the algorithm is poly(n) · d O(k ) , where n is the number of variables and d is the
2
degree of the circuit. If |F| ≤ dnk2 then the algorithm may make queries from an extension field of F of
size larger than dnk2 .
Our next result uses the black-box PIT algorithm for multilinear ΣΠΣΠ(k) circuits of [33] and obtains
ROT algorithms for this class.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 472
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
Theorem 1.9. There is a deterministic algorithm that given black-box access to a multilinear depth-4
circuit C, of top fan-in k (i. e., a ΣΠΣΠ(k) circuit), solves the ROT problem. The running time of the
algorithm is (ns)O(k ) , where n is the number of variables and s is the size of the circuit. If |F| ≤ n2 then
6
the algorithm may make queries from an extension field of F of size larger than n2 .
We can also extend our results to hold for non-commutative formulas, for which [32] gave a polyno-
mial time white-box PIT algorithm and [14, 13] gave quasi-polynomial time black-box PIT algorithms.
However, extending our results to the non-commutative case requires redoing many steps of the algorithm,
without introducing any new ideas, and so we omit the proof. We nevertheless write some algorithms in a
way that allows one to apply them in non-commutative models as well (by making sure we do not change
the order of left and right children of a multiplication gate, etc.).
1.2 Related work
Read-once arithmetic formulas were studied before in the context of learning theory and exact learning
algorithms were devised for them. We shall now discuss the different models in which it was studied and
highlight the differences from our work.
In [18] algorithms for learning ROFs, that use membership and equivalence queries, were given. A
membership query to a ROF Φ(x̄) is simply a query that asks for the value of Φ(x̄) on a specific input.
An equivalence query on the other hand, gives the oracle4 a certain hypothesis, h(x̄), and the oracle either
answers “equal” if Φ ≡ h or returns an input ᾱ such that Φ(ᾱ) 6= h(ᾱ). In this language, our results use
only membership queries.
In [10] a different approach was taken. They considered randomized learning algorithms that only use
membership queries. It is not difficult to see that using randomness one does not need to use equivalence
queries. The learning algorithm of [10] can reconstruct, with high probability, ROFs that also use division
gates (and not just +, × gates). They also considered a model in which justifying assignments (a notion
that we later define and use) are given in advance to the algorithm. This result was later generalized in [8]
who gave a randomized reconstruction algorithm for ROFs that use addition, multiplication, division and
exponentiation gates.
In this work we give deterministic reconstruction algorithms, introduce the ROT problem, show
the relation between PIT and ROT and, as a result, obtain several deterministic ROT algorithms. Our
reconstruction algorithms diverge from previous work in that our algorithms are deterministic, we do
not need to use randomness at all.5 We also study the more general problem of ROT. To the best of our
knowledge, this is the first time that ROT is studied. The main difference between the reconstruction
problem and the ROT problem is that in the reconstruction setting we are guaranteed that there exists a
PROF for the given circuit, whereas in the ROT problem we first have to check whether the polynomial
can be computed by a PROF and only then we can try and find such a formula. The first step is the main
difficulty in designing ROT algorithms.
Finally, we discuss the relation to our previous papers [40, 41]. The core ideas behind this work
appeared as an extended abstract in [40]. There, the ROT problem was formally introduced and shown to
4 In the learning theory literature, the word oracle is used to describe the function in the black-box and so we use this
terminology here too.
5 Equivalence queries can be viewed as randomized queries, as they allow one to solve PIT efficiently.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 473
A MIR S HPILKA AND I LYA VOLKOVICH
be computationally equivalent to the PIT problem. That is, it was shown that a circuit class C, satisfying
some closure properties, has an efficient deterministic ROT algorithm if and only if it has an efficient
deterministic PIT algorithm. That paper also gave the first deterministic sub-exponential time PIT
algorithm for sum of ROFs. Later, in [41], a more efficient deterministic PIT algorithm for sum of ROFs
was obtained. That work also extended our previous results to PROFs. In conclusion, the basic ideas
behind our reconstruction and ROT algorithms come from the paper [40], and the improved PIT algorithm
of [41] is only used to improve the running time of the algorithms (in the black-box model).
In this paper we only consider reconstruction and testing of PROFs. We defer our results concerning
PIT algorithms to another paper ([43]6 ) to make this work more focused.
1.3 Techniques
To explain our approach we first need the notion of the gate-graph of a ROF. This is a graph on the set
of variables, in which two variables are connected if and only if their first common ancestor gate is a
multiplication gate (see Definition 3.3).
Our reconstruction algorithms use, at a high level, the gate-by-gate reconstruction technique of [18,
10]. The idea is to first first learn the gate-graph of the ROF. Once we have the gate-graph, we can learn
the top gate of the formula by, roughly, checking whether the graph is connected or disconnected. We can
thus reconstruct the tree of the formula recursively. In the process we also learn the “fine details,” namely,
we reconstruct the constants in the circuit. For reconstructing PROFs, we first learn the underlying
preprocessing and then proceed with the reconstruction algorithm for the underlying ROF.
Compared to the techniques of [18, 10] our algorithm does not require the ability to compute square
roots of field elements, which is assumed to be the case in [10]. The algorithm of [10] used randomness
to gain access to so called justifying assignments. Instead, we use PIT algorithms for ROF in order to
deterministically compute justifying assignments. Furthermore, we introduce some new ingredients that
allow us to extend the algorithm to the case of PROFs.
The second part of the paper is devoted to the ROT problem with the main idea being “Doveryai, no
Proveryai.”7 Given (white-box or black-box) access to an input circuit C, we first apply our reconstruction
algorithm and construct a PROF Φ, that supposedly computes the same polynomial as C. Recall that
our reconstruction algorithm works in the black-box model so we can pretend that C is a PROF and run
the algorithm on C. If the algorithm fails then we know that the polynomial computed by C cannot be
computed by a PROF. However, if the reconstruction does not fail then we are not done yet. At this
point we have a PROF Φ and we have to test whether C ≡ Φ. We do so by going over Φ gate-by-gate,
mimicking the reconstruction algorithm. Since we know Φ, we can set variables to constants and obtain
access to sub-formulas of Φ. Making appropriate queries to the circuit C, we can compare the restricted
Φ and the restricted C. We can thus check if “locally” C and Φ agree. It is at this point that we need
access to a PIT algorithm for circuits of the form C1 +C2 +C3 ×C4 as in Theorem 1.5. A more detailed
explanation of the verification procedure is given in Section 6.2.
6 This is the full version of the paper [41].
7 “Trust, but Verify”—a translation of a Russian proverb which became a signature phrase of Ronald Reagan during the cold
war.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 474
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
1.4 Subsequent work
Recently, in [45] a simple characterization of polynomials computable by ROFs was given. Those
polynomials are refereed to as read-once polynomials (ROP for short), see Definition 3.1. Roughly
speaking, it is shown that a polynomial P is a ROP if and only if all its restrictions to three variables
are ROPs. In other words, a polynomial P can be computed by a ROF if and only if it can be “locally”
computed by ROFs. This result is obtained by borrowing and extending several techniques from the
current paper.
1.5 Organization
The paper is organized as follows. In Sections 2 and 3 we give the basic definitions and notation. In
Section 4 we give some basic algorithms for ROFs. Then, in Section 5 we prove Theorems 1.1, 1.2
and 1.3. Next, in Section 6 we show how to convert efficient deterministic PIT algorithms to efficient
deterministic ROT algorithms and prove Theorem 1.5. We conclude the paper (Section 7) by showing
some corollaries of Theorem 1.5, thus proving Theorems 1.6, 1.7, 1.8 and 1.9.
2 Preliminaries
For a positive integer n we denote [n] = {1, . . . , n}. Given a graph G = (V, E) we denote with Gc the
complement graph.
For a polynomial P(x1 , . . . , xn ), a variable xi and a field element α we denote with P|xi =α the
n
polynomial resulting from setting xi = α. We say that P depends on xi if there exist assignments ā, b̄ ∈ F ,
which differ only on the i-th coordinate, such that P(ā) 6= P(b̄). We denote
var(P) , {xi | P depends on xi } .
Given a subset I ⊆ [n] we say that P is defined on I if var(P) ⊆ I. Intuitively, P depends on xi if xi
“appears” when P is listed as a sum of monomials. On the other hand, a constant function P ≡ c is defined
on every subset of [n].
Definition 2.1. Given a subset I ⊆ [n] and an assignment ā ∈ Fn we define P|xI =āI to be the polynomial
resulting from substituting ai to xi , for every i ∈ I. In particular P|xI =āI is defined on [n] \ I.
Observation 2.2. Let J ⊆ I ⊆ var(P) be subsets of var(P). Then for every assignment ā ∈ Fn it must be
the case that var(P|xI =āI ) ⊆ var(P|xJ =āJ ) ⊆ var(P) \ J.
Note that by substituting a value to a variable of P we, obviously, eliminate the dependence of P on
that variable. This, however, may also eliminate the dependence of P on other variables and thus lose
more information than intended. When we wish to reconstruct a formula, we cannot allow losing any
information as it would affect our final answer. We now define a “lossless” type of an assignment. Similar
definitions were given in [18] and [10], but we repeat the definitions here to ease the reading of the paper
(we also slightly change some of the definitions).
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 475
A MIR S HPILKA AND I LYA VOLKOVICH
Definition 2.3 (Justifying assignment). We say that an assignment ā ∈ Fn is a justifying assignment for a
polynomial P if for every subset I ⊆ var(P) we have that
var(P|xI =āI ) = var(P) \ I . (2.1)
We say that a polynomial P is ā-justified if ā is a justifying assignment for P. A set J ⊆ Fn is called a
justifying set for a circuit class C, if it contains a justifying assignment for every polynomial P computed
by a circuit from C.
The next proposition shows that in order to verify whether P is ā-justified it is enough to consider
only subsets I of size |var(P)| − 1, rather than all subsets of var(P).
Proposition 2.4. An assignment ā ∈ Fn is a justifying assignment for P if and only if equation (2.1) holds
for every subset I of size |var(P)| − 1.
Proof. Let J ⊆ var(P). If J = var(P) then, obviously, var(P|xJ =āJ ) = 0/ = var(P) \ J. Otherwise, let
x ∈ var(P) \ J. Consider the set I = var(P) \ {x}. From the definition: |I| = |var(P)| − 1 and J ⊆ I, and
thus (2.1) holds for I. Combining with Observation 2.2 we obtain that
{x} = var(P) \ I = var(P|xI =āI ) ⊆ var(P|xJ =āJ ) ⊆ var(P) \ J .
Hence, x ∈ var(P|xJ =āJ ). As this holds for every x ∈ var(P) \ J, it follows that var(P) \ J ⊆ var(P|xJ =āJ ),
and hence the two sets are equal. The second direction of the claim is trivial.
For convenience we will concentrate on 0̄-justified polynomials. The following lemma shows that, in
a sense, we can do so w. l. o. g.
Lemma 2.5. Let ā ∈ Fn and let P(x̄) be an ā-justified polynomial. Then
P(x̄ + ā) , P(x1 + a1 , x2 + a2 , . . . , xn + an )
is a 0̄-justified polynomial. In addition, P(x̄ + ā) ≡ 0 if and only if P(x̄) ≡ 0.
Definition 2.6 (0̄-justified closure). We denote
n o
var0 (P) , xi P|x[n]\{i} = 0̄[n]\{i} depends on xi .
That is, var0 (P) is the maximal set of variables such that P is 0̄-justified with respect to this set.
Clearly, var0 (P) ⊆ var(P) and equality holds iff P is 0̄-justified.
Lemma 2.7. A polynomial P is 0̄-justified iff var(P) = var0 (P).
The Hamming weight of a vector ā ∈ Fn is defined as: wt(ā) , |{i | ai 6= 0 }|. That is, the number of
non-zero coordinates.
Definition 2.8. For a set 0 ∈ W ⊆ F and k ≤ t we define Atk (W ) to be the set of all vectors in W t with
Hamming weight at most k.
An immediate conclusion from the definition is that for a finite set W (that contains 0), it holds that
k
t
Ak (W ) = ∑
t
· (|W | − 1) j = (t · (|W | − 1))O(k) .
j=0 j
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 476
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
2.1 Partial derivatives
The concept of a partial derivative of a multivariate function and its properties (for example, P depends
on xi if and only if ∂∂ xPi 6≡ 0) are well-known and well-studied for continuous domains (such as, R, C
etc.). This concept can be extended to polynomials over arbitrary fields, by defining the discrete partial
derivative. Discrete partial derivatives play an important role in the analysis of our algorithms.
Definition 2.9. Let P ∈ F[x1 , x2 , . . . , xn ] be a polynomial. We define the discrete partial derivative of P,
with respect to xi , as
∂P
, P|xi =1 − P|xi =0 .
∂ xi
Notice that if P is a multilinear polynomial then this definition coincides with the formal definition
for polynomials. The following lemma is easy to verify.
Lemma 2.10. The following properties hold for a multilinear polynomial P:
∂P
• P depends on xi if and only if 6≡ 0.
∂ xi
∂P ∂ 2P
• does not depend on xi (in particular ≡ 0).
∂ xi ∂ xi2
∂ 2P ∂ 2P
∂ ∂P
• = = .
∂ xi ∂ x j ∂ xi ∂ x j ∂ x j ∂ xi
∂P ∂
• ∀i 6= j, |x =a = (P|x j =a ).
∂ xi j ∂ xi
∂P
• ā ∈ Fn is a justifying assignment for P if and only if for every i ∈ var(P) it holds that (ā) 6≡ 0.
∂ xi
Since the above properties trivially hold, we shall use them implicitly throughout the paper. We note
that these basic properties do not hold for non-multilinear polynomials. For example, when P(x) = x2 − x
we get that ∂∂ Px ≡ 0. Thus, to handle general polynomial we need the following extension.
Definition 2.11. Let P ∈ F[x1 , x2 , . . . , xn ] be a polynomial. The directed partial derivative of P, with
respect to xi and direction α ∈ F, is defined as
∂P
, P|xi =α − P|xi =0 .
∂α xi
Definition 2.12. For a non-empty subset I ⊆ [n], I = i1 , . . . , i|I| , we define the iterated partial derivative
with respect to I in the following way:
∂ |I| P
∂I P , .
∂ xi1 ∂ xi2 ∂ xi3 · · · ∂ xi|I|
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 477
A MIR S HPILKA AND I LYA VOLKOVICH
2.2 Commutator
We now formally introduce one of our main reconstruction tools. Previously it was defined and used
in [42] for the purpose of polynomial factorization. Here we define a simpler, “multilinear” version of
the commutator since we are only going to apply it to multilinear polynomials. It is not hard to see that
both our definition and the commutator of [42] have the same properties when restricted to multilinear
polynomials.
Definition 2.13. Let P ∈ F[x1 , x2 , . . . , xn ] be a polynomial and let i, j ∈ [n]. We define the commutator
between xi and x j as
∆i j P , P|xi =1,x j =1 · P|xi =0,x j =0 − P|xi =1,x j =0 · P|xi =0,x j =1 .
Definition 2.14. Let P ∈ F[x1 , x2 , . . . , xn ] be a polynomial, c ∈ F, and i 6= j ∈ [n]. We say that P is (xi , x j )-
separated mod c if P can be written as P = h·g+c, where xi ∈ var(h)\var(g) and x j ∈ var(g)\var(h). We
say that P is (xi , x j )-separated mod F if there exists a field element c ∈ F such that P is (xi , x j )-separated
mod c.
We next show that the commutator actually tells us whether a polynomial is separated or not.
Lemma 2.15 (Lemma 4.6 of [42]). Let P ∈ F[x1 , x2 , . . . , xn ] be a multilinear polynomial and let xi 6= x j ∈
var(P). Then P is (xi , x j )-separated mod 0 if and only if ∆i j P ≡ 0.
The next observation follows from the definition of the commutator.
Observation 2.16. Let P, R ∈ F[x1 , x2 , . . . , xn ] be multilinear polynomials with xi , x j 6∈ var(R). Then
∂ 2P
∆i j (P + R) = ∆i j P + R · .
∂ xi ∂ x j
The following is an immediate corollary of Lemma 2.15 and Observation 2.16, which extends
Lemma 2.15.
Corollary 2.17. Let P ∈ F[x1 , x2 , . . . , xn ] be a multilinear polynomial and let xi 6= x j ∈ var(P). Let c ∈ F
be a field element. Then P is (xi , x j )-separated mod c if and only if
∂ 2P
∆i j P = c · .
∂ xi ∂ x j
2.3 Polynomials and circuit classes
We shall associate with a circuit class C the set of polynomials that can be computed by circuits from C.
The following notation will be useful for us.
Definition 2.18.
1. We say that the circuit class C contains the polynomial P if P can be computed by some circuit C
from C. We denote it by P ∈ C.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 478
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
2. We say that the circuit class C1 contains the circuit class C2 if it contains all its polynomials (i. e.,
P ∈ C1 =⇒ P ∈ C2 ). We denote it by C1 ⊆ C2 .
3. For a circuit class C we define the (discrete) directed partial derivatives of C as:
∂P
∂C , P ∈ C, i ∈ [n], α ∈ F .
∂α xi
4. We say that a circuit class C is closed under partial derivatives if ∂ C ⊆ C.
5. The linear closure of a circuit class C is L(C) , {α · P + β | P ∈ C and α, β ∈ F }.
3 Our model
In this section we discuss our computational model. We first consider the basic model of ROFs and cover
some of its main properties. Then, we introduce the model of PROFs and give the corresponding basic
properties.
3.1 ROFs and ROPs
Most of the definitions that we give in this section, or small variants of them, are from [18]. We start by
formally defining the notions of a ROF and a ROP.
Definition 3.1. An arithmetic read-once formula (ROF for short) Φ, in the variables x̄ = (x1 , . . . , xn ), over
a field F, is a binary tree whose leafs are labelled with the input variables and whose internal nodes are
labelled with the arithmetic operations {+, ×} and with a pair of field elements8 (α, β ) ∈ F2 . Each input
variable can label at most one leaf. The computation is performed in the following way. A leaf labelled
with the variable xi and with (α, β ) computes the polynomial α · xi + β . If a node v is labelled with the
operation op ∈ {+, ×} and with (α, β ), and its children compute the polynomials Φv1 and Φv2 then the
polynomial computed at v is Φv = α · (Φv1 op Φv2 ) + β . We say that a ROF Φ is non-degenerate if the
polynomial that it computes depends on all the variables appearing in it Φ. For the sake of completeness,
we denote the non-degenerate ROF computing the constant field element β by the special CONST gate
CN β .
A polynomial P(x̄) is a read-once polynomial (ROP for short) if it can be computed by a ROF. Clearly,
ROPs are a subclass of multilinear polynomials.
3.2 The gate-graph of ROFs and ROPs
In this section we define the important notion of gate-graph of a ROF and a ROP. A similar notion was
defined in [18], but here we define it in a slightly more general form.
Given a graph of computation of a ROF it is natural to define the first common gate of a subset of
gates. A similar notion was presented in [10].
8 This is a slightly more general model than the usual definition of read-once formulas.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 479
A MIR S HPILKA AND I LYA VOLKOVICH
Definition 3.2. Let V ⊆ var(Φ), |V | ≥ 2, be a subset of the input variables of a ROF Φ. We define the
first common gate of V , fcg(V ), to be the first gate in the graph of computation of Φ common to all the
paths from the inputs of V to the root of the formula.
We note that fcg(V ) is in fact the least common ancestor of the nodes in V when viewing the formula
as a tree. We now define, for every ROF, several new graphs that are related to it. The notion of a t-graph
of a ROF (where t is a type of a gate) was introduced and studied in [18] for various types of gates (such
as threshold gates, modular gate, division gates etc.). We shall focus on + and × gates as these are the
only gates appearing in our ROFs. We now give a definition of a t-graph that is slightly different from the
one in [18].
Definition 3.3 (t-graph). Let Φ be a ROF in the input variables var(Φ). Let t ∈ {+, ×} be a possible
label of an internal node. The t-graph of the formula Φ, denoted GtΦ , is an undirected graph whose
vertex set is var(Φ) and whose edges are defined as follows: (i, j) is an edge if and only if the arithmetic
operation that labels the gate fcg(xi , x j ) is t.
The following simple lemma (whose basic form can be found in [18]) gives some basic properties of
t-graphs. We omit the proof as it is implicit in the proof of Lemma 3 in [18].
Lemma 3.4. The following properties are satisfied by t-graphs.
1. Let P be a ROP and let Φ and Ψ be two non-degenerate ROFs computing P. Then G× ×
Φ = GΨ and
+ + × × + +
GΦ = GΨ . In particular, the graphs GP , GΦ and GP , GΦ are well defined. Consequently, the
t-graph of a ROP is a well defined notion.
+ c
2. For every ROP P we have G×
P = GP . That is, the addition and the multiplication graphs of each
ROP P are simply complements to each other.
3. For every ROP P exactly one of G× +
P and GP is connected. More precisely, the type of the top gate
t
of P is t if and only if GP is connected.
We define the gate-graph of a ROF Φ as GΦ , G×
Φ . Similarly, we define GP to be the gate-graph of a
ROP P.
Lemma 3.5. Let P be a ROP. Then (i, j) is an edge in the gate-graph GP if and only if xi · x j appears in
some monomial of P. Moreover, if I is a clique in GP then there is some monomial in P containing ∏ xi .
i∈I
Proof. The first part is immediate from the definition. The second part is easily proved by induction on
|I|.
The following is an algebraic version of the above lemma. It also provides a more algebraic definition
of the gate-graph of a ROP P. The proof is similar to the proof of Lemma 3.5.
Lemma 3.6. Let P(x1 , . . . , xn ) be a ROP. Then (i, j) is an edge in the gate-graph GP if and only if
∂ 2P
6≡ 0 .
∂ xi ∂ x j
Moreover, for I ⊆ [n] we have that ∂I P 6≡ 0 if and only if I is a clique in GP .
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 480
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
Next, we give two examples of family of multilinear polynomials that are not ROPs.
Example 3.7. For n ≥ 4, the polynomial P(x1 , x2 , . . . , xn ) = x1 x2 + x2 x3 + · · · + xn−1 xn is not a ROP.
Indeed, form Lemmas 3.4 and 3.5 we get that both the +-graph and the ×-graph are connected for this
polynomial. From Lemma 3.4 we get that P is not a ROP.
Example 3.8. For every n ≥ 3, the polynomial
P(x1 , x2 , . . . , xn ) = ∑ xi x j
i6= j∈[n]
is not a ROP. Indeed, notice that GP is complete graph (a clique) while ∂[n] P ≡ 0. Lemma 3.6 implies
that P is not a ROP.
The following lemma is also an easy corollary of Lemma 3.4.
Lemma 3.9 (ROP Structural Lemma). Every ROP P(x̄) with |var(P)| ≥ 2 can be presented in exactly
one of the following two forms:
1. P(x̄) = P1 (x̄) + P2 (x̄) and
2. P(x̄) = P1 (x̄) · P2 (x̄) + c,
where P1 and P2 are non-constant variable disjoint ROPs and c is a constant.
We end this section by providing two more useful properties related to partial derivatives of ROPs.
Lemma 3.10. A partial derivative of a ROP is a ROP. Moreover, a partial derivative of a 0̄-justified
ROP is also a 0̄-justified ROP.
The proof is very similar to the proof of Lemma 5.12 in [43]. For completeness we give it in
Appendix A.
Lemma 3.11. Let P be a 0̄-justified ROP. Then
∂ 2P ∂ 2P
6≡ 0 if and only if (0̄) 6= 0 .
∂ xi ∂ x j ∂ xi ∂ x j
Proof. By Lemma 3.10, ∂∂ xPi is a 0̄-justified ROP. Consequently, by the definition,
∂ ∂P ∂ ∂P
6≡ 0 if and only if (0̄) 6= 0 .
∂xj ∂ xi ∂xj ∂ xi
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 481
A MIR S HPILKA AND I LYA VOLKOVICH
3.3 Factors of ROPs
In this section we study properties of factors of ROPs. We start by proving that every factor of a ROP
is also a ROP. Although this is an easy claim to prove, our proof has the advantage that it can be used
to devise a linear-time factorization algorithm for ROFs in the white-box model (see Algorithm 1 in
Section 4.2.1).
Lemma 3.12. Every factor of a ROP is a ROP.
Proof. Let P(x̄) = h1 (x̄) · h2 (x̄) be a reducible ROP, where h1 and h2 are (not necessarily irreducible)
non-constant factors. In particular, |var(P)| ≥ 2. According to Lemma 3.9 P has exactly one of the
following two forms:
1. P(x̄) = P1 (x̄) + P2 (x̄). Notice that h1 and h2 are variable disjoint. Consequently, we can assume
w. l. o. g. that there exist xi , x j such that xi ∈ var(h1 ) ∩ var(P1 ) and x j ∈ var(h2 ) ∩ var(P2 ). Otherwise
2
all the variables of P will be in the same factor. Now, by considering ∂ ∂xi ∂Px j we obtain on the one
hand
∂ 2P ∂2
= (P1 + P2 ) ≡ 0
∂ xi ∂ x j ∂ xi ∂ x j
since P1 and P2 are variable-disjoint. On the other hand
∂ 2P ∂ h1 ∂ h2
= · .
∂ xi ∂ x j ∂ xi ∂ x j
As ∂∂hx1i and ∂∂ hx2j are non-zero, we get a contradiction.
2. P(x̄) = P1 (x̄) · P2 (x̄) + c. As previously, we can assume w. l. o. g. that there exist xi , x j such that
xi ∈ var(h1 ) ∩ var(P1 ) and x j ∈ var(h2 ) ∩ var(P2 ). This time we consider ∆i j P. On the one hand
∆i j P = ∆i j (h1 · h2 ) ≡ 0. On the other hand, by Observation 2.16,
∂ P1 ∂ P2
∆i j P = c · · .
∂ xi ∂ x j
This implies that c = 0. It follows that P1 and P2 are factors of P and that P1 and P2 are ROPs. A
simple induction completes the proof.
As a corollary of the proof we deduce the following observation.
Observation 3.13. Let P(x̄) = P1 (x̄) · P2 (x̄) + c , P(x̄) = P10 (x̄) · P20 (x̄) + c0 be two representations of a
ROP P. Then c = c0 . In other words, the constant c is unique.
3.4 Commutators of ROPs
In general, a commutator ∆i j P of a polynomial P may be a more complicated polynomial than the original
P. In this section we show that a commutator of a ROP has a nice structure. For our future purposes we
consider the commutator between two variables xi , x j for which
∂ 2P
6≡ 0 .
∂ xi ∂ x j
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 482
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
Lemma 3.14. Let P(x̄) ∈ F[x1 , x2 , . . . , xn ] be a ROP and let i 6= j ∈ var(P) be such that
∂ 2P
6≡ 0 .
∂ xi ∂ x j
Then there exist variable disjoint ROPs H(x̄) and R(x̄, y) such that:
1. P(x̄) = R(x̄, H(x̄)),
∂ 2P
2. ∆i j P = R(x̄, 0) · ,
∂ xi ∂ x j
3. H is (xi , x j )-separated mod 0.
Proof. Let Φ be a ROF for P and let v = fcg(xi , x j ) in Φ. Take R0 (x̄, y) to be the ROP computed by Φ
when we replace the subtree rooted at v with a new variable y, and let H 0 be the ROP computed by Φv .
We can write P(x̄) = R0 (x̄, H 0 (x̄)). As v is a multiplication gate (by Lemma 3.6), Lemma 3.9 implies that
H 0 is of the form H 0 (x̄) = h1 (x̄) · h2 (x̄) + c for c ∈ F, where xi ∈ var(h1 ) and x j ∈ var(h2 ). Define
H(x̄) , H 0 (x̄) − c and R(x̄, y) , R0 (x̄, y + c) .
Observe that P(x̄) = R0 (x̄, H 0 (x̄)) = R(x̄, H(x̄)) and that H is (xi , x j )-separated mod 0. This proves items
1 and 3 of the claim. For the remaining item, observe that we can write R(x̄, y) = Ry (x̄) · y + R0 (x̄), where
∂R
Ry = and R0 = R|y=0 .
∂y
By Observation 2.16 and the chain rule:
∂ 2 (Ry · H) ∂ 2H ∂ 2P
∆i j (P) = ∆i j (Ry · H + R0 ) = R0 · = R0 · Ry · = R(x̄, 0) · ,
∂ xi ∂ x j ∂ xi ∂ x j ∂ xi ∂ x j
as claimed.
Unlike the partial derivative operator (see Lemma 3.10) the commutator does not preserve the property
of being a 0̄-justified ROP. We show, however, that to some extent, the assignment 0̄ remains interesting
when considering commutators of 0̄-justified ROPs. Specifically, it acts nicely on the ROP R(x̄, y) that
was constructed in Lemma 3.14.
Lemma 3.15. Let R(x̄, y) ∈ F[x1 , x2 , . . . , xn , y] be a ROP with |var(R)| = n + 1 such that:
∂R
1. there exists ` ∈ [n] such that (x̄, 0) 6≡ 0, and
∂ x`
∂R
2. for each i ∈ [n] we have that (0̄, y) 6≡ 0.
∂ xi
∂R
Then there exists k ∈ [n] such that (0̄, 0) 6= 0.
∂ xk
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 483
A MIR S HPILKA AND I LYA VOLKOVICH
Proof. By induction on n. Let n = 1. Clearly, k = 1. Since R is a multilinear polynomial we get that in
this case
∂R ∂R
(0, 0) = (x1 , 0) 6= 0 .
∂ x1 ∂ x1
Now suppose that n ≥ 2. By Lemma 3.9, R can be presented in one of the following forms:
Case 1: R(x̄, y) = R1 (x̄, y) + R2 (x̄). Pick xk ∈ var(R2 ). As y 6∈ var(R2 ). We have that:
∂R ∂ R2 ∂ R2
(0̄, 0) = (0̄, 0) = (0̄, y) 6= 0 .
∂ xk ∂ xk ∂ xk
Case 2: R(x̄) = R1 (x̄, y) · R2 (x̄) + c, where c ∈ F. We have two subcases to consider.
Case 2a: There exists x j ∈ var(R1 ) such that ∂∂Rx 1j (x̄, 0) 6≡ 0. In particular, |var(R1 ) \ {y}| ≥ 1. For
each xi ∈ var(R1 ) we have that:
∂ R1 ∂R ∂ R1
(0̄, y) · R2 (0̄) = (0̄, y) 6≡ 0 =⇒ (0̄, y) 6≡ 0 , R2 (0̄) 6= 0 .
∂ xi ∂ xi ∂ xi
Consequently, we can apply the induction hypothesis to R1 and get that there exists xk ∈
var(R1 ) such that
∂ R1
(0̄, 0) 6= 0 .
∂ xk
To finish the proof of this case, observe that
∂R ∂ R1
(0̄, 0) = (0̄, 0) · R2 (0̄) 6= 0 .
∂ xk ∂ xk
Case 2b: For each x j ∈ var(R1 ) we have that
∂ R1
(x̄, 0) ≡ 0 .
∂xj
This implies that R1 (x̄, 0) ≡ b for some b ∈ F. In particular, x` ∈ var(R2 ). Consequently,
∂ R2 ∂ R2 ∂R
b· (x̄) = R1 (x̄, 0) · (x̄) = (x̄, 0) 6≡ 0 =⇒ b 6= 0 ,
∂ x` ∂ x` ∂ x`
and
∂ R2 ∂R ∂ R2
R1 (0̄, y) · (0̄) = (0̄, y) 6≡ 0 =⇒ (0̄) 6= 0 .
∂ x` ∂ x` ∂ x`
Hence,
∂R ∂ R2 ∂ R2
(0̄, 0) = R1 (0̄, 0) · (0̄) = b · (0̄) 6= 0 .
∂ x` ∂ x` ∂ x`
Taking k = ` completes the proof.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 484
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
We can now show that in a 0̄-justified ROP the 0̄ assignment can, in some sense, preserve the
separation property.
with |var(P)| ≥ 3 and xi 6= x j ∈ var(P). Then,
Lemma 3.16. Let P ∈ F[x1 , x2 , . . . , xn ] be a 0̄-justified ROP
P is (xi , x j )-separated mod F iff for every k ∈ var(P) \ xi , x j it holds that
P|x[n]\{i, j,k} =0̄[n]\{i, j,k}
is (xi , x j )-separated mod F.
Proof. We begin by noting that since
var P|x[n]\{i, j,k} =0̄[n]\{i, j,k} = xi , x j , xk ,
the first direction of the claim immediately follows. For the other direction, observe that
∂ 2P
6≡ 0 .
∂ xi ∂ x j
Therefore, we can apply Lemma 3.14 to obtain ROPs H(x̄) and R(x̄, y) such that
∂ 2P
P(x̄) = R(x̄, H(x̄)) and ∆i j P = R(x̄, 0) · .
∂ xi ∂ x j
Now, assume for a contradiction that P is not (xi , x j )-separated mod F. We would like to apply Lemma 3.15
to reach a contradiction. We first show that R(x̄, y) satisfies the condition of that lemma.
Note that R(x̄, 0) must be a non-constant polynomial. Indeed, if it was constant then we would get
that
∂ 2P ∂ 2P
∆i j P = R(x̄, 0) · = c· ,
∂ xi ∂ x j ∂ xi ∂ x j
in contradiction to Corollary 2.17. Thus, there exists x` ∈ var(R) such that
∂R
(x̄, 0) 6≡ 0 .
∂ x`
Let xm ∈ var(R). As P is 0̄-justified, we have that
∂R ∂P
(0̄, H(0̄)) = (0̄) 6= 0 ,
∂ xm ∂ xm
hence
∂R
(0̄, y) 6≡ 0 .
∂ xm
We have thus shown that R satisfies the conditions of Lemma 3.15. Consequently, there exists xk such that
∂R
(0̄, 0) 6= 0 .
∂ xk
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 485
A MIR S HPILKA AND I LYA VOLKOVICH
To simplify notation, assume without loss of generality that k = 1, i. e., assume that
∂R
(0̄, 0) 6= 0 .
∂ x1
By Corollary 2.17 there must exist c ∈ F such that
∂ 2P
∆i j P|x[n]\{1,i, j} =0̄[n]\{1,i, j} = c · (x1 , 0̄) .
∂ xi ∂ x j
On the other hand,
∂ 2P
∆i j P|x[n]\{1,i, j} =0̄[n]\{1,i, j} = R(x1 , 0̄, 0) · (x1 , 0̄) .
∂ xi ∂ x j
As
∂ 2P
(x1 , 0̄) 6≡ 0
∂ xi ∂ x j
(by Lemma 3.11) it must be the case that R(x1 , 0̄, 0) ≡ c in contradiction to
∂R
(0̄, 0) 6= 0 .
∂ x1
Therefore, P must be (xi , x j )-separated mod F.
3.5 PROPs
In this subsection we extend the model of ROFs by allowing a preprocessing step of the input variables.
While the basic model is read-once in its variables, the extended model can be considered to be read-once
in univariate polynomials.
Definition 3.17. A preprocessing is a transformation T (x̄) : Fn → Fn of the form
T (x̄) , (T1 (x1 ), T2 (x2 ), . . . , Tn (xn ))
such that each Ti is a non-constant univariate polynomial. We say that a preprocessing is standard if in
addition each Ti is monic and satisfies Ti (0) = 0.
Notice that preprocessing does not affect the PIT problem in the white-box model as for every
n-variate polynomial P(ȳ) it holds that P(ȳ) ≡ 0 if and only if P(T (x̄)) ≡ 0. We now give a formal
definition and list some simple properties of PROFs.
Definition 3.18. A preprocessed arithmetic read-once formula (PROF for short), in the variables
x̄ = (x1 , . . . , xn ), over a field F, is a binary tree whose leafs are labelled with non-constant univari-
ate polynomials T1 (x1 ), T2 (x2 ), . . . , Tn (xn ) (all together forming a preprocessing) and whose internal
nodes are labelled with the arithmetic operations {+, ×} and with a pair of field elements (α, β ) ∈ F2 .
Each Ti can label at most one leaf. The computation is performed in the following way. A leaf labelled
with the polynomial Ti (xi ) and with (α, β ) computes the polynomial α · Ti (xi ) + β . If a node v is labelled
with the operation op ∈ {+, ×} and with (α, β ), and its children compute the polynomials Φv1 and Φv2 ,
then the polynomial computed at v is Φv = α · (Φv1 op Φv2 ) + β .
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 486
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
A polynomial P(x̄) is a Preprocessed Read-Once Polynomial (PROP for short) if it can be computed
by a PROF. A decomposition of a polynomial P is a pair (Q(z̄), T (x̄)) such that P(x̄) = Q(T (x̄)), where
Q is a ROP and T is a preprocessing. We call Q the backbone of P. We let the gate-graph of P, GP , be the
gate-graph of its backbone Q. A standard decomposition is as above with the additional requirement that
T is a standard preprocessing. An immediate consequence of the definition is that each PROP admits a
decomposition. To provide additional intuition we start with a simple, yet important, lemma.
Lemma 3.19. Every PROP P admits a standard decomposition. In addition, if (Q(z̄), T (x̄)) and
(Q0 (z̄), T 0 (x̄)) are two decompositions of a PROP P(x̄), then there exist two vectors ā, b̄ ∈ Fn , with
ai 6= 0 for every i ∈ [n], such that
Q(z̄) = Q0 (a1 · z1 + b1 , . . . , an · zn + bn ) ,
T 0 (x̄) = (a1 · T1 (x1 ) + b1 , . . . , an · T2 (x2 ) + bn ) .
Moreover, if (Q, T ) is a decomposition of a PROP P, then any pair (Q0 , T 0 ) that satisfies the above
conditions is also a decomposition of P.
Proof. Let (Q, T ) be some decomposition of P and let ci 6= 0 denote the leading coefficient of xi in the
polynomial Ti (xi ) for i ∈ [n] (ci is well-defined since Ti is non-constant). Consider the shifted polynomials:
Q̃(z̄) , Q (c1 · z1 + T1 (0), c2 · z2 + T2 (0), . . . , cn · zn + Tn (0)) ,
Ti (xi ) − Ti (0)
T̃i (xi ) , , and
ci
T̃ (x̄) , T̃1 (x1 ), T̃2 (x2 ), . . . , T̃n (xn ) .
It is easy to verify that (Q̃, T̃ ) is a standard decomposition of P. Given the above argument, the proofs of
the second and the third properties follow easily and so we omit them.
To handle the preprocessed case we will need the following definitions:
Definition 3.20. Let P(x̄) = Q(T (x̄)) ∈ F[x1 , x2 , . . . , xn ] be a PROP in its standard decomposition. We
say that ᾱ ∈ Fn is a witness for P if for every i ∈ [n] it holds that Ti (αi ) 6= 0.
Definition 3.21. Let P ∈ F[x1 , x2 , . . . , xn ] be a polynomial, ᾱ ∈ Fn and i, j ∈ [n]. We define the α-directed
commutator between xi and x j as
∆ᾱi j P , P|xi =αi ,x j =α j · P|xi =0,x j =0 − P|xi =αi ,x j =0 · P|xi =0,x j =α j .
The next two lemmas follow easily from the definition and from following the proof for the case of
ROFs and so we omit their proofs.
Lemma 3.22. Let P, (Q(z̄), T (x̄)) be a PROP and its standard decomposition, respectively. Then the
following properties hold for any ᾱ ∈ F[x1 , x2 , . . . , xn ].
∂P ∂Q ∂ Ti ∂Q
• = · = · Ti (αi ).
∂αi xi ∂ zi z̄=T (x̄) ∂αi xi ∂ zi z̄=T (x̄)
∂Q ∂P
In particular Ti (αi ) · (z̄), T (x̄) is a standard decomposition of .
∂ zi ∂α xi
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 487
A MIR S HPILKA AND I LYA VOLKOVICH
• P is 0̄-justified if and only if Q is 0̄-justified. More generally, P is ā-justified if and only if Q is
T (ā)-justified.
• ∆ᾱi j P = ∆i j Q|z̄=T (x̄) · Ti (αi ) · T j (α j ).
∂P ∂Q
• If ᾱ is a witness for P then ≡ 0 ⇐⇒ ≡ 0, and ∆ᾱi j P ≡ 0 ⇐⇒ ∆i j Q ≡ 0.
∂αi xi ∂ zi
The following is the PROP version of Lemma 3.9.
Lemma 3.23 (PROP Structural Lemma). Every PROP P(x̄) such that |var(P)| ≥ 2 can be presented in
exactly one of the following forms:
1. P(x̄) = P1 (x̄) + P2 (x̄), and
2. P(x̄) = P1 (x̄) · P2 (x̄) + c,
where P1 , P2 are non-constant, variable-disjoint PROPs and c is a constant.
4 Auxiliary algorithms
In this section we give some auxiliary algorithms to be used later.
4.1 From PIT to justifying assignments
We now show how to compute a justifying assignment from a PIT algorithm, following Section 4 in [43].
We shall consider a circuit class C (e. g., depth-3 circuits, ROFs, etc.) for which there exists another circuit
class C0 such that ∂ C ⊆ C0 (recall Definition 2.18) and C0 has an efficient deterministic PIT algorithm.9
Lemma 4.1 (Lemma 4.1 [43]). Let n, d ≥ 1. Assume |F| > nd. Let P ∈ F[x1 , x2 , . . . , xn ] be a polynomial,
with individual degrees bounded by d, that is computed by circuits from C. Let C0 be another (or the
same) circuit class such that ∂ C ⊆ C0 . Suppose C0 admits a deterministic PIT algorithm A. Then there
exists a deterministic algorithm B that has black-box access to A and computes a justifying assignment ā
for P in time O(n3 d · t), where t is the running time of A.
Lemma 4.1 gives an (adaptive) algorithm that computes a justifying assignment for any polynomial
in C, given access to a PIT algorithm for the class C0 . In order to obtain a non-adaptive reconstruction
algorithm we will need a non-adaptive version of the lemma. More precisely, we require an algorithm
that computes a justifying set for PROPs, i. e., a set that contains a justifying assignment for every PROP
(recall Definition 2.3). In Section 4.1 of [43] it was also shown how to convert a black-box PIT algorithm
into a justifying set of roughly the same size. In addition, [43] presented a black-box PIT algorithm for
PROPs (see Lemma 5.12). Combining these results we get the following lemma:
Lemma 4.2. Let n, d ≥ 1. Assume |F| > n3 d. Then there exists a deterministic algorithm that, given n
and d, runs in time (nd)O(log n) and computes a set, Jd , of size |Jd | = (nd)O(log n) , which is a justifying set
for PROPs, of individual degrees at most d, in F[x1 , x2 , . . . , xn ].
9 Note that in most cases an identity testing algorithm for C can be slightly modified to yield an identity testing algorithm for
∂ C.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 488
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
4.2 ROF graph-related algorithms
In this section we give two basic algorithms for PROFs in the white-box model. To slightly simplify the
algorithms we shall assume w. l. o. g. that all the PROFs are non-degenerate. Notice that we can make
this assumption since there is a trivial O(n) time white-box algorithm that can convert any ROF Φ to a
non-degenerate ROF Φ0 such that Φ ≡ Φ0 .
For the analysis of the algorithms we will need the following easy observations. The first is that
a non-degenerate ROF Φ computes the zero polynomial if and only if Φ is the “zero ROF,” Φ = CN 0
(the graph of computation of Φ is no other than CN 0 ). Secondly, in a non-degenerate ROF, for every
gate-label (α, β ), it holds that α 6= 0.
We will use the following notation in our algorithms.
Definition 4.3. Let G be the graph of computation of a PROF. We think of G as a planar graph (and in
particular the notions “left child” and “right child” of a node are well defined). Let v be a gate in the
formula.
• Φv - denotes the formula rooted at v.
• v.var - denotes var(Φv ). Note that v.var can be computed recursively.
• v.α - denotes the value of α labeling v.
• v.β - denotes the value of β labeling v.
• v.Left - denotes the left child of v.
• v.Right - denotes the right child of v.
• v.Type - denotes the type of the arithmetic operation labeling v. (IN - Input, CONST - Constant
Function gate (i. e., CN α ), × - Multiplication, + - Addition)
4.2.1 Factoring a ROF
We now give an algorithm for finding all the irreducible factors of a given ROF. The idea of the algorithm
comes from the proof of Lemma 3.12. There we showed that a ROF Φ has non trivial factors if and
only if its top gate is a multiplication gate and the additive constant β , of the top gate, is 0. Note that in
this case Φ equals the product of the polynomials computed by its children. From this it is clear that by
looking at the top gate and recursing on the left and right children we can find all the irreducible factors.
Algorithm 1 computes a list S = {hi } of all irreducible factors of Φv (the polynomial computed by the
node v) and a constant α such that
Φv = α · ∏ hi .
i
The following lemma gives the analysis of the algorithm. We omit the proof as it is immediate from
the proof of Lemma 3.12.
Lemma 4.4. Given a node v in the graph of computation of a non-constant ROF Φ, Algorithm 1 computes
a pair (S, α), where S consists of ROFs for the irreducible factors of Φv and α is a constant satisfying
Φv = α · ∏h∈S h. The running time of the algorithm is O(n).
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 489
A MIR S HPILKA AND I LYA VOLKOVICH
Algorithm 1 FactorROF(Φ)
Input: Non-constant ROF Φ.
Output: (S, α) where S is a list of the irreducible factors of Φ,
α a constant in the field.
1: if v.Type = IN then {Univariate polynomial}
2: return (Φ , 1)
3: if v.Type = + then
4: return (Φ , 1)
5: if v.β 6= 0 then
6: return (Φ , 1)
{Now v.Type = × and β = 0, thus Φ = α · Φv.Right × Φv.Left }
7: (SL , αL ) ← FactorROF(Φv.Left )
8: (SR , αR ) ← FactorROF(Φv.Right )
9: return (union(SL , SR ) , αL · v.α · αR )
4.2.2 Counting the number of monomials in a PROP
The number of monomials in a polynomial P is the number of monomials with non-zero coefficients.
We now give an efficient deterministic algorithm for counting the number of monomials computed by a
given PROF. The main idea is that once a non-constant monomial appears, it cannot be canceled later.
Consequently, we only have to sum the number of non-constant monomials and keep track of the behavior
of the constant term.
In order to determine whether a certain value is zero or not we use an auxiliary function NZ(x) that is
defined as (
0 x = 0,
NZ(x) =
1 otherwise.
The algorithm simply recurses on the left child and on the right child of the root and combines the results
according to the different values of the constant terms.
Lemma 4.5. Given a node v in the graph of computation of a PROF Φ, with individual degrees at most
d, Algorithm 2 computes a pair (M,C), where M is the number of non-constant monomials of Φv and C
is the constant term of Φv . The running time of the algorithm is Õ(nd + n2 ).
Proof. We start by proving the correctness of the algorithm. The proof is by induction on the structure
of the formula. We first analyze what happens at the leaves and then move up. During the analysis we
shall use the simple observation that the number of non-constant monomials is not affected by the (α, β )
labeling of the gates. We denote with (ML ,CL ) and (MR ,CR ) the results returned from the left child and
the right child, respectively. We consider the different possibilities for the operation labeling v (i. e.,
v.Type).
• v.Type = CONST or v.Type = IN: Φv computes a constant or a univariate polynomial. In this case
we can simply count the number of non-constant monomials and set M to this value.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 490
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
Algorithm 2 CountMonomials(v)
Input: The root v of a PROF.
Output: (M,C) where M is the number of the non-constant monomials of Φv ,
C is the constant term of Φv .
1: if v.Type = IN OR v.Type = CONST then {Φv is a univariate or constant polynomial}
2: M ← The number of non-constant monomials in Φv
3: return (M , v.β )
{Internal gate}
4: (ML , CL ) ← CountMonomials(v.Left)
5: (MR , CR ) ← CountMonomials(v.Right)
6: if v.Type = × then
7: C ← v.α ·CL ·CR + v.β
8: M ← (ML + NZ(CL )) · (MR + NZ(CR )) − NZ(CL ·CR )
9: return (M , C)
10: if v.Type = + then
11: C ← v.α · (CL +CR ) + v.β
12: M ← ML + MR
13: return (M , C)
When v is not a leaf we recursively run the algorithm on the left child and on the right child. Denote with
pL and pR the polynomials computed by the left child and the right child, respectively. We again analyze
the different options for v.Type.
• v.Type = ×: Φv computes a product of two functions, Φv = v.α · pL × pR + v.β . The total number of
monomials of pL × pR is (ML + NZ(CL )) · (MR + NZ(CR )). Therefore, the number of non-constant
monomials of pL × pR is (ML + NZ(CL )) · (MR + NZ(CR )) − NZ(CL ·CR ). From our observation
this is exactly the number of non-constant monomials of Φv . The claim regarding C is trivial.
• v.Type = +: Φv computes a sum of two functions. Φv = v.α × (pL +pR ) + v.β and, as before, the
number of non-constant monomials of pL + pR (and hence of Φv ) is ML + MR . Again, the claim
regarding C is trivial.
It is clear from the above analysis that the algorithm returns the correct answer. The claim regarding
the running time follows easily from the fact that the algorithm is a simple graph traversal that requires
O(n) time. As the individual degrees of the polynomial are bounded by d, computing the number of
non-zero monomials for the leaves requires O(d) time. In addition, note that at each step we multiply two
n log d-bit numbers (since 0 ≤ M ≤ (d + 1)n ). Thus the total running time is Õ(nd + n2 ).
5 Reconstruction of a PROF
In this section we discuss the problem of PROF reconstruction: given black-box access to a PROP P
we wish to construct a PROF Φ such that Φ computes P. We first give a reconstruction algorithm for
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 491
A MIR S HPILKA AND I LYA VOLKOVICH
the case of 0̄-justified PROPs. As an arbitrary PROP can be made 0̄-justified via a proper shifting (see
Lemma 2.5), we conclude the general case by giving an algorithm for computing such a shift efficiently.
We give three different reconstruction algorithms: a randomized algorithm, a deterministic algorithm
and a non-adaptive deterministic algorithm, with some deterioration in the running times between the
different models.
Let d be a bound on the individual degrees of the PROP in question. We assume that |F| > d. If this
is not the case then we allow the algorithm to make queries to the polynomial from an extension field
of appropriate size. We note that such a requirement is necessary even for the simple task of univariate
polynomial interpolation. Throughout this section we fix a set W ⊆ F of d + 1 distinct elements such that
0 ∈ W.
5.1 Reconstruction of a 0̄-justified PROF
Let P be a 0̄-justified PROP with individual degrees bounded by d. In [43] (Theorem 7.4 specialized to
k = 2) it was shown that P is uniquely determined by its values on the set An6 (W ) (recall Definition 2.8).
This implies that P can be reconstructed given those values. Yet, in principal, such an “information-
theoretic” reconstruction algorithm need not be efficient. In this section we give an efficient deterministic
reconstruction algorithm for 0̄-justified PROPs, which queries the polynomial on inputs from the set
An3 (W ).
Algorithm 3 Reconstruct 0̄-justified PROF
Input: Black-box access to a 0̄-justified PROP P.
Output: PROF Φ such that Φ ≡ P.
1: Learn the Preprocessing and var0 (P)
2: Construct the gate-graph of P
3: Construct a PROF Φ by recursively constructing its sub-formulas
Lemma 5.1. There exists an algorithm that given black-box access to a 0̄-justified PROP
P ∈ F[x1 , x2 , . . . , xn ] ,
with individual degrees bounded by d, constructs a (non-degenerate) PROF Φ, such that Φ ≡ P. Further-
more, the algorithm only queries P on the set An3 (W ). The running time of the algorithm is poly(n, d).
A high level description of the algorithm is given in Algorithm 3. We now describe in depth each step
of the algorithm.
5.1.1 Learning the preprocessing and var0 (P)
Given access to a PROP P(x̄) = Q(T (x̄)), the first step is to compute the standard preprocessing T (x̄) and
the set var0 (P). For that purpose, for every i ∈ [n] we define
Pi (xi ) , P(0, . . . , 0, xi , 0, . . . , 0) .
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 492
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
The next observation is immediate in the light of Lemma 3.19. Recall that for every 0̄-justified polynomial
P it holds that var0 (P) = var(P).
Observation 5.2. For each i ∈ [n] it holds that Pi (xi ) = ai · Ti (xi ) + bi for some ai , bi ∈ F. In addition,
ai 6= 0 iff xi ∈ var0 (P).
For the sake of future steps we also compute a witness ᾱ for P (recall Definition 3.20).
Algorithm 4 Learn the Preprocessing, var0 (P) and a Witness
Input: A 0̄-justified P(x̄) = Q(T (x̄)) given via black-box access.
Output: A standard preprocessing T (x̄) = (T1 (x1 ), . . . , Tn (xn )), var0 (P), a witness ᾱ for P.
1: for i ∈ [n] do
2: Interpolate Pi (xi ) as a univariate polynomial of degree d
3: Compute Ti from Pi
4: If Ti is non-constant find αi ∈ W such that Ti (αi ) 6= 0
5: Compute var0 (P)
Lemma 5.3. Given black-box access to a 0̄-justified PROP P, Algorithm 4 computes a standard prepro-
cessing T (x̄) of P, the set var0 (P) and a witness ᾱ for P. The running time of the algorithm is poly(n, d).
In addition, the algorithm does so by querying P on the set An1 (W ) alone.
Proof. First of all note that, as the individual degrees in Pi are bounded by d, the set An1 (W ) contains
enough points to interpolate Pi . It is easy to compute a standard Ti from Pi . From Observation 5.2,
xi ∈ var0 (P) iff the resulting Ti is a non-constant polynomial, thus, for every non-constant Ti there exists
αi ∈ W such that Ti (αi ) 6= 0. All the above operations can be carried out in time poly(n, d) by querying P
only on inputs from the set An1 (W ).
As P is 0̄-justified we can set
P , P|x[n]\var (P) =0̄[n]\var (P)
0 0
and, by renaming variables, assume w. l. o. g. that var(P) = var0 (P) = [n]. If P is constant or univariate
(i. e., |var0 (P)| ≤ 1) then we are done. Otherwise, P contains at least one (addition or multiplication) gate,
and we continue to the next step of Algorithm 3.
As we have learned the preprocessing, we will, in some sense, be able to “forget” about it and
reconstruct P as if it was a (non-preprocessed) ROP. In fact, the witness ᾱ and Lemma 3.22 allow us to
access the backbone ROF of P.
5.1.2 Constructing the gate-graph
In this step we recursively unfold the structure of the backbone ROF of a given PROP. As mentioned
above, after the previous step we can treat P as if there was no preprocessing involved (i. e., “assume” that
Ti (xi ) = xi ). Recall that the gate-graph of a PROP P is defined to be the gate-graph of its backbone ROP.
We will use Lemma 3.6 in order to construct that graph.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 493
A MIR S HPILKA AND I LYA VOLKOVICH
Algorithm 5 Construct The Gate-Graph
Input: a 0̄-justified PROP P(x̄) given via black-box access, a witness ᾱ for P.
Output: GP .
∂ 2P
For each pair i 6= j ∈ [n] add (i, j) to GP iff (0̄) 6= 0.
∂αi xi ∂α j x j
Lemma 5.4. Given black-box access to a 0̄-justified PROP P Algorithm 5 runs in time O(n2 ) and
constructs GP —the gate-graph of the P—by making queries to P from the set An2 (W ) alone.
Proof. Let P(x̄) = Q(T (x̄)). Since T (x̄) is standard, Lemma 3.22 implies that Q is 0̄-justified. Therefore,
by Lemmas 3.6 and 3.11:
∂ 2Q ∂ 2Q
(i, j) ∈ GP ⇐⇒ 6≡ 0 ⇐⇒ (0̄) 6= 0 .
∂ zi ∂ z j ∂ zi ∂ z j
On the other hand, Lemma 3.22 implies that
∂ 2P ∂ 2Q ∂ 2Q
(0̄) = · Ti (αi ) · T j (α j ) = Ti (αi ) · T j (α j ) · (0̄) .
∂αi xi ∂α j x j ∂ zi ∂ z j z̄=T (0̄) ∂ zi ∂ z j
As Ti (αi ), T j (α j ) 6= 0, correctness of the algorithm follows. From the definition of discrete partial
derivative (Definition 2.11), for each i, j the expression
∂ 2P
(0̄)
∂αi xi ∂α j x j
can be computed by querying P on four points from An2 (W ).
Having the gate-graph at hand, we can recursively reconstruct the formula gate-by-gate, according to
the labelling (+ or ×) of its top gate. By Lemma 3.23, every PROP P(x̄) that has at least one gate can
be presented in exactly one of the two forms P(x̄) = P1 (x̄) + P2 (x̄) or P(x̄) = P1 (x̄) · P2 (x̄) + c, depending
on the labeling of the top gate. Thus the high level view of step 3 of the reconstruction algorithm is as
follows: first we find a (possible) partition of the variables L ∪ ˙ R = var(P) such that L = var(P1 ) and
R = var(P2 ), then we recursively construct formulas Φi ≡ Pi and, finally, we “glue” them together to
obtain a formula for P.
5.1.3 Top gate “+”
In this case a partition can be obtained by considering the connected components of GP . The idea is
summarized in the following observation that follows from the definitions in Section 3.2.
Observation 5.5. Let Q(x̄) be a multilinear polynomial and let L ∪ ˙ R = var(Q) be a non-trivial partition
of var(Q). Then, Q can be represented in the form Q(x̄L , x̄R ) = QL (x̄L ) + QR (x̄R ) iff for every i ∈ L and
j ∈ R it holds that
∂ 2Q
≡ 0.
∂ xi ∂ x j
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 494
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
This gives rise to the following algorithm:
Algorithm 6 Top Gate + Case
Input: 0̄-justified PROP P(x̄) given via black-box access.
Output: PROF Φ ≡ P.
˙ R = var(P) of GP , such that there is no edge between a vertex in L and a vertex
1: Find a partition L ∪
in R. {P can be regarded as P(x̄L , x̄R ) = P1 (x̄L ) + P2 (x̄R )}
2: ΦL (x̄L ) ← Reconstruct(P(x̄L , 0̄)), ΦR (x̄R ) ← Reconstruct(P(0̄, x̄R ))
3: Φ(x̄L , x̄R ) ← ΦL (x̄L ) + ΦR (x̄R ) − P(0̄, 0̄)
Lemma 5.6. Given black-box access to a 0̄-justified PROP P, computed by a PROF with a top gate
labelled as “+,” Algorithm 6 constructs a PROF Φ that computes P. The algorithm makes queries to P
on inputs from the set An2 (W ) and from the set queried during the Reconstruct procedure. The running
time is poly(n) plus the time required by the Reconstruct procedure.
Proof. Let P(x̄) = Q(T (x̄)). By Lemma 3.23, P(x̄) = P1 (x̄) + P2 (x̄) and GP is disconnected. Hence,
we can find a non-trivial partition L ∪ ˙ R = var(P), to two components that are not connected to each
other. By Observation 5.5 we can assume w.l.o.g that L = var(P1 ) and R = var(P2 ), and hence ΦL (x̄L ) =
P1 (x̄L ) + P2 (0̄) and ΦR (x̄R ) = P1 (0̄) + P2 (x̄R ). Hence,
ΦL (x̄L ) + ΦR (x̄R ) − P(0̄, 0̄) = P(x̄) + P1 (0̄) + P2 (0̄) − P(0̄, 0̄) = P(x̄) ,
and so the last step gives the required formula.
5.1.4 Top gate “×”
The case of a top × gate is slightly more subtle. Here P(x̄) = Q(T (x̄)) = Q1 (T (x̄)) · Q2 (T (x̄)) + c.
Although c is a priori unknown, Observation 3.13 implies that a possible partition can be found by
considering all j such that Q is (x1 , x j )-separated mod F. For this purpose we shall use Corollary 2.17.
In general there is no efficient deterministic procedure to divide, or even check divisibility of, two
multivariate polynomials. Lemma 3.16 suggests that in our setting this can be done by considering a set
of three variables at a time. The structural result of Lemma 3.14 allows further simplification of the test.
Note that P and Q essentially depend on the same set of variables, thus we can abuse notation and say
that var(P) = var(Q).
Lemma 5.7. Given black-box access to a 0̄-justified PROP P, computed by a PROF with a top gate
labelled as “×,” Algorithm 7 constructs a PROF Φ that computes P. The running time of the algorithm
is poly(n) plus the time required by the Reconstruct procedure. The algorithm queries P on inputs from
the set An3 (W ) and on the inputs queried by the Reconstruct procedure.
Proof. Note that all the arithmetic operations in the algorithms are on polynomials of at most three
variables. Thus, those operation can be carried out efficiently by making queries to P on inputs from the
set An3 (W ). We now prove that
L = j ∈ [n] Q is not (x1 , x j )-separated mod F ∪ {1} .
The rest of the proof is similar to the proof of Lemma 5.6.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 495
A MIR S HPILKA AND I LYA VOLKOVICH
Algorithm 7 Top Gate × Case
Input: 0̄-justified PROP P(x̄), given via black-box access, and a witness ᾱ.
Output: PROF Φ ≡ P.
Finding L:
1: L ← {1}
2: for all j 6= k ∈ var(P) \ {1} do
3: P1, j,k ← Interpolate P|x[n]\{1, j,k} =0̄[n]\{1, j,k} {viewed as a three-variate polynomial}
!
∂ 2 P1, j,k ᾱ
∂ 2 P1, j,k
4: if ≡ 0 OR deg ∆1 j (P1, j,k ) 6= deg then
∂α1 x1 ∂α j x j ∂α1 x1 ∂α j x j
5: L ← L ∪ { j}
Reconstructing the formula:
1: R ← var(P) \ L {P can be regarded as P(x̄L , x̄R ) = P1 (x̄L ) · P2 (x̄R ) + c}
2: Chose i ∈ L, j ∈ R ! !
∂P ∂P ∂ 2P
3: c ← P(0̄, 0̄) − (0̄) · (0̄) ÷ (0̄)
∂αi xi ∂α j x j ∂αi xi ∂α j x j
4: ΦL (x̄L ) ← Reconstruct(P(x̄L , 0̄) − c), ΦR (x̄R ) ← Reconstruct(P(0̄, x̄R ) − c)
1
5: Φ(x̄L , x̄R ) ← · ΦL (x̄L ) × ΦR (x̄R ) + c
P(0̄, 0̄) − c
(⊆) Let j ∈ L \ {1}. Then there exists k ∈ var(P) \ {1, j} such that
!
∂ 2 P1, j,k ∂ 2 P1, j,k
≡ 0 or deg ∆ᾱ1j (P1, j,k ) 6= deg
∂α1 x1 ∂α j x j ∂α1 x1 ∂α j x j
for P1, j,k = P|x[n]\{1, j,k} =0̄[n]\{1, j,k} . In the former case, by Lemma 3.11,
∂ 2Q ∂ 2P
· T1 (α1 ) · T j (α j ) = ≡0
∂ z1 ∂ z j z̄=T (x̄) ∂α1 x1 ∂α j x j
and hence Q is not (x1 , x j )-separated mod F. The latter case is equivalent to
2
∂ Q(xk , 0̄)
deg ∆1 j (Q(x1 , x j , xk , 0̄)) 6= deg
∂ xi ∂ x j
which implies that
∂ 2Q
∆1 j Q 6= c ·
∂ x1 ∂ x j
for any c ∈ F. Thus, by Corollary 2.17, Q is (again) not (x1 , x j )-separated mod F.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 496
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
(⊇) Suppose Q is not (x1 , x j )-separated mod F. Lemma 3.16 implies that there exists k ∈ var(P)\ {1, j}
such that
Q|x[n]\{1, j,k} =0̄[n]\{1, j,k}
is not (xi , x j )-separated mod F. Now, if
∂ 2Q
≡0
∂ z1 ∂ z j
then j ∈ L; otherwise, by Lemma 3.14,
∂ 2 (Q(x1 , x j , xk , 0̄))
∆1 j Q|x[n]\{1, j,k} =0̄[n]\{1, j,k} = g(xk ) · ,
∂ x1 ∂ x j
where g(xk ) is a univariate polynomial. By Corollary 2.17 g(xk ) must be non-constant (since we assumed
that Q is not (x1 , x j )-separated mod F) and hence
2
∂ Q(xk , 0̄)
deg ∆1 j (Q(x1 , x j , xk , 0̄)) 6= deg ,
∂ xi ∂ x j
implying (again) that j ∈ L.
The rest of the algorithm follows the same rationale as before. We first find the value of the constant
c and then recursively construct the left and right subformulas. We note that since P is 0̄-justified, we can
perform the division in the last step.
5.1.5 Conclusion
We can now prove Lemma 5.1.
Proof of Lemma 5.1. The proof is by induction on |var0 (P)| = |var(P)|. By Lemma 5.3 we can learn the
set var0 (P) and handle the case |var0 (P)| ≤ 1. Now, assume |var0 (P)| ≥ 2. This implies that any PROF
computing P must have at least one gate. Lemma 5.4 allows us to construct the gate-graph from which
we can learn the labeling of the top gate (Lemma 3.4, Property 3). From this point on Lemmas 5.6 and 5.7
ensure the correctness of construction. We note that in each step we query P only on inputs from the set
An3 (W ). The claim regarding the running time follows from previous lemmas.
The next lemma shows that Algorithm 3 gives useful information also when applied to PROFs that
are not 0̄-justified.
Lemma 5.8. Let P a PROP, with individual degrees bounded by d, given via black-box access. Algo-
rithm 3, when given P as input, constructs a (non-degenerate) PROF Φ satisfying Φ ≡ P|x[n]\var (P) =0̄[n]\var (P) .
0 0
Proof. Denote
P0 , P|x[n]\var (P) =0̄[n]\var (P) .
0 0
Observe that var(P0 ) = var0 (P) = var0 (P0 ) hence P0 is a 0̄-justified PROP. To complete the proof note
that the algorithm runs in the same way when given either P or P0 as input.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 497
A MIR S HPILKA AND I LYA VOLKOVICH
5.2 Reconstruction of a general PROF
So far we gave a reconstruction algorithm for 0̄-justified PROPs. By combining our algorithm with
Lemma 2.5 we obtain an algorithm for reconstructing arbitrary PROPs, assuming that we know a justifying
assignment for the black-box polynomial.
Theorem 5.9. Let P ∈ F[x1 , x2 , . . . , xn ] be a PROP, with individual degrees bounded by d, given via
black-box access, and let ā ∈ Fn be a justifying assignment of P. Then there exists an algorithm that
constructs a (non-degenerate) PROF Φ such that Φ ≡ P by querying P on inputs from the set ā + An3 (W ).
The running time of the algorithm is poly(n, d).
Proof. Invoke the algorithm described in Lemma 5.1 on P0 (x̄) , P(x̄ + ā). By Lemma 2.5 P0 is a 0̄-
justified PROP. Therefore, the algorithm will return a PROF Φ such that Φ(x̄) ≡ P0 (x̄) , P(x̄ + ā). The
algorithm returns the formula Φ(x̄ − ā).
Consequently, to extend our algorithm to handle a general PROP P, we first need to find a justifying
assignment ā for P and then apply Theorem 5.9. We give a randomized algorithm, a deterministic
algorithm and a non-adaptive deterministic algorithm for computing a justifying assignment, thus
obtaining a reconstruction algorithm for general PROPs.
5.2.1 Randomized PROF reconstruction
The simplest way to get a justifying assignment is to pick one at random. This idea was used in the
previous works on ROF reconstruction [18, 10]. We give it here for completeness. We first state the
Schwartz-Zippel lemma:
Lemma 5.10 ([46, 38]). Let P ∈ F[x1 , x2 , . . . , xn ] be a non-zero polynomial with individual degrees
bounded by d. Then,
nd
Pr n [P(ā) = 0] ≤ .
ā∈F |F|
Since a justifying assignment is simply a common non-zero assignment of several polynomials, we
get the following corollary:
Corollary 5.11. Let n, d ≥ 1. Assume that |F| > 4n2 d. Let P ∈ F[x1 , x2 , . . . , xn ] be a PROP with individual
degrees bounded by d. Then,
3
Pr [ā is a justifying assignment of P] ≥ .
ā∈Fn 4
Proof. Let (Q(z̄), T (x̄)) be a standard decomposition of P and let ᾱ be a corresponding witness for P.
By Lemma 3.22:
" #
∂P ∂P
Pr [ā is not a justifying assignment of P] ≤ Pr n ∃i s.t. 6≡ 0 but (ā) = 0
ā∈Fn ā∈F ∂αi xi ∂αi xi
nd 1
≤ n· ≤ .
|F| 4
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 498
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
In fact, the statement can be shown to hold for arbitrary polynomials. We can now prove Theorem 1.3.
Proof of Theorem 1.3. The algorithm picks an assignment ā ∈ Fn at random and then runs the algo-
rithm described in Theorem 5.9. The claim follows from Corollary 5.11 and Theorem 5.9. Note that
randomization is required only for picking the justifying assignment ā.
5.2.2 Deterministic PROF reconstruction
We use a result from [43] to obtain a deterministic reconstruction algorithm.
Lemma 5.12 (Theorem 1 of [43]10 ). Let n, d ≥ 1. Assume |F| > n2 d. Then there exists a black-box
PIT algorithm for PROPs over F[x1 , x2 , . . . , xn ] with individual degrees bounded by d, that runs in time
(nd)O(log n) .
We are ready to prove Theorem 1.1.
Proof of Theorem 1.1. Given a PROP P invoke the algorithm in Lemma 4.1 to obtain a justifying as-
signment ā for P. Recall that Lemma 4.1 requires a PIT algorithm for a class that contains all partial
derivatives of PROPs. By Lemma 3.22, PROPs are closed under taking partial derivatives. Hence, the
PIT algorithm given in Lemma 5.12 satisfies the requirements of Lemma 4.1. The running time of the
algorithm (nd)O(log n) .
Now, apply Theorem 5.9. The reconstruction will take poly(n, d) time. Consequently, the whole
execution takes (nd)O(log n) time.
5.2.3 Non-adaptive PROF reconstruction
The reconstruction algorithm described by Algorithm 3 in non-adaptive as it queries the PROP on the
points in the set An3 (W ) regardless of the results of previous queries. Consequently, the randomized
version of the algorithm is non-adaptive as well. On the other hand, the algorithm given in Lemma 4.1 is
in fact adaptive: its subsequent queries to P depend on the result of the previous queries (for more details
see [43, Section 4.1]). This implies that the deterministic algorithm given in Theorem 1.1 is adaptive.
To obtain a non-adaptive algorithm we proceed as follows: instead of finding a (single) justifying
assignment and using it for the reconstruction, we will attempt to reconstruct P using every assignment
in a justifying set for PROPs (see Lemma 4.2).11 Let S be the set of all resulting PROFs. Following
Lemma 5.8, the PROF with the largest number of variables is the one we are looking for.
Proof of Theorem 1.2. The algorithm follows the steps specified in Algorithm 8.
Running time: By Lemma 4.2 Jd can be computed in time (nd)O(log n) . Other steps can be carried out
in polynomial time. Hence, the total running time is (nd)O(log n) .
10 The size of the field does not appear in the statement of Theorem 1 of [43], but this is what the proof gives.
11 Recall that a justifying set contains a justifying assignment for every PROP.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 499
A MIR S HPILKA AND I LYA VOLKOVICH
Algorithm 8 Non-Adaptive PROF Reconstruction
Input: A black-box access to a PROP P with individual degrees bounded by d.
Output: PROF Φ such that Φ ≡ P.
1: S ← 0/
2: Compute the set Jd {Using Lemma 4.2}
3: for all ā ∈ Jd do
4: Φā ← Reconstruct P {Using Theorem 5.9}
5: S ← S ∪ Φā
6: Find Φ0 ∈ S with the maximal var(Φ0 ), denote it with ΦM
7: return ΦM
Correctness of the algorithm: First of all, notice that since Algorithm 3 is non-adaptive so is Algo-
rithm 8. By Lemma 4.2, Jd contains a justifying assignment ā∗ of P, hence S must contain Φā∗ —the result
of reconstructing P using ā∗ as a justifying assignment input. By Theorem 5.9 Φā∗ ≡ P. We now argue
that ΦM ≡ Φā∗ ≡ P. By Lemma 5.8 var(ΦM ) ⊆ var(P). On the other hand, from the definition of ΦM , it
holds that |var(ΦM )| ≥ |var(Φā∗ )| = |var(P)|. This implies that var(ΦM ) = var(P). From Lemma 5.8 we
conclude that the assignment used to construct ΦM is a justifying assignment as well. Thus, ΦM ≡ P.
6 Read-once testing
In this section we study the relation between the PIT problem and the ROT problem and prove Theorem 1.5.
We first present a generic scheme that can be used to strengthen efficient deterministic PIT algorithms to
yield efficient deterministic ROT algorithms. Then we use known schemes to obtain ROT algorithms for
models for which PIT algorithms are known.12
6.1 Generic scheme
As was mentioned in Section 1.3, the main idea behind the scheme is “Doveryai, no Proveryai” (trust, but
verify): Given a circuit we run a PROP reconstructing algorithm on the circuit (based on Theorem 5.9).
If the algorithm encounters an error or is unable to run correctly, then we conclude that the circuit does
not compute a PROP and thus we stop and report a failure. Things are more complicated in the case of
success, that is, when the algorithm does construct a PROF. The problem is that we do not have any
guarantee regarding the correctness of our assumption (that the circuit computes a PROP) and hence no
guarantee that the PROF constructed indeed computes the same polynomial as the circuit. Moreover,
for any circuit C that computes a PROP, there exist many circuits (computing different polynomials)
“aliasing” C. That is, an execution of our reconstruction algorithm on each such circuit C0 6≡ C will
succeed and yield a PROF Φ such that Φ ≡ C 6= C0 .13 Consequently, for ROT we need to verify the
correctness of the output. The verification procedure is the technical core of our ROT algorithm, and is
12 In fact, in several cases we give “tailored” algorithms that are somewhat more efficient than the generic algorithm.
13C0 just needs to agree with C on the set of queries made by the reconstruction algorithm.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 500
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
given in Algorithm 10. Algorithm 9 gives the generic scheme for ROT. The algorithm works both in the
black-box and in the white-box models, depending on the PIT algorithm at hand.
Algorithm 9 Generic ROT Scheme
Input: (Black-box access to a) Circuit C that belongs to C.
Output: A PROF Φ such that Φ ≡ C if C computes a PROP and
“reject” otherwise.
1: Compute a justifying assignment ā using Lemma 4.1.
2: Reconstruct a PROF Φ from C using Theorem 5.9.
3: Verify that Φ ≡ C using Algorithm 10 (given in Subsection 6.2).
In Section 6.3 we give the proof of Theorem 1.5, that basically analyzes the running time of Algo-
rithm 9, given Lemma 4.1 and Theorems 5.9 and 6.2. Then, in Section 7, we go over some circuit classes
that have efficient PIT algorithms and give the corresponding ROT algorithms.
6.2 Read-once verification
Read-Once Verification is testing whether a given circuit C, from a certain circuit class C, and a given
PROF Φ compute the same polynomial. This is somewhat a harder problem than PIT since it requires
determining the equivalence of polynomials computed by circuits from two different circuit classes. We
shall work under the assumptions that C has a PIT algorithm and that the PROF Φ is the output of the
PROF reconstruction algorithm and thus is given to us explicitly (e. g., as a graph of computations). The
circuit C, on the other hand, may be given to us as a black-box (depending on the assumed PIT algorithm
for C). Clearly, if C − Φ ∈ C then the verification procedure is trivial (as C has a PIT algorithm). The
general case however is more complicated. The idea behind the algorithm is to recursively ensure that
every gate v of Φ computes the same polynomial as a corresponding restriction of C. To give a rough
sketch, we first find a justifying assignment ā for Φ. Then we consider v, the root of Φ. It has two
subformulas. Denote Φ = α · (Φv1 op Φv2 ) + β , where Φvi is the PROF computed at vi and op is either +
or ×. Assume that the variables of vi are Si (S1 and S2 are disjoint). Consider the circuit C1 that results
from C after substituting the corresponding values from ā to the variables in S2 . Similarly we define C2 ,
and the PROFs Φ1 and Φ2 .14 We now recursively verify that Ci ≡ Φi . The only thing left to do is to
verify that indeed C ≡ α · (C1 op C2 ) + β . This basically reduces the verification problem to the problem
of verifying that C ≡ C1 op C2 where C1 and C2 compute variable disjoint PROPs and op is either +
or ×. Note that this is a PIT problem for a circuit class that is closely related to C, although slightly
different (e. g., if C is the class of ΣΠΣ(k) circuits, defined in Section 7.2, then we need a PIT algorithm
for ΣΠΣ(O(k2 )) circuits). Therefore, we shall assume that a slightly larger circuit class has an efficient
deterministic PIT algorithm (e. g., a class containing C −C1 op C2 for variable disjoint C1 and C2 ). For
this we make the following definition of a “verifying class.” The definition uses the notations given in
Definition 2.18.
Definition 6.1. A circuit class CV is a (read-once) Verifying Class for a circuit class C if C1 +C2 +C3 ×
C4 ∈ CV when C1 ,C2 ,C3 ,C4 ∈ L(C) and C2 ,C3 ,C4 are defined on disjoint sets of variables.
14 In fact, in the algorithm it will be more convenient to have Φ = Φ and so we will slightly change the definition of C .
i vi i
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 501
A MIR S HPILKA AND I LYA VOLKOVICH
Note that for most circuit classes that have efficient deterministic PIT algorithms, there exists an
efficient deterministic PIT algorithm for a corresponding verifying class.
Algorithm 10 solved the verification problem following the outline described above. It uses notation
from Definition 4.3.
Algorithm 10 Verify (C, Φ)
Input: Circuit C from a circuit class C, a PROF Φ,
Access to a PIT algorithm for CV ,
and a justifying assignment ā for Φ and C.
Output: “accept” if C ≡ Φ and “reject” otherwise.
1: if v.Type = IN then {Φ is a univariate polynomial}
2: Check that C ≡ Φ {As two univariate polynomials of degree at most d}
{Internal Gate}
3: L ← var(Φv.Left )
4: R ← var(Φv.Right )
{Multiplication Gate}
5: if v.Type = × then
6: CL ← (C|xR =āR − v.β ) / (v.α · Φv.Right (ā))
7: CR ← (C|xL =āL − v.β ) / (v.α · Φv.Left (ā))
8: Verify(CL , Φv.Left ) and Verify(CR , Φv.Right ) {Recursively}
9: Check that C ≡ v.α · (CL ×CR ) + v.β {Using the PIT algorithm for CV }
{Addition Gate}
10: if v.Type = + then
11: CL ← (C|xR =āR − v.β ) / v.α − Φv.Right (ā)
12: CR ← (C|xL =āL − v.β ) / v.α − Φv.Left (ā)
13: Verify(CL , Φv.Left ) and Verify(CR , Φv.Right ) {Recursively}
14: Check that C ≡ v.α · (CL +CR ) + v.β {Using the PIT algorithm for CV }
{Everything is OK}
15: If any of the steps failed than reject, otherwise accept.
Theorem 6.2. Let C be an n-variate circuit from a circuit class C, that computes a polynomial with
individual degrees at most d, and Φ a PROF, such that var(C) = var(Φ). Let CV be a verifying class of C
and ā a justifying assignment for Φ and C. Then, given C, Φ and ā as input, Algorithm 10 runs in time
O(nd + n · t), where t is the cost of the given PIT algorithm for CV , and accepts if and only if C ≡ Φ.
Proof. We start by analyzing the running time.
Running time: As described above, the algorithm preforms a traversal over the tree of Φ. The PIT
algorithm of CV is invoked once for every internal gate. For each input gate we interpolate a univariate
polynomial using d + 1 queries. Hence the total running time is O(nd + n · t) when t is the cost of a single
PIT algorithm for CV . We now prove the correctness of the algorithm.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 502
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
Execution: We show that all the PIT calls that we make are “well defined,” namely, that in lines 9 and
14 we indeed have the correct input to the relevant PIT algorithm. We make the following observation:
At each step of the algorithm it holds that
1. C,CL ,CR ∈ L(C) (when CL and CR are defined). This follows (recursively) from the definitions of
CL and CR (both are obtained by applying a linear function to a restriction of C).
2. var(C) = var(Φ). By induction: For the base case we are guaranteed that var(C) = var(Φ). For the
induction step, consider the definition of the sets L and R. As ā is a justifying assignment of C we
have that
var(CL ) = var(C) \ R = var(Φ) \ var(Φv.Right ) = var(Φv.Left )
and similarly var(CR ) = var(Φv.Right ). It is only left to notice that this is in line with the recursive
invocation of the algorithm.
3. CL and CR are variable-disjoint. Indeed,
var(CL ) ∩ var(CR ) = var(Φv.Left ) ∩ var(Φv.Right ) = 0/ .
From Observations 1 and 3 it follows that
C − v.α · (CL ×CR ) − v.β ∈ CV and C − v.α · (CL +CR ) − v.β ∈ CV .
Hence, we can execute Lines 9 and 14 using the PIT algorithm of CV .
Correctness: The correctness of the algorithm can be proved by a simple induction. We need to show
that the algorithm accepts iff C ≡ Φ. The base case (i. e., Φ is a univariate polynomial of degree at most
d) is trivial. The inductive step follows from Lemmas 6.3 and 6.4 given below (and the correctness of the
PIT algorithm of CV ). This completes the proof.
We first handle the case of a multiplication gate.
Lemma 6.3. Let C(x̄, ȳ) and Φ(x̄, ȳ) = α · Φ` (x̄) × Φr (ȳ) + β be two polynomials and let (x̄0 , ȳ0 ) be a
justifying assignment of Φ. Then C(x̄, ȳ) ≡ Φ(x̄, ȳ) if and only if the following conditions hold:
C(x̄, ȳ0 ) − β
1. Φ` (x̄) = ,
α · Φr (ȳ0 )
C(x̄0 , ȳ) − β
2. Φr (ȳ) = ,
α · Φ` (x̄0 )
C(x̄, ȳ0 ) − β C(x̄0 , ȳ) − β
3. C(x̄, ȳ) = α · × +β.
α · Φr (ȳ0 ) α · Φ` (x̄0 )
Notice that the conditions are well defined since (x̄0 , ȳ0 ) is a justifying assignment of Φ and hence
Φ` (x̄0 ), Φr (ȳ0 ) 6= 0.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 503
A MIR S HPILKA AND I LYA VOLKOVICH
We next handle the case of an addition gate.
Lemma 6.4. Let C(x̄, ȳ) and Φ(x̄, ȳ) = α · (Φ` (x̄) + Φr (ȳ)) + β be two polynomials and let (x̄0 , ȳ0 ) be a
justifying assignment of Φ. Then C(x̄, ȳ) ≡ Φ(x̄, ȳ) if and only if the following conditions hold:
C(x̄, ȳ0 ) − β
1. Φ` (x̄) = − Φr (ȳ0 ), or
α
C(x̄0 , ȳ) − β
2. Φr (ȳ) = − Φ` (x̄0 ), or
α
C(x̄, ȳ0 ) − β C(x̄0 , ȳ) − β
3. C(x̄, ȳ) = α · − Φr (ȳ0 ) + − Φ` (x̄0 ) + β .
α α
Proof. Both proofs follow from straightforward manipulations.
6.3 Proof of Theorem 1.5
Proof of Theorem 1.5. We show that given C and CV , satisfying the assumptions, we can successfully
preform each step of the “generic ROT scheme” described in Algorithm 9.
1. Computing a Justifying Assignment
As ∂ C ⊆ CV we can compute a justifying assignment ā using Lemma 4.1.
The running time is O(n3 d · T (n, d, s)).
2. Reconstructing a PROF Φ from C
Given a justifying assignment ā we can reconstruct Φ from C using Theorem 5.9.
The running time is poly(n, d, s).
3. Verifying that Φ ≡ C
Notice that CV satisfies the conditions of Definition 6.1 and hence is a verifying class of C. We can
thus invoke the verification procedure described in Algorithm 10.
The running time is O(nd + n · T (n, d, s)).
The total running time is poly(n, s, d, T (n, d, s)).
In the next section we use Theorem 1.5 and the generic ROT scheme of Algorithm 9 in order to
get ROT algorithms for several restricted models for which PIT is known. Theorem 1.5 requires a PIT
algorithm for a class slightly larger than the class for which we design the ROT algorithm. However,
we note that basically any “reasonable” PIT algorithm yields a PIT algorithm for that larger class, and
hence implies a ROT algorithm. For example, an immediate consequence of Theorem 1.5 is that an
efficient deterministic PIT algorithm for multilinear circuits (either in the black-box or the white-box
model) implies an efficient deterministic ROT algorithm for multilinear circuits.
7 ROT for specific models
In this section we prove Theorems 1.6, 1.7, 1.8 and 1.9 by applying the ROT scheme of Section 6
(Algorithm 9). We start with the case of sparse polynomials (Theorem 1.7).
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 504
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
7.1 Sparse polynomials
An m-sparse polynomial is a polynomial with at most m (non-zero) monomials. Equivalently, it is a
polynomial computed by a depth-2 ΣΠ circuit of size m. Sparse polynomials received a lot of attention
(see, e. g., [7, 29, 31]) and several polynomial time algorithms for both reconstruction and PIT were
given, over sufficiently large fields. We now show how to solve the ROT problem for sparse polynomials.
Note that in [10] it is mentioned that a polynomial time interpolation algorithm is known in the case
that the given ROF is a sparse polynomial (see last sentence of paragraph 4 on page 707 of [10] that
refers to [30]). We present another proof here that gives a stronger result (thus proving Theorem 1.7). We
denote by ΣΠ(m, d) the class of m-sparse polynomials, in n variables, of degree d.15 In order to apply
Algorithm 9 on ΣΠ(m, d) we shall need a PIT algorithm for ΣΠ(poly(m), poly(d)). Several such results
are known, see [29] and references within.
Lemma 7.1 ([29]). Let n, m, d ≥ 1. Assume |F| > (nd)6 . There is a deterministic black-box PIT algorithm
for ΣΠ(m, d) that runs in time poly(m, d).
Note that ΣΠ(m2 + 4m + 3, 2d) is a verifying class for ΣΠ(m, d) (recall Definition 6.1). Hence, we
can use the above lemma in conjunction with Algorithm 9 to prove Theorem 1.7. We now give an
alternative proof of the theorem that follows the same lines as the scheme of Algorithm 9 albeit using a
different verification procedure.
Proof of Theorem 1.7. Let P ∈ ΣΠ(m, d) be a sparse polynomial given via black-box access. We follow
the scheme outlined in Algorithm 9 noting that ∂ ΣΠ(m, d) ⊆ ΣΠ(m, d). We first run the algorithms
suggested by Lemma 4.1 and Theorem 5.9 to obtain a candidate PROF Φ. Of course, should any of
the algorithms fail, we reject (“not PROF”). We now wish to verify that Φ ≡ P. Originally, we used
Algorithm 10, but here we use a different scheme instead. We first compute the degree of Φ (denoted
by D) by a simple traversal, and then run Algorithm 2 to count the number of monomials in the PROP
computed by Φ (denoted by M). Now, if M > m or D > d then, obviously, Φ 6≡ P. Otherwise, we set
P0 , Φ − P. Note that the resulting polynomial P0 has at most 2m monomials and hence P0 ∈ ΣΠ(2m, d).
Consequently, we can apply Lemma 7.1 to determine whether P0 ≡ 0. Note that the PIT algorithm for
ΣΠ(2m, d) is polynomial in n, m, d (and is slightly more efficient than Algorithm 10 when given access
to a PIT algorithm for the class ΣΠ(m2 + 4m + 3, 2d)).
7.2 Depth-3 circuits
A depth-3 ΣΠΣ(k) circuit C computes a polynomial of the form
k k di
C(x̄) = ∑ Fi (x̄) = ∑ ∏ Li j (x̄) ,
i=1 i=1 j=1
where the Li j (x̄)-s are linear functions;
n
Li j (x̄) = ∑ ati j xt + a0i j
t=1
15 As the number of variables is always n we do not mention it.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 505
A MIR S HPILKA AND I LYA VOLKOVICH
with ati j ∈ F. We denote by ΣΠΣ(k, d) a ΣΠΣ(k) in which each Fi has degree at most d (i. e., di ≤ d).
Those circuits were a subject of a long line of research [12, 27, 26, 41, 5, 25, 35, 36, 37] yielding several
efficient deterministic PIT algorithms. The state of the art black-box PIT algorithm for this circuit class
was given in [36].
Lemma 7.2 ([36]). Let n, k, d ≥ 1. Assume |F| > dnk2 . There is a deterministic black-box PIT algorithm
for n-variate polynomials computed by ΣΠΣ(k, d) circuits that runs in time poly(n) · d O(k) .
We now give the proof of Theorem 1.8.
Proof of Theorem 1.8. Observe that the class ΣΠΣ(k2 + 4k + 3, 2d) is a verifying class for ΣΠΣ(k, d).
Hence, we can invoke Algorithm 9 in conjunction with Lemma 7.2. Theorem 1.5 guarantees the
correctness. The running time is poly(n) · d O(k ) .
2
7.3 Multilinear depth-4 circuits
A depth-4 ΣΠΣΠ(k) circuit C has four layers of alternating Σ and Π gates (the top Σ gate is at level one)
and it computes a polynomial of the form
k k di
C(x̄) = ∑ Fi (x̄) = ∑ ∏ Pi j (x̄)
i=1 i=1 j=1
where the Pi j (x̄)-s are polynomials computed by a ΣΠ circuit (i. e., sparse polynomials). In other words,
the Pi j s are being computed by the last two ΣΠ layers of the circuit and are the inputs to the Π gates at
the second level. A multilinear ΣΠΣΠ(k) circuit is a ΣΠΣΠ(k) circuit in which each multiplication gate
Fi computes a multilinear polynomial. PIT algorithms were given for restricted classes of depth-4 circuits
in [34, 41, 5, 3, 2, 33, 23]. The state-of-the-art PIT algorithm for multilinear depth-4 circuits was given
in [33].
Lemma 7.3 ([33]). Let n, k, s ≥ 1. Assume |F| > n2 . There is a deterministic black-box PIT algorithm for
n-variate polynomials, computed by multilinear ΣΠΣΠ(k) circuits, of size s, that runs in time (ns)O(k ) .
3
We can now prove Theorem 1.9.
Proof of Theorem 1.9. First, observe that the class of multilinear ΣΠΣΠ(k2 + 4k + 3) circuits of size
4s + 4 is a verifying class for multilinear ΣΠΣΠ(k) circuits of size s. Hence, we can invoke Algorithm 9
in conjunction with Lemma 7.3. Theorem 1.5 guarantees correctness. The running time is (ns)O(k ) .
6
7.4 Multilinear read-k formulas
Read-k formulas are formulas in which each variable appears at most k times. The study of this class of
formulas was initiated in [40, 41] where sums of read-once formulas were studied. Efficient deterministic
PIT algorithms were given for multilinear [3] and bounded depth [2] read-k formulas. Here we only
consider multilinear read-k formulas, the bounded depth case is similar.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 506
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
Lemma 7.4 ([3]). Let n, k ≥ 1 and assume |F| > n2 . Let F be a multilinear read-k formula over
F[x1 , x2 , . . . , xn ]. Then:
O(k)
• There is a deterministic algorithm that given F explicitly decides if F ≡ 0 in time nk .
• There is a deterministic algorithm that given black-box access to F decides if F ≡ 0 in time
O(k)
nk +O(k log n) .
We now show a generalization of those PIT algorithms to ROT algorithms, thus proving Theorem 1.6.
Proof of Theorem 1.6. Let F be a multilinear read-k formula. We first use Lemma 4.1 to compute a
justifying assignment for F. It is easy to see that this circuit class is closed under partial derivatives, thus
we can use the PIT algorithms from Lemma 7.4.
Next, we construct a candidate ROF Φ by applying Theorem 5.9. To complete the procedure, we
need to verify that Φ = F or, in other words, that F − Φ ≡ 0. This is a case of a PIT of a multilinear
read-(k + 1) formula, hence we can use Lemma 7.4 again to obtain the result.
8 Acknowledgments
The authors would like to thank Lisa Hellerstein [20] for sharing the containment of [30] with us. We
thank Laci Babai and the anonymous referees for useful comments that greatly improved the presentation
of our results.
A Proof of Lemma 3.10
In this section we give the proof of Lemma 3.10. To ease the reading we repeat the statement of the
lemma.
Lemma 3.10. A partial derivative of a ROP is a ROP. Moreover, a partial derivative of a 0̄-justified ROP
is also a 0̄-justified ROP.
The following lemma will be useful.
Lemma A.1. Let P(x1 , x2 , . . . , xn ) be a ROP such that xi , x j ∈ var(P). Set I = var(P) \ {xi , x j }. Assume
that
∂ 2P ∂ 2P
6≡ 0 and ≡ 0.
∂ xi ∂ x j ∂ xi ∂ x j xI =0̄
Then,
∂P ∂P
≡0 or ≡ 0.
∂ xi xI =0̄ ∂ x j xI =0̄
Proof. Let Φ be a ROF computing P and v = fcg x j , xi . As
∂ 2P
6≡ 0 ,
∂ xi ∂ x j
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 507
A MIR S HPILKA AND I LYA VOLKOVICH
it follows that v is a multiplication gate. Let Pv (x̄) be the polynomial computed by v in Φ. It is not
hard to see that there exist polynomials A(x̄) and B(x̄), that do not share variables with Pv (x̄), such that
P(x̄) ≡ A(x̄) · Pv (x̄) + B(x̄). Clearly, xi , x j ∈ var(Pv ) \ (var(A) ∪ var(B)). By the definition of fcg and
Lemma 3.9, Pv (x̄) has the form Pv = P1 · P2 + c, where xi ∈ var(P1 ), x j ∈ var(P2 ) and c ∈ F. We thus have
that
∂P ∂ Pv ∂ P1 ∂P ∂ Pv ∂ P2
= A· = A· · P2 and = A· = A · P1 · .
∂ xi ∂ xi ∂ xi ∂xj ∂xj ∂xj
In addition, we have that
∂ 2P ∂ P1 ∂ P2
= A· · .
∂ xi ∂ x j ∂ xi ∂ x j
This implies that
∂P ∂P ∂ P1 ∂ P2
· = A· · P2 · A · P1 ·
∂ xi xI =0̄ ∂ x j xI =0̄ ∂ xi xI =0̄ ∂ x j xI =0̄
∂ P1 ∂ P2
= A· · · (A · P1 · P2 )
∂ xi ∂ x j xI =0̄ xI =0̄
∂ 2P
= · (A · P1 · P2 ) ≡0.
∂ xi ∂ x j xI =0̄ xI =0̄
In particular, either
∂P ∂P
≡0 or ≡ 0.
∂ xi xI =0̄ ∂ x j xI =0̄
Proof of Lemma 3.10. Let P be a ROP and i ∈ [n]. We prove the claim by induction on k = |var(P)|. For
k = 0, 1 the claim is trivial. For k ≥ 2 we get by Lemma 3.9 that P can be in one of two forms.
Case 1. P(x̄) = P1 (x̄) + P2 (x̄). Since P1 and P2 are variable disjoint we can assume w. l. o. g. that
∂ P ∂ P1
= .
∂ xi ∂ xi
In addition, |var(P1 )| < |var(P)| and so by the induction hypothesis we get that
∂ P ∂ P1
=
∂ xi ∂ xi
is a ROP.
Case 2. P(x̄) = P1 (x̄) · P2 (x̄) + c. Again we assume w. l. o. g. that
∂ P ∂ P1
= · P2 .
∂ xi ∂ xi
As before, ∂∂Px1i is a ROP. Since P1 and P2 are variable disjoint and P2 is a ROP, we have that
∂ P ∂ P1
= · P2
∂ xi ∂ xi
is a ROP as well.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 508
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
For the “moreover” part, assume for a contradiction that for some i ∈ [n], we have that ∂∂ xPi is not
0̄-justified. That is, there exists some j ∈ [n] such that ∂∂ xPi depends on x j , however, for I = var(P) \ {i, j},
the polynomial
∂P
∂ xi xI =0̄
does not depend on x j . In other words, we have that
∂ 2P ∂ 2P
6≡ 0 and ≡ 0.
∂ xi ∂ x j ∂ xi ∂ x j xI =0̄
Lemma A.1 implies that either
∂P ∂P
≡0 or ≡0
∂ xi xI =0̄ ∂ x j xI =0̄
holds. On the other hand, xi , x j ⊆ var(P ), since P is a 0̄-justified ROP, and hence
xI =0̄
∂P ∂P
6≡ 0 and 6≡ 0 ,
∂ xi xI =0̄ ∂ x j xI =ō
in contradiction.
References
[1] M ANINDRA AGRAWAL: Proving lower bounds via pseudo-random generators. In 25th Internat.
Conf. Foundations of Software Technology and Theoretical Computer Science (FSTTCS’05), 2005,
pp. 92–105, 2005. [doi:10.1007/11590156_6] 469
[2] M ANINDRA AGRAWAL , C HANDAN S AHA , R AMPRASAD S APTHARISHI , AND N ITIN S AX -
ENA : Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-
3 transcendence degree-k circuits. In Proc. 44th STOC, pp. 599–614. ACM Press, 1980.
[doi:10.1145/2213977.2214033, arXiv:1111.0582] 506
[3] M ATTHEW A NDERSON , D IETER VAN M ELKEBEEK , AND I LYA VOLKOVICH: Derandomizing poly-
nomial identity testing for multilinear constant-read formulae. In Proc. 26th IEEE Conf. on Compu-
tational Complexity (CCC’11), pp. 273–282, 2011. See also at ECCC. [doi:10.1109/CCC.2011.18]
472, 506, 507
[4] DANA A NGLUIN , L ISA H ELLERSTEIN , AND M AREK K ARPINSKI: Learning read-once for-
mulas with queries. J. ACM, 40(1):185–210, 1993. Preliminary version in COLT’89.
[doi:10.1145/138027.138061] 470
[5] V. A RVIND AND PARTHA M UKHOPADHYAY: The monomial ideal membership problem and
polynomial identity testing. Inform. and Comput., 208(4):351–363, 2010. See also at ECCC.
[doi:10.1016/j.ic.2009.06.003] 506
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 509
A MIR S HPILKA AND I LYA VOLKOVICH
[6] A MOS B EIMEL , F RANCESCO B ERGADANO , NADER H. B SHOUTY, E YAL K USHILEVITZ , AND
S TEFANO VARRICCHIO: Learning functions represented as multiplicity automata. J. ACM,
47(3):506–530, 2000. Preliminary version in FOCS’96. [doi:10.1145/337244.337257] 469
[7] M ICHAEL B EN -O R AND P RASOON T IWARI: A deterministic algorithm for sparse multivariate
polynominal interpolation (extended abstract). In Proc. 20th STOC, pp. 301–309. ACM Press, 1988.
[doi:10.1145/62212.62241] 472, 505
[8] DAOUD B SHOUTY AND NADER H. B SHOUTY: On interpolating arithmetic read-once formulas
with exponentiation. J. Comput. System Sci., 56(1):112–124, 1998. Preliminary version in COLT’94.
[doi:10.1006/jcss.1997.1550] 470, 473
[9] NADER H. B SHOUTY AND R ICHARD C LEVE: Interpolating arithmetic read-once formulas in
parallel. SIAM J. Comput., 27(2):401–413, 1998. [doi:10.1137/S009753979528812X] 470
[10] NADER H. B SHOUTY, T HOMAS R. H ANCOCK , AND L ISA H ELLERSTEIN: Learning arithmetic
read-once formulas. SIAM J. Comput., 24(4):706–735, 1995. Preliminary version in STOC’92.
[doi:10.1137/S009753979223664X] 470, 471, 473, 474, 475, 479, 498, 505
[11] NADER H. B SHOUTY, T HOMAS R. H ANCOCK , AND L ISA H ELLERSTEIN: Learning boolean
read-once formulas with arbitrary symmetric and constant fan-in gates. J. Comput. System Sci.,
50(3):521–542, 1995. Preliminary version in COLT’92. [doi:10.1006/jcss.1995.1042] 470
[12] Z EEV DVIR AND A MIR S HPILKA: Locally decodable codes with 2 queries and polynomial identity
testing for depth 3 circuits. SIAM J. Comput., 36(5):1404–1434, 2007. Preliminary version in
STOC’05. [doi:10.1137/05063605X] 472, 506
[13] 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. See also at ECCC. [doi:10.1145/2591796.2591816] 473
[14] 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. See also at ECCC. [doi:10.1109/FOCS.2013.34] 473
[15] J OACHIM VON ZUR G ATHEN AND E RICH K ALTOFEN: Factoring sparse multivariate polynomials.
J. Comput. System Sci., 31(2):265–287, 1985. Preliminary version in FOCS’83. [doi:10.1016/0022-
0000(85)90044-3] 471
[16] D IMA Y U . G RIGORIEV, M AREK K ARPINSKI , AND M ICHAEL F. S INGER: Fast parallel algorithms
for sparse multivariate polynomial interpolation over finite fields. SIAM J. Comput., 19(6):1059–
1063, 1990. [doi:10.1137/0219073] 472
[17] A NKIT G UPTA , N EERAJ K AYAL , AND S ATYANARAYANA V. L OKAM: Reconstruction of depth-4
multilinear circuits with top fan-in 2. In Proc. 44th STOC, pp. 625–642. ACM Press, 1980. See also
at ECCC. [doi:10.1145/2213977.2214035] 469
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 510
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
[18] T HOMAS R. H ANCOCK AND L ISA H ELLERSTEIN: Learning read-once formulas over fields and
extended bases. In Proc. 4th Ann. Workshop on Computational Learning Theory (COLT’91), pp.
326–336, 1991. [ACM:114867] 470, 473, 474, 475, 479, 480, 498
[19] J OOS H EINTZ AND C LAUS -P ETER S CHNORR: Testing polynomials which are easy to compute (ex-
tended abstract). In Proc. 12th STOC, pp. 262–272. ACM Press, 1980. [doi:10.1145/800141.804674]
469
[20] L ISA H ELLERSTEIN: Private communication, 2009. 472, 507
[21] VALENTINE K ABANETS AND RUSSELL I MPAGLIAZZO: Derandomizing polynomial identity tests
means proving circuit lower bounds. Comput. Complexity, 13(1-2):1–46, 2004. Preliminary version
in STOC’03. See also at ECCC. [doi:10.1007/s00037-004-0182-6] 469
[22] M AURICIO K ARCHMER , NATI L INIAL , I LAN N EWMAN , M IKE S AKS , AND AVI W IGDERSON:
Combinatorial characterization of read-once formulae. Discrete Mathematics, 114(1-3):275–282,
1993. [doi:10.1016/0012-365x(93)90372-z] 470
[23] Z OHAR S HAY K ARNIN , PARTHA M UKHOPADHYAY, A MIR S HPILKA , AND I LYA VOLKOVICH:
Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. SIAM J.
Comput., 42(6):2114–2131, 2013. Preliminary version in STOC’10. [doi:10.1137/110824516] 506
[24] Z OHAR S HAY K ARNIN AND A MIR S HPILKA: Reconstruction of generalized depth-3 arithmetic
circuits with bounded top fan-in. In Proc. 24th IEEE Conf. on Computational Complexity (CCC’09),
pp. 274–285, 2009. Full version on author’s website. [doi:10.1109/ccc.2009.18] 469
[25] Z OHAR S HAY K ARNIN AND A MIR S HPILKA: Black box polynomial identity testing of general-
ized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica, 31(3):333–364, 2011.
Preliminary version in CCC’08. [doi:10.1007/s00493-011-2537-3] 472, 506
[26] N EERAJ K AYAL AND S HUBHANGI S ARAF: Blackbox polynomial identity testing for depth 3
circuits. In Proc. 50th FOCS, pp. 198–207. IEEE Comp. Soc. Press, 2009. See also at ECCC.
[doi:10.1109/FOCS.2009.67] 472, 506
[27] N EERAJ K AYAL AND N ITIN S AXENA: Polynomial identity testing for depth 3 circuits. Comput.
Complexity, 16(2):115–138, 2007. Conference version at CCC’06. [doi:10.1007/s00037-007-0226-
9] 472, 506
[28] A DAM R. K LIVANS AND A MIR S HPILKA: Learning restricted models of arithmetic cir-
cuits. Theory of Computing, 2(1):185–206, 2006. Preliminary version in COLT’03.
[doi:10.4086/toc.2006.v002a010] 469
[29] A DAM R. K LIVANS AND DANIEL A. S PIELMAN: Randomness efficient identity testing of multivari-
ate polynomials. In Proc. 33rd STOC, pp. 216–223. ACM Press, 2001. [doi:10.1145/380752.380801]
469, 470, 472, 505
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 511
A MIR S HPILKA AND I LYA VOLKOVICH
[30] BARBARA L HOTZKY: On the computational complexity of some algebraic counting problems.
Ph.D. thesis, University of Bonn, Department of Computer Science, Bonn, Germany, 1991. 472,
505, 507
[31] R ICHARD J. L IPTON AND N ISHEETH K. V ISHNOI: Deterministic identity testing for multivariate
polynomials. In Proc. 14th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’03), pp. 756–760.
ACM Press, 2003. [ACM:644233] 505
[32] 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] 473
[33] S HUBHANGI S ARAF AND I LYA VOLKOVICH: Black-box identity testing of depth-4 multi-
linear circuits. In Proc. 43rd STOC, pp. 421–430. ACM Press, 2011. See also at ECCC.
[doi:10.1145/1993636.1993693] 472, 506
[34] N ITIN S AXENA: Diagonal circuit identity testing and lower bounds. In Proc. 35th Internat. Colloq.
on Automata, Languages and Programming (ICALP’08), pp. 60–71, 2008. See also at ECCC.
[doi:10.1007/978-3-540-70575-8_6] 506
[35] N ITIN S AXENA AND C. S ESHADHRI: An almost optimal rank bound for depth-3 identities.
SIAM J. Comput., 40(1):200–224, 2011. Preliminary version in CCC’09. See also at ECCC.
[doi:10.1137/090770679] 506
[36] N ITIN S AXENA AND C. S ESHADHRI: Blackbox identity testing for bounded top-fanin depth-3
circuits: The field doesn’t matter. SIAM J. Comput., 41(5):1285–1298, 2012. Preliminary version in
STOC’11. See also at ECCC. [doi:10.1137/10848232] 472, 506
[37] N ITIN S AXENA AND C. S ESHADHRI: From Sylvester-Gallai configurations to rank bounds:
Improved blackbox identity test for depth-3 circuits. J. ACM, 60(5):33, 2013. Preliminary version
in FOCS’10. See also at ECCC. [doi:10.1145/2528403] 506
[38] JACOB T. S CHWARTZ: Fast probabilistic algorithms for verification of polynomial identities. J.
ACM, 27(4):701–717, 1980. Preliminary version in ISSAC’79. [doi:10.1145/322217.322225] 471,
498
[39] A MIR S HPILKA: Interpolation of depth-3 arithmetic circuits with two multiplication gates. SIAM J.
Comput., 38(6):2130–2161, 2009. Preliminary version in STOC’07. [doi:10.1137/070694879] 469
[40] A MIR S HPILKA AND I LYA VOLKOVICH: Read-once polynomial identity testing. In Proc. 40th
STOC, pp. 507–516. ACM Press, 2008. [doi:10.1145/1374376.1374448] 465, 473, 474, 506
[41] A MIR S HPILKA AND I LYA VOLKOVICH: Improved polynomial identity testing for read-once
formulas. In Proc. 12th Internat. Workshop on Approximation Algorithms for Combinatorial
Optimization Problems (APPROX’09), pp. 700–713, 2009. Full version at ECCC. [doi:10.1007/978-
3-642-03685-9_52] 473, 474, 506, 513
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 512
O N R ECONSTRUCTION AND T ESTING OF R EAD -O NCE F ORMULAS
[42] A MIR S HPILKA AND I LYA VOLKOVICH: On the relation between polynomial identity testing
and finding variable disjoint factors. In Proc. 37th Internat. Colloq. on Automata, Languages and
Programming (ICALP’10), pp. 408–419, 2010. See also at ECCC. [doi:10.1007/978-3-642-14165-
2_35] 478
[43] A MIR S HPILKA AND I LYA VOLKOVICH: Read-once polynomial identity testing. Electron. Colloq.
on Comput. Complexity (ECCC), 17:11, 2010. Full version of [41]. [ACM:1616551] 474, 481, 488,
492, 499
[44] A MIR S HPILKA AND A MIR Y EHUDAYOFF: Arithmetic circuits: A survey of recent results and
open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207–388, 2010.
[doi:10.1561/0400000039] 469, 470
[45] I LYA VOLKOVICH: Characterizing arithmetic read-once formulae. Manuscript, 2014.
[arXiv:1408.1995] 471, 475
[46] R ICHARD Z IPPEL: Probabilistic algorithms for sparse polynomials. In Internat. Symp. Symbolic
and Algebraic Computation (ISSAC’79), pp. 216–226, 1979. [doi:10.1007/3-540-09519-5_73] 471,
498
AUTHORS
Amir Shpilka
Associate Professor
Tel-Aviv University, Tel-Aviv, Israel
shpilka post tau ac il
http://www.cs.tau.ac.il/~shpilka
Ilya Volkovich
Postdoctoral Visiting Scholar
Department of Electrical Engineering and Computer Science
University of Michigan
ilyavol umich edu
http://www.umich.edu/~ilyavol
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 513
A MIR S HPILKA AND I LYA VOLKOVICH
ABOUT THE AUTHORS
A MIR S HPILKA obtained his Ph. D. in Computer Science and Mathematics from the Hebrew
University in Jerusalem in 2001 under the supervision of Avi Wigderson. From 2005 to
2014 he was a faculty member at the CS department at the Technion. In October 2014 he
joined the CS department at Tel-Aviv University. He is married to Carmit and has two
children. His research interests lie in complexity theory, especially in arithmetic circuit
complexity. When not working or enjoying his family he likes to read and play chess.
I LYA VOLKOVICH graduated from the Computer Science Department of the Technion in
2012, where he had the pleasure of doing his Ph. D. under the supervision of Amir Shpilka.
The topic of his thesis was Polynomial Identity Testing and related algebraic problems.
Subsequently he was a postdoc at the Center for Computational Intractability at Princeton
University and held a visiting position at the School of Mathematics at the Institute for
Advanced Study. Currently he is a postdoctoral visitor at the University of Michigan.
His research interests lie in theoretical computer science and discrete mathematics, in
particular in computational complexity theory, derandomization, algebraic complexity
and applications of algebraic tools to algorithms and other areas of CS. His recent
interests also include algorithmic and general game theory.
T HEORY OF C OMPUTING, Volume 10 (18), 2014, pp. 465–514 514