Interpolating Arithmetic Read-Once Formulas in Parallel.
A formula is read-once if each variable appears in it at most once. An arithmetic formula is one in which the operations are addition, subtraction, multiplication, and division (and constants are allowed). We present a randomized (Las Vegas) parallel algorithm for the exact interpolation of arithmetic read-once formulas over sufficiently large fields. More specifically, for $n$-variable read-once formulas and fields of size at least 3(n2+3n-2), our algorithm runs in $O(\log^2 n)$ parallel steps using O(n4) processors (where the field operations are charged unit cost). This complements some results from [N. H. Bshouty and R. Cleve, Proc. 33rd Annual Symposium on the Foundations of Computer Science, IEEE Computer Science Press, Los Alamitos, CA, 1992, pp. 24--27] which imply that other classes of read-once formulas cannot be interpolated---or even learned with membership and equivalence queries---in polylogarithmic time with polynomially many processors (even though they can be learned sequentially in polynomial time). These classes include boolean read-once formulas and arithmetic read-once formulas over fields of size $o(n / \log n)$ (for n variable read-once formulas).
Introduction
The problem of interpolating a formula (from some class C) is the problem of exactly
identifying the formula from queries to the assignment (membership) oracle.
The interpolation algorithm queries the oracle with an assignment a and the oracle
returns the value of the function at a.
There are a number of classes of arithmetic formulas that can be interpolated sequentially
in polynomial-time as well as in parallel in poly-logarithmic-time (with
polynomially many processors). These include sparse polynomials and sparse rational
functions ([BT88,BT90,GKS90,GrKS88,RB89,M91]).
Research supported in part by NSERC of Canada. Author's E-mail addresses:
bshouty@cpsc.ucalgary.ca and cleve@cpsc.ucalgary.ca.
A formula over a variable set V is read-once if each variable appears at most once
in it. An arithmetic read-once formula over a field K is a read-once formula over
the basic operations of the field K: addition, subtraction, multiplication, division,
and constants are also permitted in the formula. The size of an arithmetic formula
is the number of instances of variables (i.e. leaves) in it.
Bshouty, Hancock and Hellerstein [BHH92] present a randomized sequential
polynomial-time algorithm for interpolating arithmetic read-once formulas (AROFs)
over sufficiently large fields. Moreover, they show that, for arbitrarily-sized fields,
read-once formulas can be learned using equivalence queries in addition
to membership queries.
The question of whether arithmetic read-once formulas can be interpolated (or
learned) quickly in parallel depends on the size of the underlying field. It is shown
in [BC92] that for arithmetic read-once formulas over fields with o(n= log n) elements
there is no poly-logarithmic-time algorithm that uses polynomially many
processors (for interpolating, as well as learning with membership and equivalence
queries). Also, a similar negative result holds for boolean read-once formulas.
We present a (Las Vegas) parallel algorithm for the exact interpolation of arithmetic
read-once formulas over sufficiently large fields. For fields of size at least
2), the algorithm runs in O(log 2 n) parallel steps using O(n 4 ) processors
(where the field operations are charged unit cost).
If the "obvious" parallelizations are made to the interpolating algorithm in
(i.e., parallelizations of independent parts of the computation) one obtains
a parallel running time that is \Theta(d), where d is the depth of the target
formula. Since, in general, d can be as large as \Theta(n), this does not result in significant
speedup. Our parallel algorithm uses some techniques from the sequential
algorithm of [BHH92] as well as some new techniques that enable nonlocal features
of the AROF to be determined in poly-logarithmic-time.
The parallel algorithm can be implemented on an oracle parallel random access
machine (PRAM). More specifically, it is an exclusive-read exclusive-write (EREW)
PRAM-which means that processor's accesses to their communal registers are
constrained so that no two processors can read from or write to the same register
simultaneously. The EREW PRAM initially selects some random input values
(uniformly and independently distributed) and then performs O(n 3 ) membership
queries (via its oracle).
queries
The learning criterion we consider is exact identification. There is a formula f
called the target formula, which is a member of a class of formulas C defined over
the variable set V . The goal of the learning algorithm is to halt and output a
formula h from C that is equivalent to f .
In a membership query, the learning algorithm supplies values (x (0)
the variables in V , as input to a membership oracle, and receives in return the
value of f(x (0)
the projection of f obtained by
hard-wiring x to the value x (0) . An assignment of values to some subset of a
read-once formula's variables defines a projection, which is the formula obtained
by hard-wiring those assigned variables to their values in the formula and then
rewriting the formula to eliminate constants from the leaves. Note that if f 0 is
a projection of f , it is possible to simulate a membership oracle for f 0 using a
membership oracle for f .
We say that the class C is learnable in polynomial time if there is an algorithm
that uses the membership oracle and interpolates any f 2 C in polynomial time
in the number of variables n and the size of f . We say that C is efficiently
learnable in parallel if there is a parallel algorithm that uses the membership oracle
and interpolates any f 2 C in polylogarithmic time with polynomial number of
processors. In the parallel computation p processors can ask p membership queries
in one step.
3 Preliminaries
A formula is a rooted tree whose leaves are labeled with variables or constants from
some domain, and whose internal nodes, or gates, are labeled with elements from a
set of basis functions over that domain. A read-once formula is a formula for which
no variable appears on two different leaves. An arithmetic read-once formula over a
field K is a read-once formula over the basis of addition, subtraction, multiplication,
and division of field elements, whose leaves are labeled with variables or constants
from K.
In [BHH92] it is shown that a modified basis can be used to represent any
read-once formula. Let K be an arbitrary field. The modified basis
for arithmetic read-once formulas over K includes only two non-unary functions,
addition (+) and multiplication (\Theta). The unary functions in the basis are (ax
d) for every a; b; c; d 2 K such that ad \Gamma bc 6= 0. This requirement is to
prevent being identically 0 or differing by just a constant factor.
We can also assume that non-constant formulas over this modified basis do not
contain constants in their leaves. We represent such a unary function as f A , where
a b
c d
The restriction on a, b, c, and d is equivalent to saying the determinant of A
(denoted det(A)) is non-zero.
The value of a read-once formula on an assignment to its variables is determined
by evaluating the formula bottom up. This raises the issue of division by zero.
In [BHH92] this problem is handled by defining basis functions over the extended
domain K [ f1;ERRORg, where 1 represents 1=0 and ERROR represents 0=0.
For the special values we define our basis function as follows (assume x
and A is as above).
f A
( a
c
It is shown in [BHH92] that these definitions are designed so that the output of
the read-once formula is the same as it would be if the formula were first expanded
and simplified to be in the form p(x
p and q where gcd(p;
We say that a formula f is defined on the variable set V if all variables appearing
in f are members of V . Let g. We say a formula f depends on
variable x i if there are values x (0)
n and x (1)
i in K for which
and for which both those values of f are not ERROR. We call such an input vector
justifying assignment for x i .
Between any two gates or leaves ff and fi in an AROF, the relationships ancestor,
descendant, parent, and child refer to their relative position in the rooted tree. Let
that ff is a descendant of fi (or, equivalently, that fi is an ancestor of
ff). Let ff ! fi denote that ff is a proper descendant of fi (i.e., ff - fi but ff 6= fi).
For any pair of variables x i and x j that appear in a read-once formula, there is a
unique node farthest from the root that is an ancestor of both x i and x j , called
their lowest common ancestor, which we write as lca(x i ; x j ). We shall refer to the
type of lca(x to mean the basis function computed at that gate. We say that
a set W of variables has a common lca if there is a single node that is the lca of
every pair of variables in W .
We define the skeleton of a formula f to be the tree obtained by deleting any
unary gates in f (i.e. the skeleton describes the parenthesization of an expression
with the binary operations, but not the actual unary operations or embedded
constants).
We now list a basic property of unary functions f A that is proved in [BHH92].
1. The function f A is a bijection from K [ f1g to K [ f1g if and only if
is either a constant value from K[f1;ERRORg
or else is a constant value from K[f1g, except on one input value on which
it is ERROR.
2. The functions f A and f -A are equivalent for any - 6= 0.
3. Given any three distinct points
(a) If are on a line then there exists a unique function f A with
f A
(b) If are not on a line then there exists a unique function f A with
4. If functions f A and f B are equivalent and det (A); det (B) 6= 0, then there is
a constant - for which -A = B.
5. The functions (f A are equivalent.
6. If det(A) 6= 0, functions f
A and f A \Gamma1 are equivalent.
7. f A
A
A
A
A
(x).
4 Collapsibility of Operations
Whenever two non-unary gates of the same type in an AROF are separated by only
a unary gate it may be possible to collapse them together to a single non-unary
gate of the same type with higher arity. For ? 2 f+; \Thetag, a unary operation f A is
called ?-collapsible if
for some unary operations f B and f C . Intuitively, the above property means that
if the f A gate occurs between two non-unary ? gates then the two ? gates can be
"collapsed" into a single ? gate of higher arity, provided that new unary gates can
be applied to the inputs.
In [BHH92] it is explained that a unary gate f A is \Theta-collapsible if and only if A
is of the form ' a 0
or
and +-collapsible if and only if A is of the form
' a b
The following are equivalent definitions of ?-collapsible that will be used in this
paper.
Property 2 The following are equivalent
1. f A is +-collapsible.
2. f A
3. f A (1) = 1.
The following are equivalent
1. f A is \Theta-collapsible.
2. f A
3. ff A (1); f A (0)g = f0; 1g.
Proof: We prove the property by showing that 1 , 2 , 3. If f A is +-collapsible
then
' a b
and therefore (b=c). Since A is nonsingular a 6= 0 and c 6= 0 and
a=c
f A
d c
must
have
The result for \Theta-collapsible is left for the reader.2
In [BHH92], a three-way justifying assignment is defined as an assignment of
constant values to all but three variables in an AROF such that the resulting
formula depends on all of the three remaining variables. For the present results,
we require assignments that meet additional requirements, which are defined below.
For any two gates, ff and fi, with ff ! fi, define the ff-fi path as the sequence of
gate operations along the path in the tree from ff to fi (including the operations
of ff to fi at the endpoints of the path). Define a non-collapsing three-way justifying
assignment as a three-way justifying assignment with the following additional
property. For the unassigned variables x, y, and z, if lca(x; y) ! lca(x; z) and all
non-unary operations in the lca(x; y)-lca(x; z) path are of the same type ? (for
some then the function that results from the justifying assignment is
of the form
for some unary operations f A , f B , f C , f D and f E , where f C is not ?-collapsible.
Intuitively, this means that, after the justifying assignment, the two gates, lca(x; y)
and lca(x; z), cannot be collapsed-and thus the relationship lca(x; y) ! lca(x; z)
can still be detected in the resulting function.
Now, define a total non-collapsing three-way justifying assignment as a single
assignment of constant values to all variables in an AROF such that, for any three
variables, if all but those three are assigned to their respective constants then the
resulting assignment is non-collapsing three-way justifying.
5 Parallel Learning Algorithm
In this section, we present a parallel algorithm for learning AROFs. The algorithm
has three principal components: finding a total non-collapsing three-way justifying
assignment; determining the skeleton of the AROF; and, determining the unary
gates of the AROF.
The basic idea is to first construct a graph (that will later be referred to as the
LCAH graph) that contains information about the relative positions of the lcas of
all pairs of variables. This cannot be obtained quickly in parallel from justifying
assignments, because of the possibility that some of the important structure of an
AROF "collapses" under any given justifying assignment. However, we shall see
that any total non-collapsing justifying assignment is sufficient to determine the
entire structure of the AROF at once (modulo some polylog processing).
Once the LCAH graph has been constructed, the skeleton of the AROF can be
constructed by discarding some of the structure of the LCAH graph (a "garbage
collection" step). This is accomplished using some simple graph algorithms, as
well as a parallel prefix sum computation (which is NC 1 computable [LF80]).
Finally, once that skeleton is determined, the unary gates can be determined by
a recursive tree contraction method (using results from [B74]).
5.1 Finding a Total Non-Collapsing Three-Way Justifying
Assignment
In [BHH92], it is proven that, for any triple of variables x, y and z, by drawing
random values (independently) from a sufficiently large field, and assigning them
to the other variables in an AROF, a three-way justifying assignment for those
variables is obtained with high probability. In the parallel algorithm, a three-way
justifying assignment that is total non-collapsing is required. We show that, if the
size of the field K is at least O(n 2 ) then the same randomized procedure also yields
a total non-collapsing three-way justifying assignment with probability at least 1Therefore in time O(1) this step can be implemented.
We shall begin with some preliminary lemmas and then the precise statement
that we require will appear in Corollary 4.
Lemma 1: If A is not ?-collapsing then there
exists at most one value z (0) for z such that f C (y) j g(y; z (0) ) is ?-collapsing.
then by property 2 we have
where ff 2 Knf0g and fi 2 K. We substitute
f A is not +-collapsible, by property 2, we have f A Solving
the above system using property 1 we get
This shows that there is at most one value of z that makes f B (f A (y)
collapsible.
then by property 2 we have
where ff 2 Knf0g and fi 2 f+1; \Gamma1g. We substitute
f A is not \Theta-collapsible, by property 2, we have either f A (0) or f A (1) is not
in f0; 1g. Suppose f A (0) 62 f0; 1g and suppose f B (f A (0)z 0
are similar). Solving this gives
This shows that there is at most one value of z that makes f B (f A (y)z) \Theta-collapsible.2
Lemma 2: Let F be an AROF with
suppose that all non-unary operations in the lca(x 1 are of
the same type ? 2 f+; \Thetag. Let x (0)
n be independently uniformly randomly
chosen from S ' K, where m. Then the probability that x (0)
n is a
non-collapsing three-way justifying assignment is at least 1 \Gamma
Proof: Note that x (0)
n is not a non-collapsing three-way justifying assignment
if and only if it is not a justifying assignment or there exists a path between
the lcas of x 1 , x 2 and x 3 such that all non-unary operations are of the same type
and the path collapses under the assignment. From [BHH92], the probability of
the former condition is at most 2n+4
. We need to bound the probability of the
latter condition.
We have that F is of the form
E(fH k
may depend on variables from x
in addition to their marked arguments. Let -
E(y)
denote the above formulas (respectively) with x (0)
substituted for the variables
denote the degrees of C
as functions of x . By the assumption that F is in normal form, f H0 is not
?-collapsing. Therefore, by Lemma 1, there exists at most one value of C 1 for
which f H 1
?-collapsing. We can bound the probability of this value
occurring for C 1 . Since the degree of C 1 is d 1 , an application of Schwartz's result
in [Sch80] implies that probability that this value occurs for C 1 is at most d 1 =m.
Similarly, if f H 1
?-collapsing then Lemma 1 implies that
there exists at most one value of C 2 for which f H 2
collapsing, which occurs with probability at most d 2 =m, and so on. It follows that
the probability that
is ?-collapsing is at most (d
The result now follows by summing the two bounds. 2
Theorem 3: Let F be an AROF over K, and x (0)
n be chosen
uniformly from a set S ' K with m. Then the probability that x (0)
is a total non-collapsing three-way justifying assignment is at least 1 \Gamma 6n 2
Proof: First, note that, from Lemma 2, we can immediately infer that if
are drawn independently uniformly randomly from S ' K, where
then the probability that x (0)
n is a non-collapsing three-way justifying
assignment is at most
To obtain a better bound, consider each subformula C i that is an input to some
non-unary gate in the AROF. By results in [BHH92], there are at most two possible
values of C i that will result in some triple of variables with respect to which the
the assignment is not three-way justifying (the values are 0 and 1). Thus, as in
the proof of Lemma 2, the probability of one of these values arising for C i is at
most 2d
, where d is the degree of C i . Also, from Lemma 2, there is at most one
value of C i that will result in a collapsing assignment, and the probability of this
arising is at most d
. Thus, the probability of one of the two events above arising
is at most 3d
, and, since d - n, this is at most 3n
Since there are at most 2n such subformulas C i , the probability of any one of
them attaining one of the above values is at most 6n 2
. 2
The constant in the proof of theorem 3 can be improved to obtain probability
of
by using the following observation. Notice that we upper bounded the degree of
each subtree by n. In fact we can upper bound the degree of the leaves (there are
n leaves) by degree 1 since they are variables. Then we have another
subformulas of degrees . It is easy to show that d i - i +1
(simple induction on the number of nodes). Taking all this into account we obtain
the above bound.
By setting m - we obtain the following.
Corollary 4: Let F be an AROF over K, and x (0)
n be chosen
uniformly from a set S ' K with 2). Then the probability that
n is a total non-collapsing three-way justifying assignment is least 1
This Corollary implies that the expected time complexity of finding a total non-
collapsing three-way justifying assignment is O(1).
5.2 Determining the Skeleton of a Read-Once Formula in
Parallel
In this section, we assume that a total non-collapsing three-way justifying assignment
is given and show how to construct the skeleton with O(n 3 ) membership
queries in one parallel step followed by O(log n) steps of computation.
Firstly, suppose that, for a triple of variables x, y, and z, we wish to test whether
or not lca(x; y) ! lca(x; z). If op(x; y) 6= op(x; z) then this can be accomplished
by a direct application of the techniques in [BHH92], using the fact that we have
an assignment that is justifying with respect to variables x, y, and z. On the
other hand, if could be difficult to
detect with a mere justifying assignment because the justifying assignment might
collapse the relative structure between these three variables. If all the non-unary
operations in the lca(x; y)-lca(x; z) path are identical then, due to the fact that
we have a non-collapsing justifying assignment, we are guaranteed that the sub-structure
between the three variables does not collapse, and we can determine
that lca(x; y) ! lca(x; z) in O(1) time (again by directly applying techniques in
[BHH92]). This leaves the case where op(x; but the non-unary operations
in the lca(x; y)-lca(x; z) path are not all of the same type. In this case, the
techniques of [BHH92] might fail to determine that lca(x; y) ! lca(x; z) and report
them as equal. We shall overcome this problem at a later stage in our learning
algorithm, by making inferences based on hierarcical relationships with other vari-
ables. For the time being, we can, in time O(1) with one processor, compute the
following.
YES if lca(x; y) ! lca(x; z) and all non-unary operations
in the lca(x; y)-lca(x; z) path are of the same type;
YES or MAYBE if lca(x; y) ! lca(x; z) and op(x; but not
all non-unary operations in the lca(x; y)-lca(x; z)
path are of the same type;
MAYBE otherwise.
Note that if DESCENDANT(x; must be that lca(x; y) !
then it is possible that
and the non-unary operations on the
are not of the same type, or that lca(x; y) 6! lca(x; z).
To construct the extended skeleton of an AROF, we first construct its least
common ancestor hierarchy (LCAH) graph, which is defined as follows.
Definition: The least common ancestor hierarchy (LCAH) graph of an AROF
with n variables consists of
vertices, one corresponding to each (unordered) pair
of variables. For the distinct variables, x and y, denote the corresponding vertex
by xy or, equivalently, yx. Then, for distinct vertices xy and zw, the directed edge
present in the LCAH graph if and only if lca(x; y) - lca(z; w).
We shall prove that the following algorithm constructs the LCAH graph of an
AROF.
Algorithm CONSTRUCT-LCAH-GRAPH
1. in parallel for all distinct variables x; y; z do
if DESCENDANT(x;
insert edges xy ! xz and xy ! yz and xz ! yz and yz ! xz
2. in parallel for all distinct variables x;
if edges xy ! xw ! xz are present then
insert edge xy ! xz
3. in parallel for all distinct variables x; y; z do
if no edges between any of xy; xz; yz are present then
insert edges in each direction between every pair of xy; xz; yz
4. in parallel for all distinct variables x;
if edges xy ! xw ! zw present or edges xy ! yw ! zw present then
insert edge xy ! zw
Theorem 5: Algorithm CONSTRUCT-LCAH-GRAPH constructs the LCAH
graph of an AROF.
Proof: The proof follows from the following sequence of observations:
(i) For all distinct variables x, y and z for which lca(x; y) ! lca(x;
after executing steps 1 and 2 of the algorithm, the appropriate edges pertaining to
vertices xy, xz and yz (namely, xy ! xz, xy ! yz, xz ! yz and yz ! xz) are
present.
(ii) For all distinct variables x, y and z for which lca(x;
after executing step 3 of the algorithm, the appropriate edges pertaining to vertices
xy, xz and yz (namely, edges in both directions between every pair) are present.
(iii) For all distinct variables x, y, z and w, after executing step 4 of the algo-
rithm, the edge xy ! zw is present if and only if lca(x; y) - lca(z; w).2
It is straightforward to verify that algorithm CONSTRUCT-LCAH-GRAPH
can be implemented to run in O(log n) time on an EREW PRAM with O(n 4 )
processors. Moreover, the O(n 3 ) membership queries can be made initially in one
parallel step.
In an AROF, each non-unary gate corresponds to a biconnected component
(which is a clique) of its LCAH graph. Thus, to transform the LCAH graph into
the extended skeleton of the AROF, we simply "compress" each of its biconnected
components into a single vertex and then extract the underlying tree structure
of this graph (where the underlying tree structure of a graph is the tree whose
transitive closure is the graph 1 ).
This is accomplished using standard graph algorithm techniques, including a
parallel prefix sum computation ([LF80]). The details follow.
We first designate a "leader" vertex for each biconnected component. We then
record the individual variables that are descendants of each non-unary gate, and
then discard the other nodes in each biconnected component.
The algorithm below selects a leader from each connected component in an
LCAH graph. We assume that there is a total ordering OE on the vertices of the
LCAH graph (for example, the lexicographic ordering on the pair of indices of the
two variables corresponding to each vertex).
Algorithm LEADER
in parallel for all vertices xy OE zw do
if edges xy ! zw and zw ! xy are present then
mark xy with X
It is easy to prove the following.
Lemma executing algorithm LEADER, there is precisely one unmarked
node (namely, the largest in the OE ordering) in each biconnected component of the
LCAH graph.
After selecting a leader from each biconnected component of the LCAH graph,
we add n new nodes to this graph that correspond to the n variables. The edge
inserted if and only if the variable x is a descendant of lca(y; z). This is
accomplished by the following algorithm.
Algorithm LEAVES
in parallel for all distinct variables x;
insert edge x ! xy
if edge xy ! zw is present then
insert edge x ! zw
Lemma 7: After executing algorithm LEAVES, the edge x ! yz is present if
and only if variable x is a descendant of lca(y; z).
Both algorithms LEADER and LEAVES can be implemented in O(log n) time
with O(n 4 ) processors.
After these steps, the marked nodes are discarded from the augmented LCAH
graph (that contains
resulting in a graph with at most 2n \Gamma 1
vertices that is isomorphic to the extended skeleton of the AROF. This discarding
is accomplished by a standard technique involving the computation of prefix sums.
We first adopt the convention that the order OE extends to the augmented LCAH
graph as x 1 OE \Delta \Delta \Delta OE x n and x OE yz for any variables x, y and z. Then, for each
All edges are directed towards the root.
node v, set
ae 1 if v is unmarked
and compute the prefix sums
u-v
With algorithms for parallel prefix sum computation ([LF80]) this can be accomplished
in O(log(
processors.
The function oe is a bijection between the unmarked nodes of the augmented
LCAH graph and some S ' ng.
The following algorithm uses the values of this function to produce the extended
skeleton of the AROF.
Algorithm COMPRESS-AND-PRUNE
in parallel for all distinct vertices u; v do
if vertices u; v are both unmarked
and edge is in augmented LCAH graph then
insert edge oe(u) ! oe(v) in skeleton graph
in parallel for all distinct do
if edges are in skeleton graph then
remove edge from skeleton graph
The following is straightforward to prove.
Lemma 5: The "skeleton" graph that COMPRESS-AND-PRUNE produces
is isomorphic to the extended skeleton of the AROF, where the inputs x
correspond to the vertices of the graph.
5.3 Determining a Read-Once Formula from its Skeleton
Once the skeleton of an AROF is determined, what remains is to determine the
constants in its unary gates (note that the non-unary operations are easy to determine
using the techniques in [BHH92]). We show how to do this in O(log 2 n)
steps with O(n log n) processors. The main idea is to find a node that partitions
the skeleton into three parts whose sizes are all bounded by half of the size of the
skeleton. Then the unary gates are determined on each of the parts (in a recursive
manner), and the unary gates required to "assemble" the parts are computed.
The following lemma is an immediate consequence from a result in [B74].
Lemma 9 [B74]: For any formula F exists a non-unary gate of
type ? that "evenly" partitions it in the following sense. With a possible relabelling
of the indices of the variables,
and the number of variables in G(y; x
are all bounded above by d ne.
A minor technicality in the above lemma is that, since the skeleton is not necessarily
a binary tree, it may be necessary to "split" a non-binary gate into two
smaller gates.
It is straightforward to obtain the above decomposition of a skeleton in NC 1 .
Once this decomposition is obtained, the recursive algorithm for computing the
unary gates of the ROF follows from the following lemma.
Lemma 10: Let x (0)
n be a total non-collapsing justifying assignment for
the AROF F
(i) Given the skeleton of F and the subformulas G(y; x
possible to determine A, B and C, and,
thus, the entire structure of F steps with O(n log n) processors

(ii) Given the skeleton of F the problem of determining G(y; x
reducible to the problem of determining a ROF
given its skeleton.
Proof: For part (i), assume that the subformulas G(y; x
and I(x are given. Since x (0)
n is a justifying assignment, G(y; x (0)
l ) are all nonconstant unary functions, so
there exist nonsingular matrices A 0 , (which are easy to determine in O(log n)
parallel steps) such that
l
Also,
so the matrices A 0 can be determined in O(1) steps, [BHH92].
From this, the matrices A, B, C can be determined.
For part (ii), consider the problem of determining G(y; x
for some nonsingular A 00 . Therefore, if we fix x l to x (0)
l then we
have a reduction from the problem of determining G(fA 00 (y); x
Similarly, we have reductions from the problem of determining f B 00 (H(x
and f C 00 (I(x Since the matrices
can be absorbed into the processing of part (i) this is sufficient.2
By recursively applying Lemmas 9 and 10, we obtain a parallel algorithm to determine
an AROF given its skeleton and a total noncollapsing three-way justifying
assignment in O(log 2 n) steps. The processor count for this can be bounded by
O(n log n).



--R

Machine Learning
Learning Read-Once Formulas with Queries
When Won't Membership Queries Help?
The parallel evaluation of general arithmetic expressions.
Learning arithmetic read-once formulas
On the exact learning of formulas in par- allel
Learning boolean read-once formulas with arbitrary symmetric and constant fan-in gates
Asking Questions to Minimize Errors.
An Algorithm to Learn Read-Once Threshold Formulas
A deterministic algorithm for sparse multivariate polynomial interpolation.
On the Decidability of Sparse Univariate Polynomial Interpolation.
Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions
Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields.
Interpolation of sparse rational functions without knowing bounds on the exponent.

Learning read-once formulas over fields and extended bases
Testing polynomials that are easy to com- pute
Parallel prefix computation.
Learning Quickly When Irrelevant Attributes Abound: A New Linear Threshold Algorithm
Randomized approximation and interpolation of sparse polynomials.
On the complexity of learning from counterexamples and membership queries.
Interpolation and approximation of sparse multivariate polynomials over GF(2).
Learning sparse multivariate polynomials over a field with queries and counterexamples.
Fast polynomial algorithms for verification of polynomial identities.
A theory of the learnable.
Learning in parallel
--TR

--CTR
Amir Shpilka, Interpolation of depth-3 arithmetic circuits with two multiplication gates, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
read-once formula;learning theory;parallel algorithm