Reconstructing Algebraic Functions from Mixed Data.
We consider a variant of the traditional task of explicitly reconstructing algebraic functions from black box representations. In the traditional setting for such problems, one is given access to an unknown function f that is represented by a black box, or an oracle, which can be queried for the value of f at any input. Given a guarantee that this unknown function f is some nice algebraic function, say a polynomial in its input of degree bound d, the goal of the reconstruction problem is to explicitly determine the coefficients of the unknown polynomial. All work on polynomial interpolation, especially sparse ones, are or may be presented in such a setting. The work of Kaltofen and Trager [Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators, in Proc. 29th Ann. IEEE Symp. on Foundations of Computer Science, 1988, pp. 296--305], for instance, highlights the utility of this setting, by performing numerous manipulations on polynomials presented as black boxes.The variant considered in this paper differs from the traditional setting in that our black boxes represent several algebraic functions f1,...,fk, where at each input x, the box arbitrarily chooses a subset of f1(x),...,fk(x) to output and we do not know which subset it outputs. We show how to reconstruct the functions f1,...,fk from the black box, provided the black box outputs according to these functions "often." This allows us to group the sample points into sets, such that for each set, all outputs to points in the set are from the same algebraic function. Our methods are robust in the presence of a small fraction of arbitrary errors in the black box.Our model and techniques can be applied in the areas of computer vision, machine learning, curve fitting and polynomial approximation, self-correcting programs, and bivariate polynomial factorization.
Introduction
. Suppose you are given a large set of points in the plane and
are told that an overwhelming majority of these points lie on one of k different
algebraic curves of some specified degree bound D (but you are not told anything
else about the curves). Given the parameters k and D, your task is to determine or
"reconstruct" these algebraic curves, or alternatively, to group the points into sets,
each of which is on the same degree D curve. Related versions of this problem may also
be of interest, such as extensions to higher dimensions, and a setting where instead of
the points being given in advance, one is allowed to make queries of the form "what
is the value of one of the curves at point x?" (the answer to such a query will not
specify which of the k curves was used to compute the value).
Solutions to this fundamental problem have applications to:
Princeton University, Supported by Dept. of Navy Grant #N00014-85-C-0456, by NSF PYI
grant CCR-9057486 and a grant from MITL.
y Princeton University. Part of this research was done while at Matsushita Information Technology
Labs.
z Cornell University. Part of this research was done while at Hebrew University and Princeton
University. This research is supported by DIMACS, NSF-STC88-09648, ONR Young Investigator
Award N00014-93-1-0590 and grant No. 92-00226 from the United States - Israel Binational Science
Foundation (BSF).
x MIT Laboratory for Computer Science, Cambridge, MA 02139. Email: madhu@lcs.mit.edu.
Part of this work was done when this author was at U.C. Berkeley and IBM's Thomas J. Watson
Research Center, supported in part by NSF Grant No. CCR 88-96202.
ffl the grouping problem in computer vision
ffl computational learning theory
ffl curve fitting over discrete domains
ffl simple algorithms for polynomial factorization
self-correcting programs.
Computer Vision. Consider a computer vision system for a robot that picks parts
out of a bin. The input to the system contains an intensity map of the scene. The
robot can distinguish between the parts by extracting edges from the image. Current
edge detection algorithms use discretised differential operators to extract edges (e.g.
[30][10]). These algorithms produce output consisting of a bit map, where for every
image point (x; y), the bit value of the point, e(x; y), is set to 1 if and only if this point
lies on an edge. For many vision applications it is then desired to connect between
neighboring points to achieve a more compact representation of the edge map. This
problem, known as "the grouping problem", is complicated by the fact that the parts
are cluttered, they may be nonconvex and they may contain holes. No polynomial
time algorithm has been found for this problem.
Under the assumption that the edges of the parts are given by piecewise algebraic
curves, and that the edge detection process produces results which are free of precision
error, our algorithm transforms edge maps into piecewise polynomial curves in
polynomial time. The second assumption is unrealistic in real computer vision appli-
cations. However, we feel that it suggests an interesting approach which should be
studied further.
Computational Learning Theory. Our mechanism can be used to extend some
well-known results on learning boolean functions to the setting of learning real-valued
functions. Here is a specific instance of such a situation: In the study of economics, the
price-demand curve is often considered to be well-described by an algebraic function
(e.g. However, it is also the case that this curve
may change [23]. In particular, there may be several unknown price-demand curves
which apply in various situations - one may correspond to the behavior found when
the country is at war, a second may apply after a stock market crash, and a third
behavior may be found after a change in the tax structure. Some of the factors
that determine which curve applies may be obvious, but others may occur because
of more subtle reasons. The task of learning the price-demand relationship may be
decomposed into the two subtasks of first determining the unknown curves, and then
learning what determines the move from one curve to another. Our algorithm gives
a solution for the first task.
We consider the Valiant model of PAC learning [36], in which a concept is learnable if
there is an efficient algorithm that is able to find a good approximation to the concept
on the basis of sample data. In general, our results imply that any function on input
x and boolean attributes (y select f i from a set of
polynomial functions f and then computes and outputs f i (x) can be learned,
as long as the selector function can be learned.
For example, a polynomial-valued decision list given by a list of terms (conjuncts
of literals), (D a list of univariate
polynomials, in a real variable x, represents a real valued function f as
follows:
where i is the least index such that D i (y
If the terms are restricted to being conjunctions of at most c literals, we call it a
polynomial-valued c-decision list. This is an extension of the boolean decision list
model defined by Rivest in [32], where the polynomials f i are restricted to being the
constants 0 or 1.
In [32], Rivest shows that the class of boolean c-decision lists is learnable in polynomial
time. Using our techniques, in combination with Rivest's algorithm, we can extend
this result to show that the class of polynomial-valued c-decision lists can be learned in
polynomial time. The only technical point that needs to be made is as follows: Rivest
gives an algorithm for producing a decision list that is consistent with the random
examples and then argues using an Occam argument (see Blumer et. al. [8]) that
any hypothesis that is consistent with the labels of the random examples is a good
hypothesis (i.e. computes a function that is usually equal to the target function). Our
techniques in combination with Rivest's algorithm yield a consistent hypothesis, but
since our hypothesis is not a boolean function, we must use the work of Haussler [22]
to see that a consistent hypothesis is a good hypothesis.
Independent of our work, Blum and Chalasani [6] also consider a model of learning
from examples where the examples may be classified according to one of several different
concepts. In their model an adversary controls the decision of which concept
would be used to classify the next example. Under this model they study the task
of learning boolean-valued concepts such as k-term DNF's and probabilistic decision
lists.
Curve Fitting Problems over Discrete Domains. A typical curve fitting problem
takes the following form: Given a set of points on the plane,
give a simple curve that "fits" the given points. Depending on the exact specification
of the "fit" the problem takes on different flavors: for instance, if the curve is to pass
close to all the points, then this becomes a uniform approximation problem (see text
by Rivlin [33]), while if the curve is supposed to pass through most of the points, then
it resembles problems from coding theory. Here, we consider a problem that unifies
the above two instances over discrete domains. For example, given a set of m points,
with integer coordinates, we show in Subsection 4.1 how to find a polynomial with
integer coefficients that is \Delta-close to all but an ffl fraction of the points (if such a
polynomial exists), where ffl need only be less than 1=2 (provided is m is larger than
(4\Delta+1)d
Reducing Bivariate Factoring to Univariate Factoring. In [4] Berlekamp gave a
randomized polynomial time algorithm for factoring univariate polynomials over finite
fields. Kaltofen [24] and Grigoriev and Chistov [18] show that the problem of bivariate
factoring can also be solved in polynomial time by a reduction to univariate factoring,
using somewhat deep methods from algebra. Our techniques in Subsection 4.2 give
a simple method to reduce the problem of factoring bivariate polynomials to that of
factoring univariate polynomials over finite fields in the special case when the bivariate
polynomial splits into factors which are monic and of constant degree in one of the
variables. Though the results are not new, nor as strong as existing results, the
methods are much simpler than those used to obtain the previously known results.
Self-Correcting Programs . One motivation for this work comes from the area of
self-correcting programs introduced independently in [7][28]. For many functions, one
can take programs that are known to be correct on most inputs and apply a simple
transformation to produce a program that is correct with high probability on each
input. But, how bad can a program be, and still allow for such a transformation?
There is previous work addressing this question when the functions in question are
polynomials (see for example [28],[13],[14]). When the program is not known to be
correct on most inputs, the definition of self-correction needs to be modified, since the
program can toggle between two seemingly correct functions. Our methods give self-
correctors that work when the error of the program is such that it answers according
to one of a small number of other algebraic functions. An algebraic decision tree may
contain a small number of branches, in which all subtrees are intended to compute the
same function but are computed separately for purposes of efficiency. The algebraic
decision tree program might err in some of the subtrees and compute the wrong
algebraic function. Our self-correctors output a small number of candidates for the
correct function.
One particular situation where this is useful is in the computation of the permanent
of a matrix, over a finite field. Results of Cai and Hemachandra ([9]), when used in
combination with our results, imply that if there is an efficient program which computes
the permanent correctly on a non-negligible fraction of the input and computes
one of a small number of other algebraic functions on the rest of the inputs, then the
permanent can be computed efficiently everywhere.
1.1. The k-Algebraic Black Box Model. We consider the following black-box
reconstruction problem, which is general enough to model all of the aforementioned
problems. We think of the black-box as "containing" k functions, f
f i is an "algebraically well-behaved" function. For instance, each f i could be a polynomial
of degree at most d, and on every input x the black box outputs f i (x) for
some (Here and throughout this paper, the notation [k] stands for the set of
integers Relating to the problem discussed in the first paragraph of the
introduction, this corresponds to the case where for every value of an x-coordinate
there is at least one point that has that value. We now present this definition formally,
starting with the standard black box model
Definition 1.1. A black box B is an oracle representing a function from a finite
domain D to a range R.
There are two kinds of domains that will be of interest to us. One is a finite subset H
of a (potentially infinite) field F . The second is an n-dimensional vector space over a
finite field F . In both cases the range will be the field F .
Previous research on black box reconstruction focused on the following: Assuming that
B is one of a special class of functions (for example, that B is a degree d polynomial),
determine an explicit representation of B. In our model, there may be more than one
output that is valid for each input. More specifically:
Definition 1.2. A black box B mapping a finite subset H of a field F to F is a
(k; d)-polynomial black box if there exist polynomials f of degree
at most d such that for every input x 2 H, there exists kg, such that
In such a case, we say that the functions f describe the black
box B.
Our first black box reconstruction problem is:
Given a (k; d)-polynomial black box B, find a set of functions f
that describe B.
The definition of a (k; d)-polynomial black box can be generalized to situations involving
noise as follows:
Definition 1.3. For ffl 2 [0; 1] and for a finite subset H of a field F , a black
is an ffl-noisy (k; d)-polynomial black box if there exist polynomials f
of degree at most d and a set S ae H, with jSj - (1 \Gamma ffl)jHj, such that for
every input x 2 S, there exists kg such that In such a case,
the functions f are said to describe B.
The notion of the reconstruction problem generalizes to the noisy case in the obvious
way. We now attempt to generalize the problem to allow the black box to compute
other algebraic functions, such as
x etc. This part is somewhat more
technical, so we introduce some new terminology:
Definition 1.4. For positive integers d x ; d y and indeterminates x; y, the f(d x ; x); (d y ; y)g-
weighted degree of a monomial x i y j is id x +jd y . The f(d x ; x); (d y ; y)g-weighted degree
of a polynomial Q(x; y) is the maximum over all monomials in Q (i.e., the monomials
with non-zero coefficients in Q) of their f(d x ; x); (d y ; y)g-weighted degree.
We now introduce the notion of an algebraic box and show how it relates to the earlier
notion of a polynomial black box.
Definition 1.5. For a finite subset H of a field F , A black
a (k; d)-algebraic black box if there exists a polynomial Q(x; y) of f(1; x); (d; y)g-
weighted degree at most kd, such that for every input x 2 H, the output y of the black
box satisfies Q(x; In such a case, we say that the polynomial Q describes B.
For example, if
x, the polynomial Q(x; satisfies the requirement
of the definition and describes B. The f(1; x); (d; y)g-weighted degree of Q is 2d.
Proposition 1.6. If B is a (k; d)-polynomial black box then B is also a (k; d)-
algebraic black box.
Proof. Let B be a (k; d)-polynomial black box and let f it. Then the
polynomial
has f(1; x); (d; y)g-weighted
degree at most kd.
The (k; d)-algebraic black box reconstruction problem is:
Given a (k; d)-algebraic box B, find the polynomialQ of f(1; x); (d; y)g-
weighted degree at most kd which describes it.
The definition and proposition can be extended easily to the ffl-noisy case.
All the above definitions generalize to a case where the input is an n-dimensional
vector over F and the black box is computing n-variate functions. In particular, we
Definition 1.7. For a finite field F , a n-variate black F is a (k; d)-
polynomial black box if there exist polynomials f of total degree
at most d such that for every input
that
Definition 1.8. For a finite field F , An n-variate black F is a (k; d)-
algebraic black box if there exists a polynomial Q(x
weighted degree at most kd such that for every input , the output y
of the black box satisfies Q(x
Again the reconstruction problems are defined correspondingly. In this paper we
attempt to solve all such reconstruction problems. Notice that this problem is not
well-defined if there exist multiple solutions, say Q and ~
Q, such that both Q and ~
describe the black box. Much of the work is done in establishing conditions under
which any ~
Q that describes the black box gives a meaningful answer.
1.2. Previous Work and Our Results. The setting where the black box represents
a single polynomial or rational function, without noise, is the classic interpolation
problem and is well studied. Efficient algorithms for sparse multivariate polynomial
interpolation are given by Zippel [40, 41], Grigoriev, Karpinski and Singer [21]
and Borodin and Tiwari [3], and for sparse rational functions by Grigoriev, Karpinski
and Singer [20].
The case where the black box represents a single function with some noise has also
been studied previously. Welch and Berlekamp [39, 5] (see also [14]) show how to
reconstruct a univariate polynomial from a ( 1
and Coppersmith [11], Gemmell, Lipton, Rubinfeld, Sudan and Wigderson [13] and
Gemmell and Sudan [14] show how to do the same for multivariate polynomials. All
the above mentioned results require, however, that the field size be at least polynomially
large in d
. The conditions are required to ensure that there is a unique degree d
polynomial describing the black box on 1=2+ ffi fraction of the inputs. Reconstructing
functions from a black box representing more than one function, or when the function
it represents is not guaranteed to be unique, seems to be a relatively unexplored
subject. The works of Goldreich and Levin [15] and Kushilevitz and Mansour [26] are
the only exceptions we know of. Both papers study the reconstruction of n-variate
linear functions (i.e., homogenous polynomials of degree 1) from a
box over GF(2). In this case, there can be up to O( 1
representing the
black box and they reconstruct all such polynomials.
The main result in this paper is an algorithm for reconstructing algebraic functions
describing noisy algebraic black boxes, which works when the black box satisfies certain
conditions. To see why the result needs to have some conditions on the black box,
consider the following example: Suppose the black box is described by the polynomial
suppose for every x the black box always outputs a y
from the unit circle (and never according to the line x clearly the
reconstruction algorithm has no information to reconstruct the line x 1. The
condition imposed on the black box essentially addresses this issue. We describe the
result for univariate ffl-noisy (k; d)-polynomial black boxes. We present a randomized
algorithm which takes as input a parameter p ? ffl and with high probability outputs
a list of all polynomials f i which describe the black box on more than p fraction of the
condition amounts to saying that the black box
must output according to f i sufficiently often.) The running time of the algorithm is
a polynomial in k; d and 1
(p\Gammaffl) . This result is presented along with generalizations to
univariate noisy algebraic black boxes in Section 2.
To reconstruct a univariate polynomial, we sample the black box on a small set of
inputs and construct a bivariate polynomial ~
Q(x; y) which is zero at all the sample
points. Then we use bivariate polynomial factorization to find a factor of the form
our candidate for output. We show that if
the number of points (x; y) such that y = f(x) is large in the sample we chose, then
has to be a factor of any ~
Q which all the sample points satisfy.
Our results do not generalize immediately to multivariate polynomials. Among other
factors, one problem is that an n-variate polynomial of degree d has
d
which is exponential in n (or d). This seems to make the problem inherently hard to
solve in time polynomial in n and d. However we bypass this, once again using the idea
of black boxes. Instead of trying to reconstruct the multivariate polynomial explicitly
(i.e., by determining all its coefficients), we allow the reconstruction algorithm to
reconstruct the polynomial implicitly, i.e., by constructing a black box which computes
the multivariate polynomial. If the polynomial turns out to be sparse then we can
now use any sparse interpolation algorithm from [3, 20, 21, 40] to reconstruct an
explicit representation of the polynomials in time polynomial in n, d and the number
of non-zero coefficients. On the other hand, by using the techniques of [25] we can
also continue to manipulate the black boxes as they are for whatever purposes 1 .
We now describe our result for reconstructing multivariate polynomials. We present a
randomized algorithm which takes as input a parameter p and with high probability
reconstructs probabilistic black boxes for all the polynomials f describing a
noisy (k; d)-black box over a finite field F , provided the noisy (k; d)-black black box
satisfies the following conditions: (1) Every polynomial is represented on at least a
p-fraction of the inputs (i.e. for every i, Pr -
p). (2) The finite
field F over which the black box works is sufficiently large (jF j should be polynomially
large in k; d; 1
). The running time of the algorithm is polynomial in k; d and 1
The main technique employed here is a randomized reduction from the multivariate
to the univariate case. We note that the solution obtained here for the multivariate
case differs in several aspects from the solution for the univariate case. First, this
algorithm does not extend to the case of finite subsets of infinite fields. Second, it
needs to make sure that all the polynomials are well-respresented in the black box.
The latter aspect is a significant weakness and getting around this is an open question.
Subsequent work. One of the main questions left open by this paper is the problem
of reconstructing all degree d polynomials that agree with an arbitrary black box
on ffl fraction of the inputs. Some recent work has addressed this question. Goldreich,
Rubinfeld and Sudan [16] give an algorithm to (explicitly) reconstruct all n-variate
degree d polynomials agreeing with a black box over F on ffl fraction of the inputs,
runs in time O((n; 1
which is exponential
in d. Their algorithm generalizes the earlier mentioned solution of Goldreich
and Levin [15]. For the case of univariate polynomials, Sudan [35], has given a polynomial
time algorithm which can find all degree d polynomials agreeing with a black
box on ffl fraction of the domain, provided
j. The main contribution in
[35] is a simple observation which shows that m input/output pairs from any black
box can be thought of as the output of a (1; O(
m))-algebraic black box. Using this
observation, Lemma 2.10 of this paper is applied to reconstruct all polynomials of low
1 The idea of manipulating multivariate polynomials and rational functions represented by black
boxes was proposed by Kaltofen and Trager in [25]. They show that it is possible to factor and
compute g.c.d.'s for polynomials given by such a representation and to separate the numerator from
the denominator of rational functions given by such a representation.
degree which describe the black box on ffl-fraction of the inputs. Finding a similar
solution for the multivariate cases remains open (some cases are addressed by [35],
but the problem is not completely resolved). A second question that is left open is
the task of solving the (k; d)-polynomial black box problem over the reals, where the
points are not provided to infinite precision. This is the true problem underlying the
application to computer vision. While the ideas in this paper do not immediately apply
to this question, some variants (in particular, the variant employed in [35]) seem
promising and deserve to be investigated further.
In other related work, Rubinfeld and Zippel [34] have employed the black box reconstruction
problem and build on the techniques presented in this paper to present a
modular approach to the polynomial factorization problem. While the application
presented in this paper (in Section 4.2) is to a restricted subclass of the bivariate factorization
problem, the work of [34] finds an application to the general multivariate
factorization problem.
1.3. Organization . The rest of this paper is organized as follows. In Section 2,
we describe our results for univariate polynomials, rational functions and other algebraic
functions. In Section 3, we consider extensions of the reconstruction problem
to the case of multivariate polynomials. Finally, in Section 4, we describe several
applications of our work.
2. Univariate Black Boxes. In this section we consider the univariate reconstruction
problem for (noisy) (k; d)-polynomial and algebraic black boxes. We describe
our general format of our results with the example of a (k; d)-polynomial black box
described by f We present a solution in the form of an algorithm which
takes of the black box and attempts
to reconstruct the polynomials f k from this set of input/output pairs. In order
to reconstruct a small set of polynomials which includes a specific polynomial
the algorithm (obviously) needs to find sufficiently many points
are needed). We present complementary bounds,
showing that if the number of points on f i is sufficiently large, then the output is
guaranteed to include f i . We then show how some simple sampling of the black box
(either by exhaustively sampling all points from the domain H or by picking a random
sample of x j 's chosen independently and uniformly at random from H) yields
a collection of input/output pairs which satisfies the required condition, provided H
is large enough and the fraction of inputs on which B's output is described by f i is
large enough.
2.1. An Intermediate Model. As a first step towards solving the algebraic
reconstruction problem, we consider the case where the black box outputs all of
on any input x. We refer to this as a (k; d)-total polynomial black
box. These are output in arbitrary order, which is not necessarily the same for each
x. We further assume that there are no errors in the output. Thus the reconstruction
problem we wish to solve may be stated formally as:
Given: Positive integers k and d, a field F and a black box
with the property that there exist polynomials f of degree at
most d over F , such that for every x 2 F , the multisets fB 1
are identical.
We reduce the problem of extracting the polynomials to that of bivariate polynomial
factorization. The main idea underlying this reduction is the following: On input
x if the (k; d)-total polynomial black box outputs fy we know that 8j 2
Therefore, each input/output pair (x; y
the black box satisfies the relation:
Y
Our aim will be to construct a related polynomial which will enable us to recover the
Consider the functions oe defined as
Y
(these are the primitive symmetric functions of
Observe that oe j (x) can be evaluated at any input x using the given (k; d)-total polynomial
black box, using the identity
Y
Furthermore this computation can be performed in time in O(k log k log log using
a fast Fourier transform (see survey article by von zur Gathen [12], pages 320-321).
Observe further that oe j is a polynomial of degree at most jd. Hence evaluating it at
points suffices to find all the coefficients of this polynomial (if the black box
outputs every f i (x) for every x).
Now consider the following bivariate polynomial, in x and a new indeterminate y:
From the explicit representation of the oe i 's, we can also compute an explicit representation
of Q. But now notice that Q can equivalently be written as:
Y
(The equivalence follows from the definition of the oe j 's.) Therefore, to recover the
we have to do is find the factors of the bivariate polynomial Q. Bivariate
factorization can be done efficiently over the rationals [18, 24, 29] and can be done
efficiently (probabilistically) over finite fields [17, 24].
We now summarize our algorithm. The input to the algorithm is kd
elements from the the field F , and a set fy for every
representing the output of the black box B on input x j .
1. Evaluate oe j
2. Interpolate for the coefficients of oe j (x) and let oe j;l be the coefficient of x l in
oe j .
3. Let Q(x; y) be the polynomial
4. Factor Q into its irreducible factors. This will yield Q(x;
5. Output the polynomials
The arguments leading to this algorithm prove its correctness and we have the following
lemma.
Lemma 2.1. Let f(x
j=1 be the input/output pairs of a (k; d) total
polynomial black box B over a field F on kd inputs. Then there exists
an randomized algorithm whose running time is polynomial in k; d which explicitly
reconstructs the set of polynomials ff which describe B.
Since the only condition on the x j 's is that they be distinct, it is easy to get a
total polynomial reconstruction algorithm from the above lemma and thus we get the
following theorem.
Theorem 2.2. Let f be degree d polynomials over Q (the rationals) or a
finite field F of cardinality at least kd + 1. Given a black box B which on input x
outputs the multiset ff 1 arbitrary order), there exists an algorithm
which queries the black box on kd distinct inputs and reconstructs the polynomials
that describe the black box. The algorithm is deterministic when the polynomials are
over Q and probabilistic when the polynomials are over some finite field.
2.2. (k; d)-polynomial black boxes. We now build on the methods of the
previous section to reconstruct information from a (k; d)-polynomial black box which
outputs the value of one of k univariate polynomials f on every input. Our
method extends immediately to two more general cases:
1. (k; d)-algebraic black boxes.
2. Noisy (polynomial and algebraic) black boxes.
The generalizations are dealt with in the next section.
The problem we wish to solve is formally stated as:
Given: Positive integers k and d, a field F , a finite set H ' F and a black box
with the property that there exist polynomials f of degree at most
d over F , such that for every x (x)g.
Our solution for this problem is based on the solution of the previous subsection.
The critical observation is that the polynomial Q produced by the algorithm of the
previous section always satisfied the property Q(x; input x to the
black box and where y is any element of the output set of the black box on input x.
We will try to construct a polynomial Q in two variables as in the previous section,
satisfying the property that if y = B(x) is the output of the black box on input x,
then Q(x; However, we will not be able to construct the polynomials oe i (x) as
in the previous case. Hence, we will abandon that part of the algorithm and directly
try to find any polynomial ~
Q such that ~
on all the sampled points. We
will then use the factors of this polynomial to determine the f i 's as in the previous
section. Thus our algorithm is summarized as follows:
The input to the algorithm is m distinct pairs of elements
1. Interpolate to find a set of coefficients ~
q lj of the polynomial
~
dl
~
that satisfies ~
2. Factor the polynomial ~
Q and if it has any factors of the form (y \Gamma g(x)),
output g as a candidate polynomial.
Notes: The important step above is Step 1 which involves finding a non-trivial
solution to a homogenous linear system. First we need to make sure this system has
at least one solution. This is easy since Q(x;
is such a solution.
However the solution in such a step need not necessarily be unique and we will simply
find any solution to this system and show that it suffices, under certain conditions,
for Step 2. In what follows, we shall examine the conditions under which the output
will include a certain polynomial f i .
Lemma 2.3. For a set f(x distinct pairs from F \Theta F , if ~
Q is a
bivariate polynomial of f(1; x); (d; y)g-weighted degree kd satisfying
and f is a univariate polynomial of degree d satisfying
then the polynomial (y \Gamma f(x)) divides the polynomial ~
Proof. g. Notice that for distinct
the pairs are not distinct.
Consider the univariate polynomial ~
Q(x; f(x)). For all indices j 2 S we
have that ~
is a polynomial of degree at most kd in x.
Hence if ~
is zero at jSj ? kd places, then it must be identically zero, implying that
The lemma above guarantees that under certain circumstances, the factors of ~
do give useful information about the f i 's. The effect is summarized in the following
lemma.
Lemma 2.4. Let f(x distinct pairs of elements which are
the input/output pairs of a (k; d)-polynomial black box B described by polynomials
. If there exists an i 2 [k] such that jfjjy then a set of
at most k polynomials fg that includes f i can be found in time polynomial in
m, k and d.
Remark: Notice that Lemma 2.4 is a strict strengthening of Lemma 2.1.
To finish the analysis of the algorithm we need to determine how to sample the black
so as to get enough points according to f i . Let p i
be the confidence parameter. Let
). The strategy for
picking the points f(x 1 depends on jHj. If jHj - 2
pick m elements independently and uniformly at random
from H. Lemma A.1 in the appendix (shown using a simple combination of Chernoff
bounds and the "birthday problem analysis") shows that the sampled points are all
distinct and satisfy with probability at least 1 \Gamma ffi . Thus
in this case we will use f(x as the input to the algorithm
described above. If on the other hand jHj is not large enough, then we will simply
sample every point in H (i.e., the input set will be f(x; B(x))jx 2 Hg) implying in
particular that and in this case the algorithm described above will include f i
as part of its output provided Notice that in both cases the running time
of the algorithm is polynomial in M , which is in turn bounded by some polynomial
in k; d; 1
. Furthermore, by choosing and a threshold parameter p and
running the algorithm above with confidence parameter ffi 0 , we find that the algorithm
above recovers, with confidence p. The
running time is still a polynomial in k; d; 1
. This yields the following theorem.
Theorem 2.5. Let B be a (k; d)-polynomial black box, mapping a finite domain H
to a field F , described by polynomials f . For
There exists an algorithm which takes as input a confidence parameter
and a threshold p ? 0, runs in time poly(k; d; 1
makes calls to the black box
B and with probability at least reconstructs a list of at most k polynomials which
includes all polynomials f i such that
2.3. (k; d)-algebraic black boxes. The algorithm of Section 2.2 extends immediately
to the case of algebraic black boxes. Here, by definition, the input/output
pair of the black box, (x; y), satisfies an algebraic relation of the form Q(x;
We can attempt to find a polynomial ~
all the sampled
points by interpolation (Step 3 in the algorithm of Section 2.2).
As in the previous section, it will not be possible to guarantee that the output we
produce will be exactly Q. For instance, if Q(x; all the
points actually come from the unit circle, then the algorithm has no information to
point to the line x+y Thus, as in the previous section, we will only attempt to
find those parts of the curve that describe significant portions of output of the black
box. More precisely, if Q(x; y) factors into irreducible factors
and we know that many points satisfy, say, Q 1 then we would like Q 1 to
be one of the outputs of the algorithm.
The proof that this is indeed the case is slightly more complicated than in the previous
subsection. We will use a version of Bezout's theorem ([38], Theorem 3.1). Essentially,
Bezout's theorem states that two algebraic curves in the plane cannot intersect in
infinitely many points, unless they are identical. The theorem gives an explicit bound
on the number of points where two curves of degree d 1 and d 2 may meet. Bezout's
bound is slightly weaker than the one we wish to prove for the case of (k; d)-algebraic
black boxes, so we prove our lemma from first principles.
Before going on to the next lemma we review a couple of standard definitions from
algebra (cf. [38]).
Definition 2.6. Given univariate polynomials P
be the (d 1
given as follows:
The resultant of the polynomials P and Q, denoted Res(P; Q) is the determinant of
Q). For multivariate polynomials P
resultant with respect to y is defined similarly by viewing polynomials in y
with coefficients from the ring of polynomials in x We define the matrix
M y (P; Q) as above and its determinant is the resultant Res y
Lemma 2.7. For a set of points with the x j 's being distinct,
if ~
Q(x; y) and Q 1 (x; y) are polynomials of f(1; x); (d; y)g-weighted degree at most kd
respectively, satisfying the properties: (1) 8
d, then the polynomials Q 1 (x; y) and ~
share a
non-constant common factor.
Proof. Consider the resultant R y (x) of the polynomials ~
Q(x; y) and Q 1 (x; y) with
respect to y. Observe that the resultant is a polynomial in x. The following claim
bounds the degree of this polynomial.
Claim 2.8. R y (x) is a polynomial of degree at most k 1 kd.
Proof. The determinant of the matrix M y ( ~
where - ranges over all permutations from [k
sign(-) denotes the sign of the permutation. We will examine every
permutation show that the degree of the
(viewed as a polynomial in x) is at most
This will suffice to show that the determinant is a polynomial
of degree at most kk 1 d.
the degree of the entry (M y ( ~
by the definition of the resultant, d ij - (i
(Here we consider the polynomial 0 as having
degree \Gamma1.) Thus the degree of the term
given by
k1
d i-(i)
k1
This concludes the proof.
It is well-known that the resultant of two polynomials is zero iff the polynomials
share a common factor (cf. [38], Chapter 1, Theorem 9.3). We will show that R y (x)
is identically zero and this will suffice to prove the lemma. We show this part in
the next claim by showing that R y (x) has more zeroes than the upper bound on its
degree.
2.9. For every j such that ~
R y
Proof. Fix x j and consider the polynomials ~
the resultant of the polynomials
~
q(y) and q 1 (y). Now we know that ~
implying that
is a common factor of ~ q and q 1 . Therefore the resultant of ~ q
and q 1 must be zero, implying R y
Since the above holds for any factor Q i of Q, we have:
Lemma 2.10. Let B be a (k; d)-algebraic black box described by a bivariate polynomial
Q with no repeated non-constant factors. Let Q l be the irreducible factors of Q
of f(1; x); (d; y)g-weighted degree k 1 Given m pairs of elements
which are the input/output pairs of B on m distinct inputs,
if there exists an i 2 [k] such that jfjjQ i then a set of at most k
polynomials f ~
that includes Q i can be found in time polynomial in m, k
and d.
Remark: For a set of pairs
is a strengthening of Lemma 2.4. Unfortunately, the proof as shown above does not
extend to the case of where the pairs are distinct, but the x j are not. Due to this
limitation, Lemma 2.10 does not even cover the case of Lemma 2.1.
Once again, using a sampling method similar to that used for Theorem 2.5, we get
the following theorem.
Theorem 2.11. Let B be a (k; d)-algebraic black box described by a polynomial Q
with distinct irreducible factors l such that the f(1; x); (d; y)g-weighted degree
of Q is at most kd and of Q i is at most k i d. Further, let
There exists a randomized algorithm which takes as input a confidence parameter
and a threshold p ? 0, runs in time poly(k; d; 1
makes calls to the black box B
and with probability at least reconstructs a list of at most k bivariate polynomials
which includes every polynomial Q i such that
2.4. ffl-noisy black boxes. Finally we extend the reconstruction algorithms of
the previous section to the case when the black boxes are allowed to output noise
on an ffl fraction of the inputs from H. As usual the basic algorithm will be to find
a polynomial ~
Q(x; y) which is zero on all the input-output pairs of the black box.
However we will have to do something about the noisy points which do not lie on any
nice algebraic curve. We adapt an algorithm of Welch and Berlekamp [39, 5] (see also
[14]) to handle this situation.
Say we sample the black box B in m points x and the black box outputs
according to some (unknown) polynomial Q in all but m 0 locations. Say
that these locations are given by 0g. We use the fact that
there exists a non-zero polynomial W (x) of degree at most m 0 which is zero when
Indeed W
is such a polynomial. Let Q   (x;
Thus we can modify the
algorithm of the previous section to try to find Q   . This algorithm is summarized as
follows:
The input to the algorithms is m pairs of elements
1. Interpolate to find a set of coefficients q lj of the polynomial
~
that satisfies ~
/* The parameter m 0 will be specified
later. */
2. Factor the polynomial ~
Q and output all its irreducible factors.
be the irreducible factors of the unknown polynomialQ   (x; y)
describing the black box B. We focus on the factor Q 1 . Let the f(1; x); (d; y)g-
weighted degree of Q 1 be k 1 d. The following two lemmas essentially show that if the
fraction of points sufficiently larger than k 1 times
the fraction of noise, then we can reconstruct the polynomial Q 1 .
Lemma 2.12. For a set of points f(x
Q(x; y) and Q 1 (x; y) are
polynomials of f(1; x); (d; y)g-weighted degree at most kd respectively,
satisfying the properties: (1) 8
share a non-constant common
factor.
Proof. The proof is a straightforward modification of the proof of Lemma 2.7. The
only change is in Claim 2.8, where the bound on the degree of the resultant Res y ( ~
goes up to k 1 because the degree of the non-zero entries in the first k 1
columns goes up by m 0 .
Lemma 2.13. Let B be a (k; d)-algebraic black box described by a bivariate polynomial
Q with no repeated non-constant factors. Let Q l be the irreducible factors of Q
of at most f(1; x); (d; y)g-weighted degree k 1
which are the input/output pairs of B on distinct
inputs, if there exists an i 2 [k] such that jfjjQ i
then a set of at most k bivariate polynomials that includes
can be found in time polynomial in m, k and d.
Lemma A.2 of the appendix ensures that if
then a sample of M elements chosen independently and uniformly at
random from F satisfies the following three properties:
1. The x j 's have no repeated elements.
2. There are (strictly) less than ((ffl values of j such that
3. There are at least ((p i +k i ffl)=2)M +k i kd=2 values of j such that Q i
Thus if jHj - 3
randomly points from H and use
as input to
the algorithm described above. If, on the other hand H is small, then we use all
as the input set and use m as input to our algorithm. In
the latter case, Q i is guaranteed to be part of the output if (p
yields the following theorem.
Theorem 2.14. Let B be an ffl-noisy (k; d)-algebraic black box described by a polynomial
Q with no repeated non-constant factors. Further, let l be the (distinct)
irreducible factors of Q and let p i
There exists an algorithm
which takes as input ffi; p ? 0, runs in time poly(k; d; 1
at least reconstructs a list of at most k bivariate polynomials which includes every
3. Multivariate Black Boxes. In this section, we extend Theorem 2.14 to
multivariate polynomial black boxes over finite fields. The methods of Section 2, i.e.,
those based on trying to find the coefficients of polynomials simultaneously, do not
seem to extend directly to the general multivariate case. This is due to the possibly
large explicit representation of the function extracted from the black box, which makes
it inefficient to work with. Instead, we use techniques of pairwise independent sampling
to reduce the problem to a univariate situation and then apply Theorem 2.14
to the new univariate problem. We start by summarizing the problem.
Given: An n-variate ffl-noisy (k; d)-polynomial black . I.e., there exist
n-variate polynomials f of total degree at most d such that
Pr
and furthermore, each f i is well represented in B, i.e.,
Construct k black boxes computing the functions f
Notice that we have changed the problem from that of the previous section in several
ways. First, we no longer ask for an explicit representation of f i , but allow for implicit
representations. This is a strengthening of the problem, since explicit representations
may be much longer than implicit ones and thus allow a reconstruction algorithm
much more time than we do. For instance, if the reconstructed function is a sparse
multivariate polynomial, then we can use any of the sparse multivariate polynomial
interpolation algorithms given in [3, 20, 21, 40] to recover explicit representations
of the reconstructed functions, in running time which is polynomial in the number
of non-zero coefficients rather than total number of possible coefficients. A second
change from the problem of the previous section is that we expect all the polynomials
to be well represented in the black box B. This is a weakening of the
problem, and we do not know how to get around it.
The outline of the method we use to solve the above problem is as follows. Consider
first the slightly simpler problem: Given B and an input - b 2 F n , find the multiset
b)g. This we solve by a reduction to a univariate version of the reconstruction
problem. Now a solution to this problem does not immediately suffice to
yield a solution to the n-variate reconstruction problem as described above. This is
because the solution produces a multiset of values fy for which we do not
know which y j corresponds to f i . We want the black boxes to always output according
to the same polynomial consistently.
In order to solve this problem, we introduce the notion of a reference point -
which will have the property that the value of the k different polynomials will be all
distinct on this point. We will then use a more general reduction to the univariate
problem which will allow us to reconstruct a set of pairs f(y
along with the property of the reference point,
allows us to order the points consistently for all inputs - b. We now go into the details.
3.1. Reference Points. The following definition of a reference point is motivated
by the above discussion. We wish to consider the polynomial Q(x
and want to ensure that at the reference point -
One way to test for this is to see if the polynomial
has any repeated non-constant factors. This will be our definition
of a reference point. Note that this definition is general enough to apply also
to polynomials Q which do not factor linearly in y.
Definition 3.1. For a multivariate polynomial Q(x that has no non-constant
repeated factors, a reference point is an element -
that the univariate polynomial p(y) has no repeated non-constant
factors.
The next lemma will show that a random point is likely to be a reference point for
any given polynomial Q, provided the field size is large compared to the degree of the
polynomial Q. We will need one more notion which is standard in algebra.
Definition 3.2. The discriminant of a univariate polynomial Q(y), denoted \Delta, is
is the derivative of Q with respect to y. The discriminant of a
multivariate polynomial Q(x with respect to y, denoted \Delta(x
defined to be Res y (Q; is the derivative of Q with respect to y. (Formally
the derivative of a monomial q i y i is the summation is of
's. The derivative of a polynomial is simply the sum of the derivatives of the
monomials in it.)
The above definition is motivated by the following well-known fact: A polynomial
(over any unique factorization domain) has repeated non-constant factors if and
only if it shares a common factor with its derivative (cf. [27], Theorem 1.68). From
the well-known fact about resultants, this extends to saying that a polynomial has
repeated non-constant factors if and only if its discriminant is zero.
Lemma 3.3. For a polynomial Q(x
degree at most kd with no repeated non-constant factors a random point - r 2 F n is a
reference point with probability at least 1 \Gamma k(k\Gamma1)d
Proof. Let \Delta(x be the discriminant of Q with respect to y. Notice that
is a polynomial of f(1; x y)g-weighted degree at most (k \Gamma 1)d.
Thus, as in Claim 2.8 we can show that \Delta(x polynomial in x
of degree at most k(k \Gamma 1)d. Since Q has no repeated factors, \Delta(x
identically zero. Thus for a random point - r 2 F n , the probability that
at most k(k \Gamma 1)d=jF j. But observe that \Delta(-r) is the discriminant of the univariate
polynomial p(y)
r is a reference point.
3.2. Reduction to the univariate case. We now consider the case where we
are given a black box B, described by polynomials f and two points -
and we wish to find a set of k pairs f(y such that for every i 2 [k],
there exists some j 2 [k] such that (y We solve this problem by
creating a univariate reconstruction problem and then using Theorem 2.14 to solve
this problem. This reduction builds upon a method of [14], which in turn builds upon
earlier work of [1, 13].
We create a univariate "subdomain", more precisely a function D , such that
the image of the domain, Im(D) satisfies the following properties:,
1. -
a and - b are contained in Im(D).
2. The restriction of a polynomial ~
weighted degree kd to Im(D), i.e., the function ~
Q(D(t); y), is a
bivariate polynomial of f(1; t); (3d; y)g-weighted degree 3kd.
3. Im(D) resembles a randomly and independently chosen sample of F n of size
jF j. In particular, with high probability, the fraction of points from Im(D)
where the black box responds with f(x very close to the fraction
of points from F n where the black box responds with f .
For a finite field F , with constructed
by picking vectors -
at random from F n and
setting construction it
is immediately clear that the "subdomain" D satisfies properties (1) and (2) listed
above. The following lemma shows that it also satisfies property (3) above.
Lemma 3.4. For sets
Pr
d
Proof. Observe that the set of points fD(t)jt 2 F n f0; 1gg, constitute a pairwise
independent sample of points chosen uniformly at random from F n . The lemma now
follows from a standard application of Chebyshev bounds.
Thus we obtain the following algorithm (tuned for confidence parameter
The algorithm is given a threshold p.
1. Pick - c; -
d at random from F n .
2. Let be given by D i
F be the black box given by B
3. Reconstruct all univariate polynomials of degree at most 3d describing
threshold p and confidence
4. Output f(g 1 (0); g 1 (1))g.
(jF j\Gamma2)
. By Lemma 3.4 we know that the above algorithm finds a univariate
domain D, s.t. at most ffl fraction of the points on the domain are "noisy" and
every polynomial is represented on at least p fraction of the domain, with
probability at least 1 \Gamma 1=6. Thus if p i - p for every i, and (p
3kd, then the univariate reconstruction algorithm is guaranteed to find all the f i 's,
with probability at least 1 \Gamma 1=6. The condition on jF j above can be simplified
(somewhat) to (p \Gamma ffl)jF j ? 3kd
and under this condition the
algorithm above returns f(f 1 correctly with probability
at least 2=3. Notice that by repeating log 1
times and outputting the majority answer
(i.e., the set that is output most often), we can boost the confidence up to
any ffi ? 0. This yields the following lemma:
Lemma 3.5. Given an ffl-noisy n-variate polynomial black box B described by polynomials
of degree d, s.t.
there exists a randomized algorithm that takes as input runs
in time poly(n; k; d; 1
outputs the set of k ordered pairs f(f 1
with probability at least
3.3. Putting it together. We are now ready to describe the algorithm for
solving the multivariate reconstruction problem. The algorithm has a preprocessing
stage where it sets up k black boxes, and a query processing stage where it is given a
query point -a 2 F n and the black boxes compute f i (-a).
Preprocessing Stage: Given: Oracle access to a black box B described by polynomials
Parameters k, ffl, p and ffi .
Step 1: Pick - r at random and - b at random.
Step 2: Reconstruct, with confidence 1\Gammaffi, the set f(f 1
using the algorithm of Section 3.2.
Step 3: If the multiset ff 1 has two identical values, then output
"failure". Else pass the reference point - r and the values f 1
to the Query Processing Stage.
Query Processing Stage: Given: Oracle access to a black box B, - b 2 F n and parameters
k; d; p and ffi . Additionally reference point - r and values v
passed on by the Preprocessing Stage.
Step 1: Reconstruct with confidence ffi the set f(f 1
using the algorithm of Section 3.2.
Step 2: If the set ff 1 equals the set fv then reorder
the indices so that f i If the sets are not identical
then report "failure".
Step 3: For every i 2 [k], the black box B i outputs f i (b).
This yields the following theorem.
Theorem 3.6. Let B be an ffl-noisy n-variate (k; d)-polynomial black box s.t.
Pr
and 8i 2 [k] Pr
there exists a randomized algorithm that
takes as input a confidence parameter ffi and with probability
such that for every i 2 [k] there exists j 2 [k] s.t. for every input - b 2 F n ,
the black box
4. Applications. In this section, we describe the application of our techniques
to curve fitting and bivariate polynomial factorization.
4.1. Curve Fitting Problems over Discrete Domains. In this subsection,
we study the curve fitting problem over discret domains. Given a set of m points,
with integer coordinates, we show how to find a polynomial with integer coefficients
that is \Delta-close to all but an ffl fraction of the points (if such a polynomial exists),
need only be less than 1=2 (provided is m is larger than (4\Delta+1)d
(or over the integers) the problem can be formulated as:
Given: m pairs of points, ffl, such that there exists a
polynomial f , of degree at most d, such that for all but fflm values of j in [m]
Problem: Find such an f .
Consider f \Delta]. Notice that all but ffl fraction of
the points are described by the polynomial f i 's. Thus the above problem could be
thought of a reconstruction problem for an ffl-noisy
reconstruction problem. Lemma 2.13 can now be applied to this set of points to get
the following result.
4.1. If there exists an i such that the number of points for which
strictly more than fflm +kd, then we can find a small set of polynomials which includes
The weakness of the above procedure is that it can only be guaranteed to succeed if
ffl is smaller than 1
2\Delta+2 , since only then can we guarantee the existence of an i such
that the polynomial f i (x) is represented more often than the noise in the input set.
We now present a variation of the above method which gets around this weakness
and solves the curve fitting problem for strictly positive values of ffl (independent of
\Delta) and in fact works for ffl arbitrarily close to 1=2.
The idea is that we can artificially decrease the influence of the bad points. To do this,
we look at the following set of points: f(x i
and y i
each point in the original sample, we generate 2\Delta+1 points,
by adding and subtracting up to \Delta to the y coordinate of each point.) We show that
these points represent the output of a (k; d)-algebraic black box for
Observe that the following conditions hold for the (2\Delta+1)m points constructed above:
ffl There exists a polynomial Q(x; y) of f(1; x); (d; y)g-weighted degree at most
fflm+(4\Delta+1)d such that Q(x; all the points. This is the polynomial:
is the
polynomial satisfying W
that the degree of W is fflm.)
ffl At least (1 \Gamma ffl)m of the points satisfy This is because for every
point in the original such that y j is within \Delta of f(x j ) (and there were
one of the new
Lemma 4.2. Given m points 1there exists
a polynomial time algorithm that can find all polynomials f of degree d such that f is
\Delta-close to all but an ffl fraction of the points
Proof. Find a polynomial ~
Q(x; y) such that ~
all the points f(x i
such that the degree of ~
Q is at most fflm
then by Lemma 2.3 we know that for every candidate function f which forms an (ffl; \Delta)
fit on the given points, (y \Gamma f(x)) divides ~
Q. Thus factoring ~
give us all the
candidates.
4.2. Reducing Bivariate Factoring to Univariate Factoring. In Section 2.1,
we saw how to reduce the problem of reconstructing total polynomial black boxes to
the problem of factoring bivariate polynomials. In the specific case of univariate polynomial
black boxes over finite fields, we will also reduce the reconstruction problem
to that of factoring univariate polynomials into their irreducible factors. As an interesting
consequence, we describe a simple way of reducing the problem of factoring
special bivariate polynomials over finite fields to the problem of factoring univariate
polynomials.
We first show how to reduce the reconstruction problem to that of factoring univariate
polynomials: Suppose we have a black box which on input x outputs the (unordered)
set ff 1 where the f i 's are univariate polynomials, each of degree at
most d. Sampling from the black box and interpolating, we can find the polynomial
explicitly (in terms of its coefficients). If somehow we could guarantee
that at least one of the f i 's is irreducible, we could factor t to find f i . Such a
guarantee is not available, but we simulate it via randomization.
Let ff(x) 2 F [x] be a random degree d polynomial. We can convert the given set of
sample points so that on each input x we have the (still unordered) set fg 1
ff(x)g. Each of the polynomials g i is a random degree d polynomial (but they
are not necessarily independent). We then use the fact that random polynomials over
finite fields have a reasonable chance of being irreducible.
Lemma 4.3 ([27], p.84). The probability P q (d) that a random polynomial of degree d
is irreducible over F q , is at least 1
We can thus interpolate (after sampling at kd explicitly compute
into irreducible factors r 1 l . For each factor r j
of g, we verify whether or not r j \Gamma ff is a candidate for one of the f i 's by checking that
it evaluates to one of the outputs of the black box B on all the sampled points. By
Lemma 4.3 we know that with non-negligible probability g i is irreducible and if this
happens, we find g i as one of the factors of g (i.e., as one of the r j 's). Subtracting ff
from g i gives us f i , which will pass the candidacy verification.
Lemma 4.4. If a degree d polynomial p agrees with one of the outputs of the black
box on kd different x's, then p agrees with one of the outputs of the black box on
all x's.
Proof. If p agrees with one of the outputs of the black box on kd different x's,
then by the pigeonhole principle there is a polynomial f i which agrees with p on at
least different x's. Thus
Thus, no r j which is not equal to one of the g i 's will pass the candidacy verification.
By repeating this procedure enough times and outputting all the candidates, we can
reconstruct all the polynomials ff g. Straightforward analysis shows that the
expected number of times that we need to repeat the process (choose random ff) is
O(k=P q (d)). Refining the analysis, we can show that O(ln k=P q (d)) times suffice.
From the above, we get the following algorithm for finding the monic linear factors of
a bivariate polynomial Q(x; y).
program Simple Factor
repeat O( ln k=P q (d) ) times
pick a random degree d polynomial
for every factor g(x) of Q(x; ff(x))
divides Q(x; y)
output (y
4.5. Given a bivariate polynomial Q(x; y), over a finite field F , of total degree
at most kd, the algorithm Simple Factor finds all the linear and monic factors of
We next extend this mechanism, and apply the reconstruction mechanism of Section
2.2 to the problem of finding the factors of Q(x; y) which are monic and of
constant degree in y. Our mechanism tries to isolate some factor A(x; y) of Q(x; y)
of the form
where the a i 's are polynomials in x of degree at most d (and c is a constant).
Let Q(x; y) be a polynomial of f(1; x); (d; y)g-weighted degree kd. For each i 2 [c] we
construct a program P i which is supposed to be a (K; d)-algebraic box for a i , for some
c
. We then use our reconstruction procedure (Theorem 2.14) to produce,
for each i 2 [c], a list of at most K polynomials which contains a i . This, in turn,
gives a set of at most K c polynomials in x and y which contains A(x; y). A(x; y) can
be isolated from this set by exhaustive search. The running time of this algorithm is
thus some polynomial in (kd) c 2
The program P i for a i works as follows on input x
constructs the polynomial Q (which is a polynomial in y)
and factors Q x1 .
ffl Let S be the set of factors of Q x1 . (S contains polynomials in y.)
ffl Let S c be the set of polynomials of degree c obtained by taking products of
polynomials in S.
picks a random polynomial f in S c and outputs the coefficient of y i in f .
We now show that P i is a (2ikd
c
described by some polynomial
the algebraic closure of the quotient ring of polynomials in x, Q(x; y)
factors into linear factors in y; let this factorization be
(The b i (x) are some functions of x, but not necessarily polynomials.) For T ae [k],
l2S b l (x). Notice that the function a i (x) that we
are interested in is actually oe T;i (x) for some T . Notice further that the output of the
program P i is always oe T;i (x) for some T (though this T is some arbitrary subset of [k]).
Thus the input/output pairs (x; y) of the program P i always satisfy
oe T;i Unfortunately, oe T;i (x) need not be a polynomial in x. So we are not done
yet. We will show that Q
actually a
polynomial in x and y of f(1; x); (d; y)g-weighted degree at most Ki, where
c
To see this, consider the coefficient of y j in Q   (x; y). This is q k (x) N times some
polynomial in b 1 By definition of Q   , we
notice that g j is a symmetric polynomial in b 1 of degree at most i
c
. We
now invoke the "fundamental theorem of symmetric polynomials" ([27], pages 29-30)
which states that a symmetric polynomial of degree D in variables z can be
expressed as a polynomial of degree at most D in the primitive symmetric functions in
In our case this translates into saying that, there exists some polynomial
~
of degree at most N s.t. g j (b 1
(since the
primitive symmetric functions in b 1 are actually
qk (x) . Thus
we find that the coefficient of y j in Q   (x; y) is a polynomial in x of degree at most
ikd
c
. The claimed bound on the degree of Q   now follows easily.
Thus we get the following lemma.
Lemma 4.6. Given a polynomial Q(x; y) of f(1; x); (d; y)g-weighted degree kd, there
is an algorithm that runs in time polynomial in (kd) c 2
which finds all factors of Q
that are monic and of degree c in y.

Acknowledgments

. We are very grateful to Avi Wigderson for asking a question
that started us down this line of research and for helpful discussions. We are very
grateful to Umesh Vazirani for his enthusiasm, his valuable opinions and suggestions,
and the time that he spent with us discussing this work. We thank Ronen Basri,
Oded Goldreich and Mike Kearns for their comments on the writeup of this paper.
We thank Joel Friedman for technical discussions about questions related to the topics
of this paper. We also thank the anonymous referees for their extensive reports and
catching many blatant as well as subtle errors from an earlier version of this paper.



--R

Hiding Instance in Multioracle Queries.
Probabilistic Algorithms in Finite Fields
A Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation.
Factoring Polynomials over Large Finite Fields.
Bounded Distance
Learning Switching Concepts.

Occam's Razor.
A note on enumerative counting.
Finding edges and lines in images.
Personal communication to Ronitt Rubinfeld


Highly resilient correctors for polynomials.

Learning polynomials with queries: The highly noisy case.
Factorization of Polynomials over a Finite Field and the Solution of Systems of Algebraic Equations.
Fast decomposition of polynomials into irreducible ones and the solution of systems of algebraic equations.
Algorithms for Sparse Rational Interpolation.
Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents.
Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields.
Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications.
Microeconomic Theory
A Polynomial-Time Reduction from Bivariate to Univariate Integral Polynomial Factorization
Computing with Polynomials Given by Black Boxes for Their Evaluations: Greatest Common Divisors
Learning decision trees using the Fourier spectrum.
Introduction to finite fields and their applications.
New directions in testing.
Factoring polynomials with rational coefficients.
Theory of edge detection.
Randomized Algorithms.
Learning Decision Lists.
An Introduction of the Approximation of Functions.
A new modular interpolation algorithm for factoring multivariate polynomials.
Decoding of Reed Solomon codes beyond the error-correction bound
A Theory of the Learnable

Algebraic Curves.
Correction of Algebraic Block Codes.
Probabilistic Algorithms for Sparse Polynomials.
Interpolating Polynomials from their Values.
--TR

--CTR
Dan Boneh, Finding smooth integers in short intervals using CRT decoding, Journal of Computer and System Sciences, v.64 n.4, p.768-784, June 2002
Dan Boneh, Finding smooth integers in short intervals using CRT decoding, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.265-272, May 21-23, 2000, Portland, Oregon, United States
Fitting algebraic curves to noisy data, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Igor E. Shparlinski, Sparse polynomial approximation in finite fields, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.209-215, July 2001, Hersonissos, Greece
Igor E. Shparlinski , Ron Steinfeld, Noisy Chinese remaindering in the Lee norm, Journal of Complexity, v.20 n.2-3, p.423-437, April/June 2004
Alina Beygelzimer , Mitsunori Ogihara, The enumerability of P collapses P to NC, Theoretical Computer Science, v.345 n.2-3, p.248-259, 22 November 2005
Fitting algebraic curves to noisy data, Journal of Computer and System Sciences, v.67 n.2, p.325-340, September
Oded Goldreich , Dana Ron , Madhu Sudan, Chinese remaindering with errors, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.225-234, May 01-04, 1999, Atlanta, Georgia, United States
A. C. Gilbert , S. Guha , P. Indyk , S. Muthukrishnan , M. Strauss, Near-optimal sparse fourier representations via sampling, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Till Tantau, Query complexity of membership comparable sets, Theoretical Computer Science, v.302 n.1-3, p.467-474, 13 June
Venkatesan Guruswami , Piotr Indyk, Linear time encodable and list decodable codes, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Venkatesan Guruswami, Algorithmic results in list decoding, Foundations and Trends in Theoretical Computer Science, v.2 n.2, p.107-195, January 2007
Zhang , Rajiv Gupta, Hiding program slices for software security, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
bezout's theorem;polynomial interpolation;polynomial factoring;error correcting codes;multivariate polynomials;PAC learning;noisy interpolation