# Increased accuracy of the two-point correlation function at no extra cost

Martin Kerscher
Ludwig–Maximilians Universtät München,
Fakultät für Physik, Schellingstr. 4, D-80799 München
<EMAIL_ADDRESS>
(January 11, 2024)

Using the pair-count implementaion from the Corrfunc package we show that with
a low discrepency sequence we can calculate the two-point correlation function
more accurately than with random points at no extra computational cost.

##  1 Introduction

The Corrfunc package (Sinha & Garrison, 2020, 2019) offers one of the fastest
implementation of pair-counts and is frequently used for calculating the two-
point correlation function for large-scale-structure statistics in cosmology.
We illustrate how one can combine the conceptual improvements suggested by
Kerscher (2022) with the blazingly fast pair-counts from
Corrfunc111https://github.com/manodeep/Corrfunc. With this approach we are
increasing the numerical accuracy of the pair-counts and we are reducing the
systematic error in calculations of the two-point correlation function.

The two-point correlation function of the galaxy distribution is often used to
constrain models of structure and galaxy formation and to estimate parameters
of cosmological models. Observations give us the positions of galaxies in
space. The two-point density

$\varrho_{2}(\bm{x}_{1},\bm{x}_{2})=\varrho^{2}\
\left(1+\xi(|\bm{x}_{1}-\bm{x}_{2}|)\right)$ (1)

is the probability of finding two galaxies at $\bm{x}_{1}$ and $\bm{x}_{2}$,
where $\varrho$ is the number density and $\xi(r)$ is the two-point
correlation function. In a homogeneous and isotropic point process $\xi(r)$
only depends on the separation $r=|\bm{x}_{1}-\bm{x}_{2}|$. We use estimators
to determine $\xi(r)$ from a galaxy catalogue within a finite domain
$W\subset\mathbb{R}^{3}$. In cosmology estimators based on random point sets
are most commonly used. These rely on the data–data DD, data–random DR, and
random–random RR pair-counts.

With DR and RR one performs a Monte-Carlo integration using random points
(Kerscher, 2022, 1999). Replacing these random point sets with a low-
discrepancy sequence of points results in a quasi Monte-Carlo integration.
This leads to an improved scaling of the error that is almost proportional to
$1/{N_{\mathrm{q}}}$, where ${N_{\mathrm{q}}}$ is the number of points from
this low-discrepancy sequence.

In Sec. 2 we give the relevant definitions, in Sec. 3 we illustrate the
preferable properties of the quasi Monte-Carlo integration with a numerical
example, and in Sec. 4 we provide details on the implementation222see
https://github.com/makerscher/corracc for the code. and give some further
comments.

##  2 Pair-counts and estimators

Given the data points $\\{\bm{x}_{i}\\}$, $i=1,\ldots,N$ within the
observational window $\bm{x}_{i}\in W$ the

$\textsf{DD}(r)=\frac{1}{N^{2}}\sum_{i=1}^{N}\sum_{j=1,j\neq
i}^{N}\,\mathbb{1}_{[r,r+\delta]}(|\bm{x}_{i}-\bm{x}_{j}|)$ (2)

is the normalised number of data–data pairs with a distance of
$r=|\bm{x}_{i}-\bm{x}_{j}|$ in the interval $[r,r+\delta]$. The indicator
function $\mathbb{1}_{A}$ of the set $A$ is defined as $\mathbb{1}_{A}(q)=1$
if $q\in A$ and $0$ for $q\notin A$. Now we consider ${N_{\mathrm{r}}}$ random
points $\\{\bm{r}_{i}\\}$, $\bm{r}_{i}\in W$, $i=1,\ldots,{N_{\mathrm{r}}}$
within the same sample geometry $W$ as the data and define the normalised
number of data-random pairs

$\textsf{DR}(r)=\frac{1}{N{N_{\mathrm{r}}}}\sum_{i=1}^{N}\
\sum_{j=1}^{{N_{\mathrm{r}}}}\,\mathbb{1}_{[r,r+\delta]}(|\bm{x}_{i}-\bm{r}_{j}|),$
(3)

and similarly

$\textsf{RR}(r)=\frac{1}{{N_{\mathrm{r}}}^{2}}\sum_{i=1}^{{N_{\mathrm{r}}}}\sum_{j=1,j\neq
i}^{{N_{\mathrm{r}}}}\mathbb{1}_{[r,r+\delta]}(|\bm{r}_{i}-\bm{r}_{j}|),$ (4)

the normalised number of random–random pairs. The Landy & Szalay (1993)
estimator is then given by

$\widehat{\xi}(r)=\frac{\textsf{DD}(r)-2\textsf{DR}(r)+\textsf{RR}(r)}{\textsf{RR}(r)}.$
(5)

As an alternative to the random points we consider a low discrepancy sequence
of points. We use two distinct low discrepancy sequence $\\{\bm{q}_{i}\\}$ and
$\\{\bm{s}_{i}\\}$, with $\bm{q}_{i},\bm{s}_{i}\in W$,
$i=1,\ldots,{N_{\mathrm{q}}}$ (see also Dávila-Kurbán et al. 2021). With one
sequence $\\{\bm{q}_{i}\\}$ we can define DQ in full analogy to DR. To define
QQ we need both sequences,

$\displaystyle\textsf{QQ}(r)$
$\displaystyle=\frac{1}{{N_{\mathrm{q}}}^{2}}\sum_{i=1}^{{N_{\mathrm{q}}}}\sum_{j=1}^{{N_{\mathrm{q}}}}\,\mathbb{1}_{[r,r+\delta]}(|\bm{q}_{i}-\bm{s}_{j}|).$
(6)

QQ is the quasi Monte-Carlo integration scheme, and correspondingly, RR is the
standard Monte-Carlo integration scheme for the same six-dimensional volume
integral (see eq. (15) and (16) in Kerscher 2022). Now we are set to define a
Landy & Szalay (1993) type estimator using a low discrepancy sequence instead
of random points:

$\widehat{\xi}_{\text{qmc}}(r)=\frac{\textsf{DD}(r)-2\textsf{DQ}(r)+\textsf{QQ}(r)}{\textsf{QQ}(r)}.$
(7)

##  3 Comparison

For the comparison of $\widehat{\xi}$ and $\widehat{\xi}_{\text{qmc}}$ we
choose the example data set gals_Mr19.ff from the Corrfunc distribution as our
test data
set333https://github.com/manodeep/Corrfunc/blob/master/theory/tests/data/gals_Mr19.ff.
This simulated galaxy sample is inside a rectangular box, and we can calculate
the exact reference value $\Xi(r)$ for the Landy & Szalay (1993) estimator in
this simple window (Kerscher, 2022). We generate $M=500$ random point sets and
also 500 randomized low-discrepancy sets and calculate $\widehat{\xi}^{(l)}$
and $\widehat{\xi}_{\text{qmc}}^{(l)}$ for each of the $l=1,\ldots,M$ point
sets. We use the same number of points ${N_{\mathrm{r}}}={N_{\mathrm{q}}}$
ranging from $10^{4}$ to $10^{7}$. To quantify the deviation from the exact
value $\Xi(r)$ we use

$\sigma_{\text{qmc}}({N_{\mathrm{q}}},r)^{2}=\frac{1}{M^{2}}\sum_{l=1}^{M}\left(\widehat{\xi}_{\text{qmc}}^{(l)}(r)-\Xi(r)\right)^{2}.$
(8)

and similarly $\sigma({N_{\mathrm{r}}},r)^{2}$.

In the following figures we compare the estimated standard errors
$\sigma({N_{\mathrm{r}}},r)$ and $\sigma_{\text{qmc}}({N_{\mathrm{q}}},r)$. We
see that with $\widehat{\xi}_{\text{qmc}}$ we gain accuracy in all the
situations. For small radii the estimated $\sigma$ can be reduced by a factor
of 2-3 using a low discrepancy sequence (see Fig. 1). Unfortunately the
scaling of $\sigma_{\text{qmc}}$ with ${N_{\mathrm{q}}}$ is only slightly
steeper than the scaling of $\sigma$ with ${N_{\mathrm{r}}}$ in the standard
estimator. Hence for small radii the gain in accuracy is not really
convincing.

As can be seen from Fig. 2 this changes on large scales. By using a low
discrepancy sequence we gain accuracy up to a factor of 10. To obtain a factor
of 10 in accuracy with random points requires 100 times the number of random
points. The error for the standard estimator using random points
$\sigma({N_{\mathrm{r}}},r)$ scales proportional to
$1/\sqrt{(}{N_{\mathrm{r}}})$, whereas the error
$\sigma_{\text{qmc}}({N_{\mathrm{q}}},r)$ for a low-discrepancy sequence is
almost proportional to $1/{N_{\mathrm{q}}}$. The implementation of
$\widehat{\xi}_{\text{qmc}}$ follows closely the implementation of the
standard Landy & Szalay (1993) estimator $\widehat{\xi}$ (see also the next
section). For the same number of points we expect a similar run-time. For a
more examples and a detailed comparison of run-times see Kerscher (2022).

Figure 1: In the top plot we show the estimated error
$\sigma_{\text{qmc}}({N_{\mathrm{q}}},r)$ (solid line, quasi MC) and
$\sigma({N_{\mathrm{r}}},r)$ (dashed line, standard) for different radii
depending on the number of points used. In the lower plot we show the scaling
of the error with the number of points for one radius range. The two dotted
lines are proprtional to $1/\sqrt{N}$ and $1/N$.

Figure 2: The same quantities as in Fig. 1 are shown for larger radii.

##  4 Some notes

### The code:

We provide a sample implementation444https://github.com/makerscher/corracc to
illustrate how one can use the pair-count functions as provided in Corrfunc
with the low discrepancy sequences from SciPy. For calculating the auto- or
cross-correlation function of point sets the package Corrfunc provides the
function Corrfunc.theory.DD. We use this function to calculate DD, RR, DR, DQ
and QQ.

To generate random points we use the random number generator from NumPy
(Harris et al., 2020). To generate low discrepancy sequences we use the
function Halton as provided in SciPy scipy.stats.qmc (starting with version
$\geq$1.7.0, Virtanen et al. 2020). This function allows us to generate
randomised Halton sequences (see Owen 2017, Owen & Rudolf 2021).

Special care has to be taken in the calculation of QQ. As one can see from eq.
(6) we need two distinct low discrepancy sequences (see also eq. (15) and (16)
in Kerscher 2022). We start with a six dimensional Halton sequence inside
$W\times W$ and split it into two three dimensional sequences.

### Exact $\Xi(r)$

As already mentioned the DR, RR and also DQ, QQ are (quasi) Monte-Carlo
schemes for special volume integrals which can be expressed in geometrical
terms for a box (Kerscher, 2022, 1999). We use these terms to calculate the
exact estimator $\Xi(r)$ for a box. Still a numerical integration remains to
be performed. We are using the integration routine quad from
scipy.integration. This calculation can take up to several hours, but for the
comparison we only need this once.

### Beyond a box

For more general sampling areas we are not able to calculate the exact
reference value $\Xi(r)$. Hence we have to compare to the empirical mean

$\overline{\xi}({N_{\mathrm{q}}},r)=\frac{1}{M}\sum_{l=1}^{M}\widehat{\xi}_{\text{qmc}}^{(l)}(r),$
(9)

and calculate the sample error

$\widehat{\sigma}_{\text{qmc}}({N_{\mathrm{q}}},r)^{2}=\frac{1}{M^{2}}\sum_{l=1}^{M}\left(\widehat{\xi}_{\text{qmc}}^{(l)}(r)-\overline{\xi}({N_{\mathrm{q}}},r)\right)^{2}.$
(10)

In the comparions in Sect. 3 we also calculated
$\widehat{\sigma}_{\text{qmc}}$ and saw that it is almost indistinguishable
from $\sigma_{\text{qmc}}$. Hence we expect that
$\widehat{\sigma}_{\text{qmc}}$ is also a good proxy for the expected error
$\sigma_{\text{qmc}}$ in more general situations. This allows the
quantification of systematic errors for a window $W$ beyond a box.

### The periodic box:

We compared the $\widehat{\xi}_{\text{qmc}}(r)$ and $\widehat{\xi}(r)$ for
data in a box, which we saw as an example for more general windows $W$. Hence
we ignored the fact that the data came from a simulation with periodic
boundaries.

Estimating $\xi(r)$ from data with periodic boundaries is much simpler. The
pair-counts $\textsf{DD}(r)$ have to be calculated respecting the periodic
boundary conditions which can be done also with Corrfunc.theory.DD. The
geometric factors for the estimation of $\xi(r)$ are well known and
specifically simple. If we assume a quadratic box $[0,L]^{3}$ with periodic
boundaries we get

$\displaystyle\widehat{\xi}_{\text{per}}(r)$
$\displaystyle=\frac{L^{3}}{\frac{4\pi}{3}\left((r+\delta)^{3}-r^{3}\right)}\textsf{DD}(r)-1$
(11)

More details are given in Appendix A.1 of Kerscher (2022). No random or low
discrepancy point set appears, only the pair-counts $\textsf{DD}(r)$ are used,
see also Corrfunc.theory.xi.

### A special DR and DQ

Kerscher (2022) suggests a special scheme for calculating DR and DQ based on
ideas of Rivolo (1986). Since this requires a different algorithm than the
pair-counts we do not cover it here. Together with another (slower) pair-count
implementation such a special DR, DQ implementation is provided at the
following link555https://homepages.physik.uni-
muenchen.de/~Martin.Kerscher/software/accuratexi/ .

## References

  * Dávila-Kurbán et al. (2021) Dávila-Kurbán, F., Sánchez, A. G., Lares, M., & Ruiz, A. N. 2021, Mon. Not. Roy. Astron. Soc., 506, 4667
  * Harris et al. (2020) Harris, C. R., Millman, K. J., van der Walt, S. J., et al. 2020, Nature, 585, 357
  * Kerscher (1999) Kerscher, M. 1999, Astron. Astrophys., 343, 333
  * Kerscher (2022) Kerscher, M. 2022, Astron. Astrophys., 666, A181
  * Landy & Szalay (1993) Landy, S. D. & Szalay, A. S. 1993, ApJ, 412, 64
  * Owen (2017) Owen, A. B. 2017, arXiv e-prints, arXiv:1706.02808
  * Owen & Rudolf (2021) Owen, A. B. & Rudolf, D. 2021, SIAM Rev., 63(2), 360
  * Rivolo (1986) Rivolo, A. R. 1986, ApJ, 301, 70
  * Sinha & Garrison (2019) Sinha, M. & Garrison, L. 2019, in Software Challenges to Exascale Computing, ed. A. Majumdar & R. Arora (Singapore: Springer Singapore), 3–20
  * Sinha & Garrison (2020) Sinha, M. & Garrison, L. H. 2020, MNRAS, 491, 3022
  * Virtanen et al. (2020) Virtanen, P., Gommers, R., Oliphant, T. E., et al. 2020, Nature Methods, 17, 261


# Almost Optimal Proper Learning and Testing Polynomials

Nader H. Bshouty
Dept. of Computer Science
Technion, Haifa, Israel.

###### Abstract

We give the first almost optimal polynomial-time proper learning algorithm of
Boolean sparse multivariate polynomial under the uniform distribution. For
$s$-sparse polynomial over $n$ variables and $\epsilon=1/s^{\beta}$,
$\beta>1$, our algorithm makes

$q_{U}=\left(\frac{s}{\epsilon}\right)^{\frac{\log\beta}{\beta}+O(\frac{1}{\beta})}+\tilde{O}\left(s\right)\left(\log\frac{1}{\epsilon}\right)\log
n$

queries. Notice that our query complexity is sublinear in $1/\epsilon$ and
almost linear in $s$. All previous algorithms have query complexity at least
quadratic in $s$ and linear in $1/\epsilon$.

We then prove the almost tight lower bound

$q_{L}=\left(\frac{s}{\epsilon}\right)^{\frac{\log\beta}{\beta}+\Omega(\frac{1}{\beta})}+\Omega\left(s\right)\left(\log\frac{1}{\epsilon}\right)\log
n,$

Applying the reduction in [9] with the above algorithm, we give the first
almost optimal polynomial-time tester for $s$-sparse polynomial. Our tester,
for $\beta>3.404$, makes

$\tilde{O}\left(\frac{s}{\epsilon}\right)$

queries.

##  1 Introduction

In this paper, we study the learnability and testability of the class of
sparse (multivariate) polynomials over ${\rm{GF}}(2)$. A polynomial over
${\rm{GF}}(2)$ is the sum in ${\rm{GF}}(2)$ of monomials, where a monomial is
a product of variables. It is well known that every Boolean function has a
unique representation as a (multilinear) polynomial over ${\rm{GF}}(2)$. A
Boolean function is called $s$-sparse polynomial if its unique polynomial
expression contains at most $s$ monomials.

###  1.1 Learning

In the learning model [1, 29], the learning algorithm has access to a black-
box query oracle to a function $f$ that is $s$-sparse polynomial. The goal is
to run in $poly(n,s,1/\epsilon)$ time, make $poly(n,s,1/\epsilon)$ black-box
queries and, with probability at least $2/3$, learn a Boolean function $h$
that is $\epsilon$-close to $f$ under the uniform distribution, i.e., ${\bf
Pr}_{x}[f(x)\not=h(x)]\leq\epsilon$. The learning algorithm is called proper
learning if it outputs an $s$-sparse polynomial. The learning algorithm is
called exact learning algorithm if $\epsilon=0$.

Proper and non-proper learning algorithms of $s$-sparse polynomials that run
in polynomial-time and make a polynomial number of queries have been studied
by many authors [2, 3, 4, 6, 8, 9, 11, 13, 16, 17, 20, 25, 28].

For learning $s$-sparse polynomial without black-box queries (PAC-learning
without black-box queries, [29]) and for exact learning ($\epsilon=0$) the
following results are known. In [20], Hellerstein and Servedio gave a non-
proper learning algorithm that learns only from random examples under any
distribution that runs in time $n^{O(n\log s)^{1/2}}$. Roth and Benedek, [13],
show that for any $s\geq 2$ polynomial-time proper PAC-learning without black-
box queries of $s$-sparse polynomials implies RP=NP. They gave a proper exact
learning ($\epsilon=0$) algorithm that makes $(n/\log s)^{\log s}$ black-box
queries. They also show that to exactly learn $s$-sparse polynomial, we need
at least $(n/\log s)^{\log s}$ black-box queries. See also [13].

For polynomial-time non-proper and proper learning $s$-sparse polynomial with
black-box queries under the uniform distribution, all the algorithms in the
literature, [2, 3, 4, 6, 8, 9, 11, 13, 17, 25, 28], have query complexities
that are at least quadratic in $s$ and linear in $1/\epsilon$. In this paper,
we prove

######  Theorem 1.

Let $\epsilon=1/s^{\beta}$. There is a proper learning algorithm for
$s$-sparse polynomial that runs in polynomial-time and makes

$q_{U}=\left(\frac{s}{\epsilon}\right)^{\frac{\log\beta}{\beta}+O(\frac{1}{\beta})}+\tilde{O}\left(s\right)\left(\log\frac{1}{\epsilon}\right)\log
n$

queries.

To the best of our knowledge, this is the first learning algorithm whose query
complexity is sublinear in $1/\epsilon$ and almost linear in $s$.

We then give the following lower bound that shows that our query complexity is
almost optimal.

######  Theorem 2.

Let $\epsilon=1/s^{\beta}$. Any learning algorithm for $s$-sparse polynomial
must make at least

$q_{L}=\left(\frac{s}{\epsilon}\right)^{\frac{\log\beta}{\beta}+\Omega(\frac{1}{\beta})}+\Omega\left(s\left(\log\frac{1}{\epsilon}\right)\log
n\right)$

queries.

###  1.2 Property Testing

A problem closely related to learning polynomial is the problem of property
testing polynomial: Given black-box query access to a Boolean function $f$.
Distinguish, with high probability, the case that $f$ is $s$-sparse polynomial
versus the case that $f$ is $\epsilon$-far from every $s$-sparse polynomial.
Property testing of Boolean function was first considered in the seminal works
of Blum, Luby and Rubinfeld [7] and Rubinfeld and Sudan [26] and has recently
become a very active research area. See the surveys and books [18, 19, 23,
24].

In the uniform distribution framework, where the distance between two
functions is measured with respect to the uniform distribution, the first
testing algorithm for $s$-sparse polynomial runs in exponential time [14] and
makes $\tilde{O}(s^{4}/\epsilon^{2})$ queries. Chakraborty et al. [12], gave
another exponential time algorithm that makes $\tilde{O}(s/\epsilon^{2})$
queries. Diakonikolas et al. gave in [15] the first polynomial-time testing
algorithm that makes $poly(s,1/\epsilon)>s^{10}/\epsilon^{3}$ queries. In [9],
Bshouty gave a polynomial-time algorithm that makes
$\tilde{O}(s^{2}/\epsilon)$ queries. As for the lower bound for the query
complexity, the lower bound $\Omega(1/\epsilon)$ follows from Bshouty and
Goldriech lower bound in [10]. Blaise et al. [5], and Saglam, [27], gave the
lower bound $\Omega(s\log s)$.

In this paper, we show

######  Theorem 3.

For any $\epsilon=1/s^{\beta}$ there is an algorithm for $\epsilon$-testing
$s$-sparse polynomial that makes

$Q=\left(\frac{s}{\epsilon}\right)^{\frac{\log\beta}{\beta}+O(\frac{1}{\beta})}+\tilde{O}\left(\frac{s}{\epsilon}\right)$

queries.

In particular, for $\beta>3.404$,

$Q=\tilde{O}\left(\frac{s}{\epsilon}\right).$

Notice that the query complexity of the tester in Theorem 3 is
$\tilde{O}((1/\epsilon)^{1+1/\beta})$. This is within a factor of
$(1/\epsilon)^{1/\beta}$ of the lower bound $\Omega(1/\epsilon)$. Therefore,
the query complexity in Theorem 3 is almost optimal.

##  2 Techniques

In this section, we give a brief overview of the techniques used for the main
results, Theorem 1, 2, and 3.

###  2.1 Upper Bound

This section gives a brief overview of the proof of Theorem 1.

Our algorithm first reduces the learning of $s$-sparse polynomial to exact
learning $s$-sparse polynomials with monomials of size at most
$d=O(\log(s/\epsilon))$, i.e., degree-$d$ $s$-sparse polynomials. Given an
$s$-sparse polynomial $f$, we project each variable to $0$ with probability
$O(\log s/\log(1/\epsilon))$. In this projection, monomials of size greater
than $\Omega(d)$ vanish, with high probability. Then we learn the projected
function. We take enough random zero projections of $f$ so that, with high
probability, for every monomial $M$ of $f$ of size at most $\log(s/\epsilon)$,
there is a projection $q$ such that $M$ does not vanish under $q$. Collecting
all the monomials of degree at most $\log(s/\epsilon)$ in all the projections
gives a hypothesis that is $\epsilon$-close to the target function $f$.

Now to exactly learn the degree-$d$ $s$-sparse polynomials, where
$d=O(\log(s/\epsilon))$, we first give an algorithm that finds a monomial of a
degree-$d$ $s$-sparse polynomial that makes

$\displaystyle Q=2^{dH_{2}\left(\frac{\log s}{d}\right)(1-o_{s}(1))}\log
n=s^{\log(\log(s/\epsilon)/\log s)+O(1)}\log n$ (1)

queries where $H_{2}$ is the binary entropy. The best-known algorithm for this
problem has query complexity $Q^{\prime}=2^{d}\log n\approx
poly(s/\epsilon)\log n$, [9, 11]. For small enough $\epsilon$, $Q^{\prime}\gg
Q$. The previous algorithm in [9] chooses uniformly at random assignments
until it finds a positive assignment $a$, i.e., $f(a)=1$. Then recursively do
the same for $f(a*x)$, where $a*x=(a_{1}x_{1},a_{2}x_{2},\ldots,a_{n}x_{n})$,
until no more $a$ with smaller Hamming weight can be found. Then
$f(a*x)=\prod_{a_{i}=1}x_{i}$ is a monomial of $f$. To find a positive
assignment in a degree $d$ polynomial from uniformly at random assignments, we
need to make, on average, $2^{d}$ queries. The number of nonzero entries in
$a*x$ is on average $n/2$. Therefore, this algorithm makes $O(2^{d}\log n)$
queries. In this paper, we study the probability ${\bf Pr}_{{\cal
D}_{p}}[f(a)=1]$ when $a$ is chosen according to the product distribution
${\cal D}_{p}$, where each $a_{i}$ is equal to $1$ with probability $p$ and is
$0$ with probability $1-p$. We show that to maximize this probability, we need
to choose $p=1-(\log s)/d$. Replacing the uniform distribution with the
distribution ${\cal D}_{p}$ in the above algorithm gives the query complexity
in (1).

Now, let $f$ be a degree-$d$ $s$-sparse polynomial, and suppose we have
learned some monomials $M_{1},\ldots,M_{t}$ of $f$. To learn a new monomial of
$f$, we learn a monomial of $f+h$ where $h=M_{1}+M_{2}+\cdots+M_{t}$. This
gives an algorithm that makes,

$\displaystyle
q=\left(\frac{s}{\epsilon}\right)^{\frac{\log\beta}{\beta}+O(\frac{1}{\beta})}\log
n$ (2)

queries where $\epsilon=1/s^{\beta}$. All previous algorithms have query
complexity that are at least quadratic in $s$ and linear in $1/\epsilon$.

Now, notice that the query complexity in (2) is not the query complexity that
is stated in Theorem 1. To get the query complexity in the theorem, we use
another reduction. This reduction is from exact learning degree-$d$ $s$-sparse
polynomials over $n$ variables to exact learning degree-$d$ $s$-sparse
polynomials over $m=O(d^{2}s^{2})$ variables. Given a degree-$d$ $s$-sparse
polynomials $f$ over $n$ variables. We choose uniformly at random a projection
$\phi:[n]\to[m]$ and learn the polynomial
$F(x_{1},\ldots,x_{m})=f(x_{\phi(1)},\ldots,x_{\phi(n)})$ over $m$ variables.
This is equivalent to distributing the $n$ variables, uniformly at random,
into $m$ boxes, assigning different variables for different boxes, and then
learning the function with the new variables. We choose $m=O(d^{2}s^{2})$ so
that different variables in $f$ fall into different boxes. By (2), the query
complexity of learning $F$ is

$\displaystyle
q^{\prime}=\left(\frac{s}{\epsilon}\right)^{\frac{\log\beta}{\beta}+O(\frac{1}{\beta})}\log
m=\left(\frac{s}{\epsilon}\right)^{\frac{\log\beta}{\beta}+O(\frac{1}{\beta})}.$
(3)

After we learn $F$, we find the relevant variables of $F$, i.e., the variables
that $F$ depends on. Then, for each relevant variable of $F$, we search for
the relevant variable of $f$ that corresponds to this variable. Each search
makes $O(\log n)$ queries. The number of relevant variables of $f$ is at most
$ds$ and here $d=O(\log(s/\epsilon))$, which adds

$\tilde{O}(s)\left(\log\frac{1}{\epsilon}\right)(\log n)$

to the query complexity in (3). This gives the query complexity in Theorem 1.
We also show that all the above can be done in time $O(qn)$ where $q$ is the
query complexity.

See more details in Section 3.3.

###  2.2 Lower Bound

This section gives a brief overview of Theorem 2.

In this paper, we give two lower bounds. One that proves the right summand of
the lower bound

$\displaystyle\Omega\left(s\left(\log\frac{1}{\epsilon}\right)\log n\right),$
(4)

and the second proves the left summand

$\displaystyle\left(\frac{s}{\epsilon}\right)^{\frac{\log\beta}{\beta}+\Omega(\frac{1}{\beta})}.$
(5)

To prove (4), we consider the class of $\log(1/(2\epsilon))$-degree $s$-sparse
polynomials. We show that any learning algorithm for this class can be
modified to an exact learning algorithm. Then, using Yao’s minimax principle,
the query complexity of exactly learning this class is at least $\log$ of the
class size. This gives the first lower bound in (4).

To prove (5), we consider the class

$C=\left\\{\left.\prod_{i\in I}x_{i}\prod_{j\in
J}(1+x_{j})\right|I,J\subseteq[n],|J|\leq\log s,|I|\leq\log(1/\epsilon)-\log
s-1\right\\}.$

It is easy to see that every polynomial in $C$ is a $s$-sparse polynomial.

Again, we show that any learning algorithm for this class can be modified to
an exact learning algorithm. We then use Yao’s minimax principle to show that,
to exactly learn $C$, we need at least $\Omega(|C|)$ queries. This gives the
lower bound in (5).

###  2.3 Upper Bound for Testing

For the result in testing, we use the reduction in [9]. In [9] it is shown
that given a learning algorithm for $s$-sparse polynomial that makes $q(s,n)$
queries, one can construct a testing algorithm for $s$-sparse polynomial that
makes

$q(s,\tilde{O}(s))+\tilde{O}\left(\frac{s}{\epsilon}\right)$

queries. Using Theorem 1 we get a testing algorithm with query complexity

$\left(\frac{s}{\epsilon}\right)^{\frac{\log\beta}{\beta}+O(\frac{1}{\beta})}+\tilde{O}\left(\frac{s}{\epsilon}\right).$

We then show that for $\beta\geq 6.219$, this query complexity is
$\tilde{O}(s/\epsilon)$. In Section 5, we give another learning algorithm that
has query complexity better than Theorem 1 for $\beta<6.219$. Using this
algorithm, we get a tester that has query complexity $\tilde{O}(s/\epsilon)$
for $\beta\geq 3.404.$

##  3 Definitions and Preliminary Results

In this section, we give some definitions and preliminary results.

We will denote by $\mathbb{P}_{n,s}$ the class of $s$-sparse polynomials over
the Boolean variables $(x_{1},\ldots,x_{n})$ and
$\mathbb{P}_{n,d,s}\subset\mathbb{P}_{n,s}$, the class of degree-$d$
$s$-sparse polynomials. Formally, let ${\cal S}_{n,\leq d}=\cup_{i\leq d}{\cal
S}_{n,i}$, where ${\cal S}_{n,i}={[n]\choose i}$ is the set of all $i$-subsets
of $[n]=\\{1,2,\ldots,n\\}$. The class $\mathbb{P}_{n,d,s}$ is the class of
all the polynomials of the form

$\sum_{I\in S}\prod_{i\in I}x_{i}$

where $S\subseteq{\cal S}_{n,\leq d}$ and $|S|=s$. The class
$\mathbb{P}_{n,s}$ is $\mathbb{P}_{n,n,s}$.

Let $B_{n}$ be the uniform distribution over $\\{0,1\\}^{n}$. The following
result is well known. See for example [4].

######  Lemma 1.

For any $f\in\mathbb{P}_{n,d,s}$ we have ${\bf Pr}_{x\in B_{n}}[f(x)=1]\geq
2^{-d}$.

We will now extend Lemma 1 to other distributions.

Let $W_{n,s}$ be the set of all the assignments in $\\{0,1\\}^{n}$ of Hamming
weight at least $n-\lfloor\log s\rfloor$. We prove the following for
completeness [25, 13].

######  Lemma 2.

For any $0\not=f\in\mathbb{P}_{n,s}$ there is an assignment $a\in W_{n,s}$
such that $f(a)=1$.

###### Proof.

We prove the result by induction on $s$. For $s=1$, $f$ is one monomial and
therefore $f(1,1,\ldots,1)=1$. Suppose that the statement is true for every
$s^{\prime}\leq s-1$. We prove it for $s$. Let $0\not=f\in\mathbb{P}_{n,s}$.
Since $s>1$ there is a variable, say wlog $x_{1}$, such that
$f=x_{1}f_{1}+f_{2}$ where $f_{1},f_{2}\not=0$. Consider
$f_{1}=f(0,x_{2},\ldots,x_{n})$ and
$f_{2}=f(0,x_{2},\ldots,x_{n})+f(1,x_{2},\ldots,x_{n})$. One of them has at
most $\lfloor s/2\rfloor$ monomials. If $f_{1}$ does, then by the induction
hypothesis there is $a\in W_{n,\lfloor s/2\rfloor}$ such that $f_{1}(a)=1$.
Then for $b=(0,a_{2},\ldots,a_{n})\in W_{n,s}$, $f(b)=f_{1}(a)=1$ . If $f_{2}$
does, then by the induction hypothesis there is $a\in W_{n,\lfloor
s/2\rfloor}$ such that $f_{2}(a)=f_{1}(a)+f(1,a_{1},\ldots,a_{n})=1$. Then
either $f_{1}(a)=1$ or $f(1,a_{1},\ldots,a_{n})=1$ and as before the result
holds for $f$. ∎

The $p$-product distribution ${\cal D}_{n,p}$ is a distribution over
$\\{0,1\\}^{n}$ where ${\cal D}_{n,p}(a)=p^{{\rm wt}(a)}(1-p)^{n-{\rm wt}(a)}$
where ${\rm wt}(a)$ is the Hamming weight of $a$. Let
$H_{2}(x)=-x\log_{2}x-(1-x)\log_{2}(1-x)$ be the binary entropy function.

We prove

######  Lemma 3.

Let $p\geq 1/2$. For every $f\in\mathbb{P}_{n,d,s}$, $f\not=0$, we have

${\bf Pr}_{x\in{\cal
D}_{n,p}}[f(x)=1]\geq\left\\{\begin{array}[]{ll}p^{d-\lfloor\log
s\rfloor}(1-p)^{\lfloor\log s\rfloor}&d\geq\lfloor\log s\rfloor\\\
(1-p)^{d}&d<\lfloor\log s\rfloor\end{array}.\right.$

In particular, if $d\geq 2\lfloor\log s\rfloor$, then for
$p^{\prime}=(d-\lfloor\log s\rfloor)/d$

$\max_{p\geq 1/2}{\bf Pr}_{x\in{\cal D}_{n,p}}[f(x)=1]={\bf Pr}_{x\in{\cal
D}_{n,p^{\prime}}}[f(x)=1]\geq 2^{-H_{2}\left(\frac{\lfloor\log
s\rfloor}{d}\right)d}$

and if $d<2\lfloor\log s\rfloor$, then for $p^{\prime}=1/2$

$\max_{p\geq 1/2}{\bf Pr}_{x\in{\cal D}_{n,p}}[f(x)=1]={\bf Pr}_{x\in{\cal
D}_{n,p^{\prime}}}[f(x)=1]\geq 2^{-d}.$

###### Proof.

We first consider the case $n=d$. Let $0\not=f(x)\in\mathbb{P}_{d,d,s}$. When
$d\geq\lfloor\log s\rfloor$, by Lemma 2, there is $a\in W_{d,s}$ such that
$f(a)=1$. Therefore

$\displaystyle{\bf Pr}_{x\in{\cal D}_{d,p}}[f(x)=1]\geq{\cal
D}_{d,p}(a)=p^{{\rm wt}(a)}(1-p)^{d-{\rm wt}(a)}\geq p^{d-\lfloor\log
s\rfloor}(1-p)^{\lfloor\log s\rfloor}.$ (6)

When $d<\lfloor\log s\rfloor$, we have
$\mathbb{P}_{d,d,s}=\mathbb{P}_{d,d,2^{d}}$. This is because $2^{d}<s$ and any
polynomial in $d$ variables of degree $d$ has at most $2^{d}$ monomials.
Therefore, by (6), we have

$\displaystyle{\bf Pr}_{x\in{\cal D}_{d,p}}[f(x)=1]\geq p^{d-\lfloor\log
2^{d}\rfloor}(1-p)^{\lfloor\log 2^{d}\rfloor}=(1-p)^{d}.$

Thus, the result follows for nonzero functions with $d$ variables.

Let $0\not=f(x)\in\mathbb{P}_{n,d,s}$. Let $M$ be a monomial of $f$ of maximal
degree $d^{\prime}\leq d$. Assume wlog that $M=x_{1}x_{2}\cdots
x_{d^{\prime}}$. First notice that for any
$(a_{d+1},\ldots,a_{n})\in\\{0,1\\}^{n-d}$ we have
$g(x_{1},\ldots,x_{d}):=f(x_{1},\ldots,x_{d},a_{d+1},\ldots,a_{n})\not=0$ and
$g\in\mathbb{P}_{d,d,s}$. Consider the indicator random variable $X(x)$ that
is equal to $1$ if $f(x)=1$. Then

$\displaystyle{\bf Pr}_{x\in{\cal D}_{n,p}}[f(x)=1]$ $\displaystyle=$
$\displaystyle{\bf E}[X]$ $\displaystyle=$ $\displaystyle{\bf
E}_{(a_{d+1},\ldots,a_{n})\in{\cal D}_{n-d,p}}[{\bf
E}_{(x_{1},x_{2},\ldots,x_{d})\in{\cal
D}_{d,p}}[X(x_{1},\ldots,x_{d},a_{d+1},\ldots,a_{n})]]$ $\displaystyle=$
$\displaystyle{\bf E}_{(a_{d+1},\ldots,a_{n})\in{\cal D}_{n-d,p}}[{\bf
Pr}_{(x_{1},x_{2},\ldots,x_{d})\in{\cal
D}_{d,p}}[f(x_{1},\ldots,x_{d},a_{d+1},\ldots,a_{n})=1]]$ $\displaystyle\geq$
$\displaystyle\left\\{\begin{array}[]{ll}p^{d-\lfloor\log
s\rfloor}(1-p)^{\lfloor\log s\rfloor}&d\geq\lfloor\log s\rfloor\\\
(1-p)^{d}&d<\lfloor\log s\rfloor\end{array}.\right.$

∎

In particular, since $f(x)\not=g(x)$ is equivalent to $f(x)+g(x)=1$ and
$f+g\in\mathbb{P}_{n,2s,d}$, we have

######  Lemma 4.

Let $p\geq 1/2$. For every $f,g\in\mathbb{P}_{n,d,s}$, $f\not=g$, we have

${\bf Pr}_{x\in{\cal
D}_{n,p}}[f(x)\not=g(x)]\geq\left\\{\begin{array}[]{ll}p^{d-\lfloor\log
s\rfloor-1}(1-p)^{\lfloor\log s\rfloor+1}&d\geq\lfloor\log s\rfloor+1\\\
(1-p)^{d}&d<\lfloor\log s\rfloor+1\end{array}.\right.$

In particular, if $d\geq 2\lfloor\log s\rfloor+2$, then for
$p^{\prime}=(d-\lfloor\log s\rfloor-1)/d$

$\max_{p\geq 1/2}{\bf Pr}_{x\in{\cal D}_{n,p}}[f(x)\not=g(x)]={\bf
Pr}_{x\in{\cal D}_{n,p^{\prime}}}[f(x)\not=g(x)]\geq
2^{-H_{2}\left(\frac{\lfloor\log s\rfloor+1}{d}\right)d}$

and if $d<2\lfloor\log s\rfloor+2$, then for $p^{\prime}=1/2$

$\max_{p\geq 1/2}{\bf Pr}_{x\in{\cal D}_{n,p}}[f(x)\not=g(x)]={\bf
Pr}_{x\in{\cal D}_{n,p^{\prime}}}[f(x)\not=g(x)]\geq 2^{-d}.$

In particular, for $p^{\prime}=\max((d-\lfloor\log s\rfloor-1)/d,1/2)$,

$\max_{p\geq 1/2}{\bf Pr}_{x\in{\cal D}_{n,p}}[f(x)\not=g(x)]={\bf
Pr}_{x\in{\cal D}_{n,p^{\prime}}}[f(x)\not=g(x)]\geq
2^{-H_{2}\left(\min\left(\frac{1}{2},\frac{\lfloor\log
s\rfloor+1}{d}\right)\right)d}$

Consider the algorithm Test in Figure 1. We now prove

######  Lemma 5.

The algorithm Test$(f,g,\delta)$ for $f,g\in\mathbb{P}_{n,d,s}$ given as
black-boxes, makes

$q=2^{H_{2}\left(\min\left(\frac{\lfloor\log
s\rfloor+1}{d}\right),\frac{1}{2}\right)d}\ln\frac{1}{\delta}$

queries, runs in time $O(qn)$, and if $f\not=g$, with probability at least
$1-\delta$, returns an assignment $a$ such that $f(a)\not=g(a)$. If $f=g$ then
with probability $1$ returns “$f=g$”.

###### Proof.

If $f\not=g$ then, by Lemma 4 and since $1-x\leq e^{-x}$, the probability that
$f(a)=g(a)$ for all $a$ is at most

$\left(1-2^{-H_{2}\left(\min\left(\frac{\lfloor\log
s\rfloor+1}{d}\right),\frac{1}{2}\right)d}\right)^{H_{2}\left(\min\left(\frac{\lfloor\log
s\rfloor+1}{d}\right),\frac{1}{2}\right)d\ln(1/\delta)}\leq\delta.$

∎

Test$(f,g,\delta)$
Input: Black-box access to $f,g\in\mathbb{P}_{m,d,s}$. Output: If $f\not=g$
then find a assignment $a$ such that $f(a)\not=g(a)$. 1. Let
$p=\max\left(1-\frac{\lfloor\log s\rfloor+1}{d},\frac{1}{2}\right).$ 2. Repeat
$2^{H_{2}\left(\min\left(\frac{\lfloor\log
s\rfloor+1}{d},\frac{1}{2}\right)\right)d}\ln\frac{1}{\delta}$ times 3. Draw
$a\in{\cal D}_{m,p}$ 4. If $f(a)\not=g(a)$ then return $a$ 5. Return “$f=g$”

Figure 1: For $f,g\in\mathbb{P}_{m,d,s}$, if $f\not=g$ then, with probability
at least $1-\delta$, returns an assignment $a$ such that $f(a)\not=g(a)$.

###  3.1 The Reduction Algorithms

In this subsection, we give the reductions we use for the learning.

Let $f(x_{1},\ldots,x_{n})$ be any Boolean function. A $p$-zero projection of
$f$ is a random function, $f(z)=f(z_{1},\ldots,z_{n})$ where each $z_{i}$ is
equal to $x_{i}$ with probability $p$ and is equal to $0$ with probability
$1-p$.

We now give the first reduction,

######  Lemma 6.

$(\mathbb{P}_{n,s}\to\mathbb{P}_{n,d,s}).$ Let $0<p<1$ and
$w=(s/\epsilon)^{\log(1/p)}\ln(16s)$. Suppose there is a proper learning
algorithm that exactly learns $\mathbb{P}_{n,d,s}$ with $Q(d,\delta)$ queries
in time $T(d,\delta)$ and probability of success at least $1-\delta$. Then
there is a proper learning algorithm that learns $\mathbb{P}_{n,s}$ with
$O(w\cdot Q(D,1/(16w))\log(1/\delta))$ queries where

$D=\log\frac{s}{\epsilon}+\frac{\log s+\log\log s+6}{\log(1/p)},$

in time $w\cdot T(D,1/(16w))\log(1/\delta)$, probability of success at least
$1-\delta$ and accuracy $1-\epsilon$.

###### Proof.

Let $A(d,\delta)$ be a proper learning algorithm that exactly learns
$\mathbb{P}_{n,d,s}$ with $Q(d,\delta)$ queries in time $T(d,\delta)$ and
probability of success $1-\delta$. We will give an algorithm $B(d,\epsilon)$
that, with probability at least $2/3$, learns $\mathbb{P}_{n,s}$ with accuracy
$1-\epsilon$. We will show that, with probability at least $2/3$, algorithm
$B$ finds all the monomials of $f$ of size at most $\log(s/\epsilon)$. Let $h$
be the sum of those monomials. Then,

${\bf Pr}[h\not=f]\leq s2^{-\log(s/\epsilon)}\leq\epsilon.$

Therefore, by running $B$, $O(\log(1/\delta))$ times, we get a learning
algorithm with a probability of success at least $1-\delta$.

Let $f\in\mathbb{P}_{n,s}$ be the target function. Algorithm $B$ chooses $w$
$p$-zero projections $f(z^{(1)}),f(z^{(2)}),\ldots$ $,f(z^{(w)})$ of $f$. It
runs $w$ copies of $A(D,1/(16w))$ to learn all $f(z^{(i)})$, $i\in[w]$. Let
$h_{i}$ be the hypothesis that the $i$-th copy of $A$ learns, $i\in[w]$. It
then defines a hypothesis $h$ equal to the sum of all the monomials $M$ in all
$h_{i}$ of size at most $\log(s/\epsilon)$. The number of queries that $B$
makes is $w\cdot Q(D,1/(16w)).$

To prove the correctness of the algorithm, we consider the following two
events

  1. 1.

$E_{1}$: For every $i$ we have $f(z^{(i)})\in\mathbb{P}_{n,D,s}$.

  2. 2.

$E_{2}$: For every monomial $M$ of $f$ of size at most $\log(s/\epsilon)$,
there is $i\in[w]$ such that $M$ is a monomial of $f(z^{(i)})$.

If the event $E_{1}$ occurs, then, with probability at least $15/16$, all the
copies of $A$ learn the projected functions. If $E_{2}$ occurs, assuming
$E_{1}$ occurs, $h$ contains all the monomials of $f$ of size at most
$\log(s/\epsilon)$.

We have

$\displaystyle{\bf Pr}[\mbox{not\ }E_{1}]$ $\displaystyle=$ $\displaystyle{\bf
Pr}[(\exists i\in[w])(\exists M\in f,|M|>D)M(z^{(i)})\not=0]$
$\displaystyle\leq$ $\displaystyle wsp^{D}\leq\frac{1}{16}.$

and

$\displaystyle{\bf Pr}[\mbox{not\ }E_{2}]$ $\displaystyle=$ $\displaystyle{\bf
Pr}[(\exists M\in f,|M|\leq\log(s/\epsilon))(\forall i\in[w])M(z^{(i)})=0]$
$\displaystyle\leq$ $\displaystyle
s\left(1-p^{\log(s/\epsilon)}\right)^{w}\leq s\cdot
exp\left(-\left(\frac{\epsilon}{s}\right)^{\log(1/p)}w\right)=\frac{1}{16}.$

Now assuming $E_{1}$ occurs, the probability that $A(D,1/(16w))$ does not
learn some $f(z^{(i)})$, $i\in[w]$, is at most $1/16$. Assuming also $E_{2}$
occurs, $h$ is the required hypothesis. Therefore, the probability that $h$
contains all the monomials of $f$ of size at most $\log(s/\epsilon)$ is at
least $13/16>2/3$. ∎

Before we give the second reduction, we first give two auxiliary lemmas.

The following is trivial,

######  Lemma 7.

There is a non-adaptive exact proper learning algorithm for
$C=\\{0,1,x_{1},\ldots,x_{n},\bar{x}_{1},$ $\ldots,\bar{x}_{n}\\}$ that makes
$\log n+O(1)$ queries and runs in time $O(n\log n)$.

We say that $x_{i}$ is a relevant variable of $f$ if there is
$a,b\in\\{0,1\\}^{n}$ that differ only in the $i$th coordinate such that
$f(a)\not=f(b)$. We say that $f$ is independent of $x_{i}$ if it is irrelevant
variable of $f$.

######  Lemma 8.

There is an algorithm that for any Boolean function $f\in\mathbb{P}_{s}$ that
is expressed as a polynomial function and a variable $x_{j}$, runs in time
$O(ds)$ and decides if $x_{j}$ is relevant variable of $f$, and if it does,
finds two assignments $a$ and $b$ that differ only in the $j$th coordinate and
$f(a)\not=f(b)$.

###### Proof.

The variable $x_{j}$ is a relevant variable of $f$ if it appears in one of the
monomials of $f$ (in its unique polynomial expression). Now suppose
$f(x)=x_{j}f_{1}(x)+f_{0}(x)$ where $f_{0},f_{1}$ are independent of $x_{j}$.
Take a monomial $M=x_{i_{1}}\cdots x_{i_{r}}$ of $f_{1}$ with minimal $r$.
Then define $a\in\\{0,1\\}^{n}$ where $a_{i}=1$ if
$i\in\\{i_{1},\ldots,i_{r}\\}$, and $a_{i}=0$, otherwise. Then define $b$ to
be $a$ with the $a_{j}$ flipped to $1$.

Now $f_{1}(a)=1$, $f(a)=f_{0}(a)$ and
$f(b)=f_{1}(a)+f_{0}(a)=1+f_{0}(a)\not=f_{0}(a)=f(a)$. ∎

We now give the second reduction.

######  Lemma 9.

$(\mathbb{P}_{n,d,s}\to\mathbb{P}_{(2ds)^{2},d,s}).$ Suppose there is a proper
learning algorithm that exactly learns $\mathbb{P}_{(2ds)^{2},d,s}$ with
$Q(d,\delta)$ queries in time $T(d,\delta)$ and probability of success at
least $1-\delta$. Then there is a proper learning algorithm that exactly
learns $\mathbb{P}_{n,d,s}$ with $q=(Q(d,1/16)+ds\log n)\log(1/\delta)$
queries in time $(T(d,1/16)+dsn\log n)\log(1/\delta)$ and probability of
success at least $1-\delta$.

###### Proof.

Let $A(d,\delta)$ be a proper learning algorithm that exactly learns
$\mathbb{P}_{(2ds)^{2},d,s}$ with $Q(d,\delta)$ queries in time $T(d,\delta)$
and probability of success at least $1-\delta$. It is enough to find a
learning algorithm that exactly learns $\mathbb{P}_{n,d,s}$ with probability
of success at least $2/3$.

Define the following algorithm $B$. The algorithm draws uniformly at random a
map $\phi:[n]\to[m]$ where $m=(2ds)^{2}$, and defines
$F(x_{1},\ldots,x_{m})=f(x_{\phi(1)},\ldots,x_{\phi(n)})$ and then exactly
learns $F$ using the algorithm $A(d,1/16)$. Then for every relevant variable
$x_{i}$ of $F$, $i\in[m]$ it finds using Lemma 8 two assignments
$a,b\in\\{0,1\\}^{m}$ that differ only in the $i$th coordinate and
$F(a)\not=F(b)$, and, using the algorithm in Lemma 7, it learns
$f(\pi^{(i,a)})$ where

$\pi^{(i,a)}_{j}=\left\\{\begin{array}[]{ll}a_{\phi(j)}&\phi(j)\not=i\\\
x_{j}&\phi(j)=i\end{array}\right..$

Then algorithm $B$ returns $F(y_{1},\ldots,y_{m})$ where $y_{i}=x_{j}$ if
$x_{i}$ is a relevant variable of $F$ and
$f(\pi^{(i,a)})\in\\{x_{j},\bar{x}_{j}\\}$ and $y_{i}=0$ otherwise.

We now prove the correctness of the algorithm. Notice that every
$f\in\mathbb{P}_{n,d,s}$ has at most $ds$ relevant variables. Let
$x_{r_{1}},\ldots,x_{r_{\ell}}$, $\ell\leq ds$, be the relevant variables of
$f$. Let $A$ be the event that $\phi(r_{1}),\ldots,\phi(r_{\ell})$ are
distinct. The probability that $A$ occurs is at least
$(1-1/m)(1-2/m)\cdots(1-(\ell-1)/m)\geq 7/8$. We now assume that event $A$
occurs. In particular, $x_{\phi(r_{1})},\ldots,x_{\phi(r_{\ell})}$ are the
relevant variables of $F$.

Let $\phi(r_{i})=t_{i}$. Let $a,b\in\\{0,1\\}^{m}$ be two assignments that
differ in the $t_{i}$-th coordinate and $F(a)\not=F(b)$. Assume wlog
$a_{t_{i}}=0$ . Then $f(\pi^{(t_{i},a)})$ is a non-constant function. This is
because $f(\pi^{(t_{i},a)})$ is a function on the variables
$\\{x_{u}\\}_{\phi(u)=t_{i}}$ where if we substitute $0$ in all
$\\{x_{u}\\}_{\phi(u)=t_{i}}$ we get $F(a)$ and if we substitute $1$ in all
$\\{x_{u}\\}_{\phi(u)=t_{i}}$ we get $F(b)$. Now since $\phi(r_{i})=t_{i}$,
and since event $A$ occurs, $x_{r_{i}}$ is the only variable in
$\\{x_{u}\\}_{\phi(u)=t_{i}}$ that is relevant variable of $f$. Therefore,
$f(\pi^{(t_{i},a)})\in\\{x_{r_{i}},\bar{x}_{r_{i}}\\}$.

Thus, $y_{\phi(r_{i})}=y_{t_{i}}=x_{r_{i}}$ and
$F(y_{1},\ldots,y_{m})=f(y_{\phi(1)},\ldots,y_{\phi(n)})=f$. ∎

###  3.2 The Algorithm for $\mathbb{P}_{m,d,s}$

In this section, we give a learning algorithm that exactly learns
$\mathbb{P}_{m,d,s}$.

Consider the algorithm FindMonomial in Figure 2. For two assignments $a$ and
$b$ in $\\{0,1\\}^{m}$ we define $a*b=(a_{1}b_{1},\ldots,a_{m}b_{m})$. We
prove

######  Lemma 10.

For $f\in\mathbb{P}_{m,d,s}$, $f\not=0$, FindMonomial$(f,d,\delta)$ makes at
most

$Q=O\left(2^{dH_{2}\left(\min\left(\frac{\lfloor\log
s\rfloor+1}{d},\frac{1}{2}\right)\right)}d\log(m/\delta)\right)$

queries, runs in time $O(Qn)$, and with probability at least $1-\delta$
returns a monomial of $f$.

###### Proof.

Let $t=8d\ln(m/\delta)$. Let $a^{(1)},\ldots,a^{(t)}$ be the assignments
generated in the “Repeat” loop of FindMonomial$(f,d,\delta)$. Define the
random variable $X_{i}=wt(a^{(i)})-d_{i}$, $i\in[t]$, where $d_{i}$ is the
degree of the minimal degree monomial of $f(a^{(i)}*x)$. First notice that
every monomial of $f(a^{(i)}*x)$ is a monomial of $f(a^{(i-1)}*x)$ and of $f$.
Therefore, $d\geq d_{i+1}\geq d_{i}$. Also, if $X_{i}=0$ then
$f(a^{(i)}*x)=\prod_{a^{(i)}_{j}=1}x_{j}$ is a monomial of $f$.

Given $a^{(i)}$ such that $g(x)=f(a^{(i)}*x)\not=0$. Notice that
$g\in\mathbb{P}_{m,d,s}$ and if $f(b*a^{(i)}*x)=0$ then $a^{(i+1)}=a^{(i)}$,
$d_{i+1}=d_{i}$ and $X_{i+1}=X_{i}$. Let $M$ be any monomial of $g$ of degree
$d_{i}$ and suppose, wlog, $M=x_{1}x_{2}\cdots x_{d_{i}}$. For $b\in{\cal
D}_{m,p}$ where $p=2^{-1/d}$, with probability $\eta:=(2^{-1/d})^{d_{i}}\geq
1/2$, $b_{1}=b_{2}=\cdots=b_{d_{i}}=1$. If $b_{1}=b_{2}=\cdots=b_{d_{i}}=1$
then $f(b*a^{(i)}*x)\not=0$. This is because $M$ remains a monomial of
$f(b*a^{(i)}*x)$. Therefore, $\eta^{\prime}:={\bf
Pr}[f(b*a^{(i)}*x)\not=0]\geq\eta$. The expected weight of
$(b_{d_{i}+1}a^{(i)}_{d_{i}+1},\ldots,b_{m}a^{(i)}_{m})$ is $2^{-1/d}X_{i}$.
Also, if $f(b*a^{(i)}*x)\not=0$ then, with probability at least $1/2$, Test
succeed to detect that $f(b*a^{(i)}*x)\not=0$. Therefore,

$\displaystyle{\bf E}[X_{i+1}|X_{i}]$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\eta^{\prime}(2^{-1/d}X_{i})+\left(1-\frac{\eta^{\prime}}{2}\right)X_{i}$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\eta^{\prime}\left(1-\frac{1}{2d}\right)X_{i}+\left(1-\frac{\eta^{\prime}}{2}\right)X_{i}$
$\displaystyle=$
$\displaystyle\left(1-\frac{\eta^{\prime}}{4d}\right)\leq\left(1-\frac{1}{8d}\right)X_{i}.$

Now, $X_{0}\leq m$ and therefore

${\bf E}[X_{t}]\leq m\left(1-\frac{1}{8d}\right)^{t}\leq{\delta}.$

Thus, by Markov’s bound, the probability that $f(a^{(t)}*x)$ is not a monomial
is

${\bf Pr}[X_{t}\not=0]={\bf Pr}[X_{t}\geq 1]\leq\delta.$

Now, by Lemma 5, the query complexity in the lemma follows. ∎

FindMonomial$(f,d,\delta)$
Input: Black-box access to $f\in\mathbb{P}_{m,d,s}$ Output: Find a monomial of
$f$. Procedure Test$(f,g,\delta)$ in Figure 1 tests, with confidense
$1-\delta$, if $f=g$ using Lemma 3. If $f\not=g$ then it returns an assignment
$u$ such that $f(u)\not=g(u).$ 1. $a=(1,1,1,\ldots,1)\in\\{0,1\\}^{m}$. 2.
Repeat $t=8d\ln\frac{m}{\delta}$ times 3. Draw $b\in{\cal D}_{m,p}$ where
$p=2^{-1/d}$. 4. Test($f(b*a*x)$,$0$,$1/2$) 5. If $f(b*a*x)\not=0$ then
$a\leftarrow a*b$. 6. Return $\prod_{a_{i}=1}x_{i}$

Figure 2: For $f\in\mathbb{P}_{m,d,s}$ returns a monomial of $f$.

We now prove

######  Lemma 11.

There is a proper learning algorithm that exactly learns $\mathbb{P}_{m,d,s}$,
makes

$Q(m,d,\delta)=O\left(s2^{H_{2}\left(\min\left(\frac{\lfloor\log
s\rfloor+1}{d}\right),\frac{1}{2}\right)d}d\log(ms/\delta)\right)$

queries, and runs in time $O(Q(m,d,\delta)n)$.

###### Proof.

In the first iteration of the algorithm, we run FindMonomial$(f,d,\delta/s)$
to find one monomial. Suppose at iteration $t$ the algorithm has $t$ monomials
$M_{1},\ldots,M_{t}$ of $f$. In the $t+1$ iteration, we run
FindMonomial$(f+\sum_{i=1}^{t}M_{i},d,\delta/s)$ to find a new monomial of
$f$.

The correctness and query complexity follows from Lemma 10. ∎

###  3.3 The Algorithm

In this section, we give the algorithm for $\mathbb{P}_{n,s}$. We prove

######  Theorem 4.

Let $\epsilon=1/s^{\beta}$, $\beta\geq 1$. There is a proper learning
algorithm for $s$-sparse polynomial with probability of success at least $2/3$
that makes

$\displaystyle
q_{U}=\left(\frac{s}{\epsilon}\right)^{\gamma(\beta)+o_{s}(1)}+O\left(s\left(\log\frac{1}{\epsilon}\right)\log
n\right)$ (8)

queries and runs in time $O(q_{U}\cdot n)$ where

$\gamma(\beta)=\min_{0\leq\eta\leq
1}\frac{\eta+1}{\beta+1}+(1+1/\eta)H_{2}\left(\frac{1}{(1+1/\eta)(\beta+1)}\right).$

In particular

  1. 1.

$\gamma(\beta)=\frac{\log\beta}{\beta}+\frac{4.413}{\beta}+\Theta\left(\frac{1}{\beta^{2}}\right).$

  2. 2.

$\beta$ | $\gamma(\beta)$
---|---
1 | 2.617
2 | 1.961
3 | 1.582
4 | 1.336
5 | 1.157
6 | 1.025
7 | 0.921

  3. 3.

$\gamma(\beta)<1$ for $\beta>6.219$. That is, the query complexity is
sublinear in $1/\epsilon$ and almost linear in $s$ when $\beta>6.219$.

  4. 4.

For $\beta>4.923$ the query complexity is better than the best known query
complexity (which is $s^{2}/\epsilon=(s/\epsilon)^{(2+\beta)/(1+\beta)}$).

  5. 5.

$\gamma(\beta)\leq 4$ for all $\beta$, and $\gamma$ is a monotone decreasing
function in $\beta$.

We note here that in Section 5, we give another algorithm that improves the
bounds in items 2-5. In particular, the query complexity of the algorithm in
Section 5 with the above algorithm is better than the best-known query
complexity for $\beta>1$. The above algorithm also works for $\beta<1$, but
the one in Section 5 has a better query complexity.

We now give the proof of the Theorem

Since $\log(1/\epsilon)/(\log s)=\beta\geq 1$, we have $\log
s<\log(1/\epsilon)$. Let $p>1/2$ and

$D=\log\frac{s}{\epsilon}+\frac{\log s+\log\log s+6}{\log(1/p)}>2\log s+2.$

We will choose $p$ later such that $\log(1/p)=\Theta((\log
s)/(\log(1/\epsilon))$ and therefore
$D=O(\log(s/\epsilon))=O(\log(1/\epsilon))$.

We start from the algorithm in Lemma 11 that exactly learns
$\mathbb{P}_{(2Ds)^{2},D,s}$ with

$Q_{1}(D,\delta)=O\left(s2^{D\cdot H_{2}\left(\frac{\lfloor\log
s\rfloor+1}{D}\right)}D\log((2Ds)^{2}s/\delta)\right)=\tilde{O}\left(s2^{D\cdot
H_{2}\left(\frac{\lfloor\log s\rfloor+1}{D}\right)}\right)\log(1/\delta)$

queries, time $O(Q_{1}n)$ and probability of success at least $1-\delta$.

By the second reduction, Lemma 9, there is a proper learning algorithm that
exactly learns $\mathbb{P}_{n,D,s}$ with

$\displaystyle Q_{2}(D,\delta)$ $\displaystyle=$
$\displaystyle(Q_{1}(D,1/16)+Ds\log n)\log(1/\delta)$ $\displaystyle=$
$\displaystyle\left(\tilde{O}\left(s2^{D\cdot H_{2}\left(\frac{\lfloor\log
s\rfloor+1}{D}\right)}\right)+O\left(s\left(\log\frac{1}{\epsilon}\right)\log
n\right)\right)\log(1/\delta).$

queries in time $O(Q_{2}(D,\delta)n)$ and probability of success at least
$1-\delta$.

If we now use the first reduction in Lemma 6 as is we get the first summand in
the query complexity in (8), but the second summand,
$O(s\log(1/\epsilon)\log(n))$, becomes
$(s^{1+\log(1/p)}/\epsilon^{\log(1/p)})(\log(1/\epsilon))$ $\log(n)$, which is
not what we stated in the Theorem. Instead, we use the first reduction with
the following changes.

Notice that the $\log n$ in the summand $ds\log(n)$ in the first reduction
resulted from searching for the relevant variable in the set
$\\{x_{u}\\}_{\phi(u)=t}$ for some $t\in[m]$. See the proof of Lemma 9.
Suppose the algorithm knows a priori $w$ relevant variables of the function
$f$ and is required to run the second reduction. Then the term $ds\log n$ can
be replaced by $(ds-w)\log n$. This is because the reduction needs to search
only for the other at most $ds-w$ relevant variables of $f$. Now, if we use
the first reduction in Lemma 6, when we find the relevant variables of $f$ in
the $p$-zero projections $f(z^{(1)}),\ldots,f(z^{(i)})$, we do not need to
search for them again in the following $p$-zero projections
$f(z^{(i+1)}),\ldots,f(z^{(w)})$. Therefore, the query complexity of the
search of all the variables remains $O(s\log(1/\epsilon)\log(n))$.

Therefore, after using the first reduction with the above modification, we get
a proper learning algorithm that learns $\mathbb{P}_{n,s}$ that makes

$Q_{3}(d,\delta,\epsilon)=\left(\tilde{O}\left(s\left(\frac{s}{\epsilon}\right)^{\log(1/p)}2^{D\cdot
H_{2}\left(\frac{\lfloor\log
s\rfloor+1}{D}\right)}\right)+O\left(s\left(\log\frac{1}{\epsilon}\right)\log
n\right)\right)\log(1/\delta)$

queries in time $O(n\cdot Q_{3})$, probability of success at least $1-\delta$
and accuracy $1-\epsilon$.

Now recall that $\epsilon=1/s^{\beta}$ and choose $p=2^{-\eta/(\beta+1)}$ for
a constant $0<\eta<1$. Then $p>1/2$, $\log(1/p)=\eta/(\beta+1)=\Theta((\log
s)/\log(1/\epsilon))$,

$D=(\beta+1)\left(1+\frac{1}{\eta}\right)\log s+\Theta(\beta\log\log
s)=\left(1+\frac{1}{\eta}\right)\log\frac{s}{\epsilon}+\Theta(\beta\log\log
s)$

and

$\displaystyle s\left(\frac{s}{\epsilon}\right)^{\log(1/p)}2^{D\cdot
H_{2}\left(\frac{\lfloor\log s\rfloor+1}{D}\right)}$ $\displaystyle=$
$\displaystyle\left(\frac{s}{\epsilon}\right)^{\frac{\eta+1}{\beta+1}}\left(\frac{s}{\epsilon}\right)^{\left((1+1/\eta)+\Theta\left(\frac{\log\log
s}{\log
s}\right)\right)H_{2}\left(\frac{1}{(1+1/\eta)(\beta+1)}\left(1-\Theta\left(\frac{\log\log
s}{\beta\log s}\right)\right)\right)}$ $\displaystyle=$
$\displaystyle\left(\frac{s}{\epsilon}\right)^{\frac{\eta+1}{\beta+1}+(1+1/\eta)H_{2}\left(\frac{1}{(1+1/\eta)(\beta+1)}\right)(1-o_{s}(1))}.$

This completes the proof.

##  4 Lower Bounds

In this section, we prove the following lower bound for learning sparse
polynomials.

######  Theorem 5.

Let $\epsilon=1/s^{\beta}$. Any learning algorithm for $s$-sparse polynomial
with a confidence probability of at least $2/3$ must make at least

$\displaystyle q_{L}$ $\displaystyle=$
$\displaystyle\tilde{\Omega}\left(\left(\frac{s}{\epsilon}\right)^{\frac{\beta\cdot
H_{2}(\min(1/\beta,1/2))}{\beta+1}}\right)+\Omega\left(s\left(\log\frac{1}{\epsilon}\right)\log
n\right)$ $\displaystyle=$
$\displaystyle\left(\frac{s}{\epsilon}\right)^{\frac{\log\beta}{\beta}+\frac{1}{(\ln
2)\beta}+\Omega(\frac{\log\beta}{\beta^{2}})}+\Omega\left(s\left(\log\frac{1}{\epsilon}\right)\log
n\right)$

queries.

We first give the following lower bound that proves the second summand in the
lower bound

######  Lemma 12.

Any learning algorithm for $\mathbb{P}_{n,s}$ with a confidence probability of
at least $2/3$ must make at least

$\Omega\left(s\left(\log\frac{1}{\epsilon}\right)\log n\right)$

queries.

###### Proof.

Consider the class $C=\mathbb{P}_{n,\log(1/(2\epsilon)),s}$. Consider a
(randomized) learning algorithm $A_{R}$ for $\mathbb{P}_{n,s}$ with a
confidence probability of at least $2/3$ and accuracy $\epsilon$. Then $A_{R}$
is also a (randomized) learning algorithm for $C$. Since by Lemma 1, any two
distinct functions in $C$ have distance $2\epsilon$, $A_{R}$ exactly learns
$C$ with a confidence probability of at least $2/3$. This is because, after
learning an $\epsilon$-close formula $h$, since any two distinct functions in
$C$ have distance $2\epsilon$, the closest function in $C$ to $h$ is the
target function. By Yao’s minimax principle, there is a deterministic non-
adaptive exact learning algorithm $A_{D}$ with the same query complexity as
$A_{R}$ that learns at least $(2/3)|C|$ functions in $C$. By the standard
information-theoretic lower bound, the query complexity of $A_{D}$ is at least
$\log((2/3)|C|)$. Since

$\log|C|=\log{{n\choose\log(1/(2\epsilon))}\choose
s}=\Omega\left(\left(\log\frac{1}{\epsilon}\right)s\log n\right)$

the result follows. ∎

We now give the following lower bound that proves the second summand in the
lower bound

######  Lemma 13.

Let $\epsilon=1/s^{\beta}$. Any learning algorithm for $\mathbb{P}_{n,s}$ with
a confidence probability of at least $2/3$ must make at least

$\Omega\left(\left(\frac{s}{\epsilon}\right)^{\frac{\beta\cdot
H_{2}(\min(1/\beta,1/2))}{\beta+1}}\right)$

queries.

###### Proof.

We first prove the lower bound for $\beta>1$. Let $t=\log(1/\epsilon)-\log
s-1$ and $r=\log s$. Let $W$ be the set of all pairs $(I,J)$ where $I$ and $J$
are disjoint sets, $I\cup J=[t+r]$, $|I|\geq t$ and $|J|=t+r-|I|\leq r$. For
every $(I,J)\in W$ define $f_{I,J}=\prod_{i\in I}x_{i}\prod_{j\in
J}(1+x_{j}).$ Consider the set $C=\\{f_{I,J}|(I,J)\in W\\}$. First notice that
$C\subset\mathbb{P}_{n,t+r,s}\subseteq\mathbb{P}_{n,s}$ and, by Lemma 1, ${\bf
Pr}[f_{I,J}=1]\geq 2^{-(t+r)}=2^{-\log(1/\epsilon)+1}=2\epsilon$. Furthermore,
since for $(I_{1},J_{1})\not=(I_{2},J_{2})$ the degree of
$f_{I_{1},J_{1}}+f_{I_{2},J_{2}}$ is $\log(1/\epsilon)-1$, we also have

$\displaystyle{\bf Pr}[f_{I_{1},J_{1}}\not=f_{I_{2},J_{2}}]\geq 2\epsilon.$
(9)

Therefore, any learning algorithm for $\mathbb{P}_{n,s}$ (with accuracy
$\epsilon$ and confidence $2/3$) is a learning algorithm for $C$ and thus is
an exact learning algorithm for $C$. This is because, after learning an
$\epsilon$-close formula $h$, by (9), the closest function in $C$ to $h$ is
the target function.

Consider now a (randomized) non-adaptive exact learning algorithm $A_{R}$ for
$C$ with probability of success at least $2/3$ and accuracy $\epsilon$. By
Yao’s minimax principle, there is a deterministic non-adaptive exact learning
algorithm $A_{D}$ such that, for uniformly at random $f\in C$, with a
probability at least $2/3$, $A_{D}$ returns $f$. We will show that $A_{D}$
must make more than $q=(1/10)|C|$ queries. Now since,

$\displaystyle|C|$ $\displaystyle=$ $\displaystyle\sum_{i=0}^{\log
s}{\log\frac{1}{\epsilon}-2\choose i}$ $\displaystyle\geq$
$\displaystyle\tilde{\Omega}\left(2^{H_{2}\left(\min\left(\frac{\log
s}{\log(1/\epsilon)},\frac{1}{2}\right)\right)\log(1/\epsilon)}\right)$
$\displaystyle=$
$\displaystyle\tilde{\Omega}\left(\left(\frac{1}{\epsilon}\right)^{H_{2}(\min(1/\beta,1/2))}\right)=\tilde{\Omega}\left(\left(\frac{s}{\epsilon}\right)^{\frac{\beta\cdot
H_{2}(\min(1/\beta,1/2))}{\beta+1}}\right)$

the result follows.

To this end, suppose for the contrary, $A_{D}$ makes $q$ queries. Let
$S=\\{a^{(1)},\ldots,a^{(q)}\\}$ be the queries that $A_{D}$ makes. For every
$(I,J)\in W$ let $S_{I,J}=\\{a\in S|f_{I,J}(a)=1\\}$. Since for any two
distinct $(I_{1},J_{1}),(I_{2},J_{2})\in W$ we have $f_{I_{1},J_{1}}\cdot
f_{I_{2},J_{2}}=0$, the sets $\\{S_{I,J}\\}_{(I,J)\in W}$ are disjoint sets.

Let $f=f_{I^{\prime},J^{\prime}}$ be uniformly at random function in $C$. We
will show that, with probability at least $4/5$, $A_{D}$ fails to learn $f$,
which gives a contradiction. Since

$E_{(I,J)\in W}[|S_{I,J}|]=\frac{\sum_{(I,J)\in
W}|S_{I,J}|}{|W|}=\frac{q}{w}=\frac{1}{10},$

at least $(9/10)|W|$ of the $S_{I,J}$ are empty sets. Therefore, with
probability at least $9/10$, $S_{I^{\prime},J^{\prime}}$ is an empty set. In
other words, with probability at least $9/10$, the answers to the all the
queries are $0$. If the answers to all the queries are zero, then with
probability at most $1/10$, the algorithm can guess $I^{\prime},J^{\prime}$,
and therefore, the failure probability of the algorithm is at least $4/5$.
This proves the case $\beta>1$.

Now we prove the result for $0<\beta\leq 1$. By Lemma 12, we get the lower
bound $\Omega(s)$. Since

$s=\left(\frac{s}{\epsilon}\right)^{1/(\beta+1)}$

and for $0<\beta\leq 1$

$\frac{1}{\beta+1}\geq\frac{\beta\cdot H_{2}(\min(1/\beta,1/2))}{\beta+1}$

the result follows. ∎

##  5 An Improved Algorithm for Small $\beta$

LearnPoly$(f,\epsilon,s)$
Input: Black-box access to $f\in\mathbb{P}_{m,s}$ Output: A hypothesis
$h\in\mathbb{P}_{m,s}$ such that ${\bf Pr}[h=f]\geq 1-\epsilon$. 1.
$h\leftarrow 0$; $\ell\leftarrow 0$; 2. Repeat $s$ times 3. $t\leftarrow 0$;
find$\leftarrow False$; 4. While $t<m:=\frac{8}{7\epsilon}\ln({128s})$ and
(NOT find) Do 5. $t\leftarrow t+1$; 6. Draw uniformly at random
$a\in\\{0,1\\}^{m}$; 7. If $(f+h)(a)=1$ Then 8. $\ell\leftarrow\ell+1;$ If
$\ell=v:=(64s)\ln(128s)$ Then Output $0$ and halt; 9. $a\leftarrow$
FindMonomial$((f+h)(a*x),\log(s/\epsilon)+3,1/(128s))$ 10. If
$wt(a)\leq\log(s/\epsilon)+3$ Then 11. $a\leftarrow$
FindMonomial$((f+h)(a*x),\log(s/\epsilon)+3,1/(128s))$; 12. find$\leftarrow
True$; 13. $h\leftarrow h+\prod_{a_{i}=1}x_{i}$; 14. If (NOT find) Then Output
$h$ and halt

Figure 3: A learning algorithm for $\mathbb{P}_{m,s}$.

In this section, we prove the following.

######  Theorem 6.

Let $\epsilon=1/s^{\beta}$. There is a proper learning algorithm for
$s$-sparse polynomial with probability of success at least $2/3$ that makes

$q_{U}^{\prime}=\left(\frac{s}{\epsilon}\right)^{\gamma^{\prime}(\beta)}+O\left(s\left(\log\frac{1}{\epsilon}\right)\log
n\right)$

queries and runs in time $O(q_{U}^{\prime}\cdot n)$, where

$\gamma^{\prime}(\beta)=\max\left(1,\frac{1}{\beta+1}+H_{2}\left(\min\left(\frac{1}{\beta+1},\frac{1}{2}\right)\right)\right).$

In particular,

  1. 1.

The query complexity of this algorithm, $q_{U}^{\prime}$ is better than the
algorithm in Theorem 4, $q_{U}$, for $\beta<6.219$.

  2. 2.

$q_{U}^{\prime}=\tilde{O}(s/\epsilon)$ for $\beta\geq 3.404$

  3. 3.

The query complexity $\min(q_{U},q_{U}^{\prime})$ is better than the best-
known query complexity (which is
$s^{2}/\epsilon=(s/\epsilon)^{(2+\beta)/(1+\beta)}$) for $\beta>1$ and is
equal to $O(s^{2}/\epsilon)$ for $0\leq\beta\leq 1$.

In the following table, we compare between $\gamma^{\prime}(\beta)$ in Theorem
6 with $\gamma(\beta)$ in Theorem 1.

$\beta$ | $\gamma(\beta)$ | $\gamma^{\prime}(\beta)$
---|---|---
1 | 2.617 | 1.5
2 | 1.961 | 1.1252
3 | 1.582 | 1.1061
4 | 1.336 | 1
5 | 1.157 | 1
6 | 1.025 | 1
7 | 0.921 | 1
8 | 0.839 | 1
9 | 0.77 | 1
10 | 0.713 | 1

We first prove

######  Lemma 14.

Let $\epsilon=1/s^{\beta}$. There is a proper learning algorithm for
$\mathbb{P}_{m,s}$ with probability of success at least $15/16$, makes

$Q=\tilde{O}\left(\frac{s}{\epsilon}\right)+\left(\frac{s}{\epsilon}\right)^{\frac{1}{\beta+1}+H_{2}\left(\min\left(\frac{1}{\beta+1},\frac{1}{2}\right)\right)(1+o_{s}(1))}\log
m$

queries, and runs in time $O(Q\cdot m)$.

###### Proof.

Consider the algorithm LearnPoly in Figure 3. The algorithm uses the procedure
FindMonomial $(f,d,\delta)$ that, for $f\in\mathbb{P}_{n,d,s}$, with
probability at least $1-\delta$, returns an assignment $a$ such that
$f(a*x)=\Pi_{a_{i}=1}x_{i}$ is a monomial of $f$. If
$f\not\in\mathbb{P}_{n,d,s}$ and $f\not=0$ then it returns an assignment $a$
such that $f(a*x)\not=0$, but, $\Pi_{a_{i}=1}x_{i}$ is not necessarily a
monomial of $f$. Also, if $a$ satisfies a monomial of $f(x)$ of size at most
$\log(s/\epsilon)+3$ and does not satisfy any monomial of size more than
$\log(s/\epsilon)+3$ then FindMonomial$(f(a*x),\log(s/\epsilon)+3,\delta)$,
with probability at least $1-\delta$, returns an assignment that corresponds
to a monomial of size at most $\log(s/\epsilon)+3$. This is because, for such
an $a$, $f(a*x)$ contains no monomials of size greater than
$\log(s/\epsilon)+3$. See the algorithm FindMonomial in Figure 2 and Lemma 10.

The Repeat-loop in step 2 is executed $s$ times, and at each iteration, the
algorithm, whp, either adds to $h$ a monomial of $f$ of size at most
$\log(s/\epsilon)+3$ that is not in $h$ or detects that ${\bf
Pr}[(f+h)(x)\not=1]={\bf Pr}[f(x)\not=h(x)]\leq\epsilon$. In the While-loop in
step 4, $h$, whp, contains some monomials of $f$. The algorithm searches for
an assignment $a$ that satisfies $f+h$, i.e., an assignment that satisfies a
monomial of $f$ that is not in $h$. If such an assignment is found, step 9
uses the procedure FindMonomial to, whp, finds a new monomial of $f$ of size
at most $\log(s/\epsilon)+3$. This procedure runs again in step 11. If such a
monomial is found, it is added to $h$ in step 13.

We call FindMonomial twice because when in step 7 a positive assignment $a$ is
found for $f+h$, it may happen that $a$ satisfies some monomials of size more
than $\log(s/\epsilon)+3$. In that case, we cannot guarantee that the first
call returns a monomial of $f+h$ of size at most $\log(s/\epsilon)+3$. See the
first paragraph in this proof.

Now, the algorithm may fail if one of the following events occurs.

  1. 1.

$A_{1}$: In at least one of the (at most $s$) executions of FindMonomial in
step 11, the procedure fails to return an assignment $a$ such that
$\prod_{a_{i}=1}x_{i}$ is a monomial of $f$ of size at most
$\log(s/\epsilon)+3$.

  2. 2.

$A_{2}$: In one of (the at most $s$) iterations in the Repeat-loop we have
${\bf Pr}[f(x)\not=h(x)]>\epsilon$ and for $m=(8/(7\epsilon))\ln(128s)$
assignments $a$ drawn uniformly at random, no one satisfies a monomial of
$F(x):=f(x)+h(x)$ of size at most $\log(s/\epsilon)+3$ and does not satisfy
any monomial of size more than $\log(s/\epsilon)+3$.

Notice that when $A_{2}$ occurs, the variable “find” remains “False”, and the
algorithm returns $h$ that is $\epsilon$-far from $f$.

  3. 3.

$A_{3}$: For one of the assignments $a$ that satisfies a monomial of
$F(x):=f(x)+h(x)$ of size at most $\log(s/\epsilon)+3$ and does not satisfy
any monomial of $F$ of size more than $\log(s/\epsilon)+3$, FindMonomial in
step 9 fails to output an assignment of weight at most $\log(s/\epsilon)+3$.

  4. 4.

$A_{4}$: The command FindMonomial in step 9 runs more than $v$ times. Notice
that the variable $\ell$ counts the number of times that the command
FindMonomial in step 9 runs. If $\ell=v$ then the algorithm outputs an
arbitrary $h=0$.

Consider the event $A_{1}$. Let $F=f+h$. Consider steps 10-13. The assignment
$a$ satisfies $F(a*x)\not=0$. This follows from steps 7 and 9. Also, by step
10, $wt(a)\leq\log(s/\epsilon)+3$ and therefore $F(a*x)$ has at most
$\log(s/\epsilon)+3$ relevant variables and all its monomials are of size at
most $\log(s/\epsilon)+3$. By Lemma 10, with probability at least
$1-1/(128s)$, FindMonomial$(F(a*x),\log(s/\epsilon)+3,1/(128s))$ returns an
assignment $b$ such that $M=\prod_{b_{i}=1}x_{i}$ is a monomial of $F(a*x)$.
Since the monomials of $F(a*x)$ are monomials of $F(x)$, the claim follows.
This is for one call to FindMonomial. Since each time we call FindMonomial,
with probability at least $1-1/(128s)$, we find a new monomial of $f$, and
since this command runs at most $s$ time, we have ${\bf Pr}[A_{1}]\leq 1/128$.

Consider the events $A_{2}$ and $A_{3}$. In step 6, the algorithm draws an
assignment $a$ uniformly at random. The probability that $F(a)=1$ is at least
$\epsilon$. The probability that $a$ satisfies at least one of the monomials
in $F$ of size more than $\log(s/\epsilon)+3$ is at most
$s2^{-\log(s/\epsilon)+3}\leq\epsilon/8$. Therefore, the probability that
$F(a)=1$ and $a$ does not satisfy any one of the monomials of size more than
$\log(s/\epsilon)+3$ is at least $7\epsilon/8$. Thus, with probability at
least $7\epsilon/8$, $F(a)=1$ and $F(a*x)$ is of degree $\log(s/\epsilon)+3$
polynomial. The probability that the algorithm fails to find such an $a$ in
the While-loop is

$(1-7\epsilon/8)^{\frac{8}{7\epsilon}\ln{128s}}\leq\frac{1}{128s}.$

Once such an $a$ is found, by Lemma 10, with probability at least
$1-1/(128s)$, FindMonomial$(F(a*x),\log(s/\epsilon)+3,1/(128s))$ in step 9
returns an assignment $a$ of weight at most $\log(s/\epsilon)+3$. In that
case, the algorithm adds a monomial to $h$, finishes the While-loop, and
returns to the Repeat-loop. Therefore, the probability of $A_{2}\vee A_{3}$ is
at most $1/64$.

Before we consider $A_{4}$, we will first assume that the events
$\bar{A}_{1},\bar{A}_{2}$, and $\bar{A}_{3}$ occur and find an upper bound for
the expected number of times that step 9 is executed.

Let $N$ be a random variable representing the number of times that step 9 is
executed. Let $N_{1}$ and $N_{2}$ be the number of times it is executed while
${\bf Pr}[F(x)=1]\geq\epsilon$ and, ${\bf Pr}[F(x)=1]<\epsilon$, respectively.
Obviously, ${\bf E}[N]={\bf E}[N_{1}]+{\bf E}[N_{2}]$. We will now upper bound
${\bf E}[N_{1}]$ and ${\bf E}[N_{2}]$.

Consider the case when ${\bf Pr}[F(x)=1]\geq\epsilon$. It is well known (and
easy to prove) that

${\bf E}[N_{1}]=\sum_{\nu=1}^{\infty}{\bf Pr}[N_{1}\geq\nu].$

Let $X_{i}$, $i\geq 1$, be an indicator random variable that is equal to $0$
if, at the $i$th time that steps 8-10 are executed (i.e., $i$th time that
$F(a)=1$ in step 7), both commands in steps 9 and 11 are executed and $1$ if
only the command in step 9 is executed. Let $W(a)$ be the event that, for a
uniform at random assignment $a$, no monomial of $f$ of size more than
$\log(s/\epsilon)+3$ satisfies $a$. If $F(a)=1$ and $W(a)$ occurs then,
assuming $\bar{A}_{1},\bar{A}_{2}$ and $\bar{A}_{3}$ occur, the command in
step 9 outputs an assignment of weight at most $\log(s/\epsilon)+3$ and then
the command in step 11 is also executed. Therefore,

$\displaystyle{\bf E}[X_{i}]$ $\displaystyle\leq$ $\displaystyle 1-{\bf
Pr}[W(a)|F(a)=1]$ $\displaystyle\leq$ $\displaystyle{\bf Pr}[\neg
W(a)|F(a)=1]$ $\displaystyle\leq$ $\displaystyle\frac{{\bf Pr}[\neg
W(a)]}{{\bf Pr}[F(a)=1]}$ $\displaystyle\leq$
$\displaystyle\frac{s2^{-(\log(s/\epsilon)+3)}}{\epsilon}=\frac{1}{8}.$

Notice that this bound is independent of $X_{i-1},\ldots,X_{1}$. That is,
${\bf Pr}[X_{i}=1|X_{i-1},\ldots,X_{1}]\leq 1/8$. Since the command in step 11
is executed at most $s$ times, the event $N_{1}\geq\nu$ implies the event
$X_{1}+\cdots+X_{\nu}\geq\nu-s$. By the generalized Chernoff’s bound, [22,
21], for $\nu\geq 4s$, we have

${\bf Pr}[N_{1}\geq\nu]\leq{\bf
Pr}\left[X_{1}+\cdots+X_{\nu}\geq\frac{\nu-s}{\nu}\nu\right]\leq e^{-\nu
D((\nu-s)/\nu\|1/8)}\leq e^{-2\nu((\nu-s)/\nu-1/8)^{2}}\leq e^{-\nu/2}.$

Therefore

${\bf E}[N_{1}]=\sum_{\nu=1}^{\infty}{\bf Pr}[N_{1}\geq\nu]\leq
4s+\sum_{\nu=4s+1}^{\infty}e^{-\nu/2}\leq 4s+1.$

To upper bound ${\bf E}[N_{2}]$, consider now the case when ${\bf
Pr}[F(x)=1]<\epsilon$. Since the Repeat-loop with the While-loop runs at most
$r=(8s/(7\epsilon))\log(128s)$ times and in each iteration the probability
that step 9 is executed is ${\bf Pr}[F(x)=1]<\epsilon$, the expected number of
times the algorithm executes the command in step 9 is at most

${\bf E}[N_{2}]=\epsilon r=\frac{8s}{7}\log({128s}).$

Therefore,

${\bf E}[N]\leq\frac{8s}{7}\log({128s})+4s+1.$

Therefore, By Markov’s bound

${\bf Pr}[A_{4}]={\bf Pr}\left[N\geq 64s\ln(128s)\right]\leq\frac{1}{32}.$

Now

$\displaystyle{\bf Pr}[A_{1}\vee A_{2}\vee A_{3}\vee A_{4}]$
$\displaystyle\leq$ $\displaystyle{\bf Pr}(A_{1})+{\bf
Pr}(A_{2}|\bar{A}_{1})+{\bf Pr}(A_{3}|\bar{A}_{1}\wedge\bar{A}_{2})+{\bf
Pr}(A_{4}|\bar{A}_{1}\wedge\bar{A}_{2}\wedge\bar{A}_{3})$ $\displaystyle\leq$
$\displaystyle 1/16.$

This completes the correctness of the algorithm.

Now for the query complexity of the algorithm, we have the following.

  1. 1.

The query complexity of step 7 is $\tilde{O}(s/\epsilon)$.

This is because we have two loops in the algorithm. The Repeat-loop runs at
most $s$ iterations, and the While-loop at most $(8/(7\epsilon))\ln(128s)$
iterations.

  2. 2.

The query complexity of step 11 is

$q:=\left(\left(\frac{s}{\epsilon}\right)^{\frac{1}{\beta+1}+H_{2}\left(\min\left(\frac{1}{\beta+1},\frac{1}{2}\right)\right)(1+o_{s}(1))}\log
m\right)$

This follows from the fact that step 11 is executed at most $s$ times. By
Lemma 10, for $d=\log(s/\epsilon)+3$, the query complexity of this step is

$q=O\left(s2^{dH_{2}\left(\min\left(\frac{\lfloor\log
s\rfloor+3}{d},\frac{1}{2}\right)\right)}d\log
m\right)=\left(\left(\frac{s}{\epsilon}\right)^{\frac{1}{\beta+1}+H_{2}\left(\min\left(\frac{1}{\beta+1},\frac{1}{2}\right)\right)(1+o_{s}(1))}\log
m\right).$

  3. 3.

The query complexity of step 9 is $v=\tilde{O}(q)$.

This completes the proof. ∎

We are now ready to prove Theorem 6.

###### Proof.

The algorithm first takes a $(1-1/(64s\log(2s/\epsilon)))$-zero projection
$g=f(z_{1},\ldots,z_{n})$ of $f$. The probability that some monomial of $f$ of
size at most $\log(2s/\epsilon)$ is not of $g$ is less than

$1-\left(1-\frac{1}{64s\log(2s/\epsilon)}\right)^{s\log(2s/\epsilon)}\leq\frac{1}{64}.$

The probability that $g$ has a monomial of size
$d:=64s\log(2s/\epsilon)\ln(64s)$ is at most

$s\left(1-\frac{1}{64s\log(2s/\epsilon)}\right)^{64s\log(2s/\epsilon)\ln(64s)}\leq
se^{-\ln(64s)}\leq\frac{1}{64}.$

Therefore, with probability at least $31/32$, $g$ is a degree-$d$ $s$-sparse
polynomial and

$\displaystyle{\bf Pr}[f(x)\not=g(x)]\leq
se^{-\log(2s/\epsilon)}=\frac{\epsilon}{2}.$ (10)

In particular, with probability at least $31/32$, $g$ contains at most
$ds=64s^{2}\log(2s/\epsilon)\ln(64s)$ relevant variables.

The algorithm then continues as in Lemma 9. It draws uniformly at random a map
$\phi:[n]\to[m]$ where $m=16(ds)^{2}$, and defines
$G(x_{1},\ldots,x_{m})=g(x_{\phi(1)},\ldots,x_{\phi(n)})$ and then learns $G$
using the algorithm in Lemma 14 with accuracy $\epsilon/2$. The probability
that different relevant variables of $f$ are mapped by $\phi$ into different
variables of $G$ is

$\displaystyle 1-\frac{(ds)^{2}}{2m}=\frac{31}{32}.$ (11)

The algorithm in Lemma 14 learns a hypothesis $H(x_{1},\ldots,x_{m})$ that
contains some of the monomials of size at most $\log(2s/\epsilon)+3$ of $G$
and, with probability at least $15/16$, ${\bf Pr}[H\not=G]\leq\epsilon/2$.

Then for every relevant variable $x_{i}$ of $H$, $i\in[m]$ it finds two
assignments $a,b\in\\{0,1\\}^{m}$ that differ only in the $i$th coordinate and
$G(a)\not=G(b)$. Here, we cannot use Lemma 8 (as we did in Lemma 9) because we
have not learned $G$ but $H$ that is $\epsilon/2$-close to $G$. To find such
assignments, we take any monomial $M=x_{i_{1}}\cdots x_{i_{r}}$ of $H$ that
contains $x_{i}$. Let $G_{M}$ be $G$ where we substitute zero in every
variable $x_{j}$, $j\not\in\\{i_{1},\ldots,i_{r}\\}$. Since the monomials of
$H$ are also monomials of $G$, then $G_{M}\not=0$ and $x_{i}$ is a relevant
variable of $G_{M}$. Also, since $H$ contains only monomials of degree
$\log(2s/\epsilon)+3$, $G_{M}$ does too. Then to get the two assignments, we
run Test$(G_{M},G_{M}^{\prime},1/(32m))$ where $G_{M}^{\prime}$ is $G_{M}$
with the substitution of $x_{i}=0$.

Then using the algorithm in Lemma 7, we learn $g(\pi^{(i,a)})$ where

$\pi^{(i,a)}_{j}=\left\\{\begin{array}[]{ll}a_{\phi(j)}&\phi(j)\not=i\\\
x_{j}&\phi(j)=i\end{array}\right..$

Then we return $H(y_{1},\ldots,y_{m})$ where $y_{i}=x_{j}$ if $x_{i}$ is a
relevant variable of $G$, and $g(\pi^{(i,a)})\in\\{x_{j},\bar{x}_{j}\\}$ and
$y_{i}=0$ otherwise. We now claim that, with probability at least $15/16$,

$\displaystyle{\bf Pr}[H(y_{1},\ldots,y_{m})=g(x)]\leq\epsilon/2.$ (12)

The proof of this claim is the same as Lemma 9.

Now, by (10), (11), (12), and the probability of success at least $31/32$ of
the Test calls, with probability at least $1-(1/16+1/32+1/32+1/32)>2/3$ we
have ${\bf Pr}[H(y_{1},\ldots,y_{m})=f(x)]\leq\epsilon.$

Now for the query complexity. By Lemma 14, the query complexity of learning
$G$ is

$\displaystyle
Q=\tilde{O}\left(\frac{s}{\epsilon}\right)+\left(\frac{s}{\epsilon}\right)^{\frac{1}{\beta+1}+H_{2}\left(\min\left(\frac{1}{\beta+1},\frac{1}{2}\right)\right)(1+o_{s}(1))}\log
m=\tilde{O}\left(\frac{s}{\epsilon}\right)+\left(\frac{s}{\epsilon}\right)^{\frac{1}{\beta+1}+H_{2}\left(\min\left(\frac{1}{\beta+1},\frac{1}{2}\right)\right)(1+o_{s}(1))}.$
(13)

We now find the query complexity of finding the relevant variables. The number
of relevant variables of $H$ is at most $v=(\log(2s/\epsilon)+3)s$. For each
variable we run Test that by, Lemma 5, takes

$q=2^{H_{2}\left(\min\left(\frac{\lfloor\log
s\rfloor+1}{\log(2s/\epsilon)+3}\right),\frac{1}{2}\right)(\log(2s/\epsilon)+3)}\ln{(32m)}=\left(\frac{s}{\epsilon}\right)^{H_{2}\left(\min\left(\frac{1}{\beta+1},\frac{1}{2}\right)\right)(1+o_{s}(1))}$

queries. So the total number of queries for all the calls is

$\displaystyle
qv=\left(\frac{s}{\epsilon}\right)^{\frac{1}{\beta+1}+H_{2}\left(\min\left(\frac{1}{\beta+1},\frac{1}{2}\right)\right)(1+o_{s}(1))}.$
(14)

Then the query of the searches is

$\displaystyle v\log n=\tilde{O}(s)\left(\log\frac{1}{\epsilon}\right)\log n.$
(15)

By (13), (14), and (15), the result follows. ∎

## References

  * [1] Dana Angluin.  Queries and concept learning.  Machine Learning, 2(4):319–342, 1987.
  * [2] Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, and Stefano Varricchio.  Learning functions represented as multiplicity automata.  J. ACM, 47(3):506–530, 2000.  doi:10.1145/337244.337257.
  * [3] Francesco Bergadano, Nader H. Bshouty, and Stefano Varricchio.  Learning multivariate polynomials from substitution and equivalence queries.  Electron. Colloquium Comput. Complex., (8), 1996.  URL: https://eccc.weizmann.ac.il/eccc-reports/1996/TR96-008/index.html.
  * [4] Laurence Bisht, Nader H. Bshouty, and Hanna Mazzawi.  On optimal learning algorithms for multiplicity automata.  In Gábor Lugosi and Hans Ulrich Simon, editors, Learning Theory, 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 22-25, 2006, Proceedings, volume 4005 of Lecture Notes in Computer Science, pages 184–198. Springer, 2006.  doi:10.1007/11776420\\_16.
  * [5] Eric Blais, Joshua Brody, and Kevin Matulef.  Property testing lower bounds via communication complexity.  In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pages 210–220, 2011.  doi:10.1109/CCC.2011.31.
  * [6] Avrim Blum and Mona Singh.  Learning functions of _k_ terms.  In Mark A. Fulk and John Case, editors, Proceedings of the Third Annual Workshop on Computational Learning Theory, COLT 1990, University of Rochester, Rochester, NY, USA, August 6-8, 1990, pages 144–153. Morgan Kaufmann, 1990.  URL: http://dl.acm.org/citation.cfm?id=92620.
  * [7] Manuel Blum, Michael Luby, and Ronitt Rubinfeld.  Self-testing/correcting with applications to numerical problems.  J. Comput. Syst. Sci., 47(3):549–595, 1993.  doi:10.1016/0022-0000(93)90044-W.
  * [8] Nader H. Bshouty.  On learning multivariate polynomials under the uniform distribution.  Inf. Process. Lett., 61(6):303–309, 1997.  doi:10.1016/S0020-0190(97)00021-5.
  * [9] Nader H. Bshouty.  Almost optimal testers for concise representations.  Electronic Colloquium on Computational Complexity (ECCC), 26:156, 2019.  URL: https://eccc.weizmann.ac.il/report/2019/156.
  * [10] Nader H. Bshouty and Oded Goldreich.  On properties that are non-trivial to test.  Electronic Colloquium on Computational Complexity (ECCC), 13, 2022\.  URL: https://eccc.weizmann.ac.il/report/2022/013/.
  * [11] Nader H. Bshouty and Yishay Mansour.  Simple learning algorithms for decision trees and multivariate polynomials.  SIAM J. Comput., 31(6):1909–1925, 2002.  doi:10.1137/S009753979732058X.
  * [12] Sourav Chakraborty, David García-Soriano, and Arie Matsliah.  Efficient sample extractors for juntas with applications.  In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, pages 545–556, 2011.  doi:10.1007/978-3-642-22006-7\\_46.
  * [13] Michael Clausen, Andreas W. M. Dress, Johannes Grabmeier, and Marek Karpinski.  On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields.  Theor. Comput. Sci., 84(2):151–164, 1991.  doi:10.1016/0304-3975(91)90157-W.
  * [14] Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, and Andrew Wan.  Testing for concise representations.  In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 549–558, 2007.  doi:10.1109/FOCS.2007.32.
  * [15] Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, and Andrew Wan.  Efficiently testing sparse _GF_(2) polynomials.  Algorithmica, 61(3):580–605, 2011.  doi:10.1007/s00453-010-9426-9.
  * [16] Arne Dür and Johannes Grabmeier.  Applying coding theory to sparse interpolation.  SIAM J. Comput., 22(4):695–704, 1993.  doi:10.1137/0222046.
  * [17] Paul Fischer and Hans Ulrich Simon.  On learning ring-sum-expansions.  SIAM J. Comput., 21(1):181–192, 1992.  doi:10.1137/0221014.
  * [18] Oded Goldreich, editor.  Property Testing - Current Research and Surveys, volume 6390 of Lecture Notes in Computer Science.  Springer, 2010.  doi:10.1007/978-3-642-16367-8.
  * [19] Oded Goldreich.  Introduction to Property Testing.  Cambridge University Press, 2017.  URL: http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=9781107194052, doi:10.1017/9781108135252.
  * [20] Lisa Hellerstein and Rocco A. Servedio.  On PAC learning algorithms for rich boolean function classes.  Theor. Comput. Sci., 384(1):66–76, 2007.  doi:10.1016/j.tcs.2007.05.018.
  * [21] Russell Impagliazzo and Valentine Kabanets.  Constructive proofs of concentration bounds.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010\. Proceedings, pages 617–631, 2010.  doi:10.1007/978-3-642-15369-3\\_46.
  * [22] Alessandro Panconesi and Aravind Srinivasan.  Randomized distributed edge coloring via an extension of the chernoff-hoeffding bounds.  SIAM J. Comput., 26(2):350–368, 1997.  doi:10.1137/S0097539793250767.
  * [23] Dana Ron.  Property testing: A learning theory perspective.  Foundations and Trends in Machine Learning, 1(3):307–402, 2008\.  doi:10.1561/2200000004.
  * [24] Dana Ron.  Algorithmic and analysis techniques in property testing.  Foundations and Trends in Theoretical Computer Science, 5(2):73–205, 2009.  doi:10.1561/0400000029.
  * [25] Ron M. Roth and Gyora M. Benedek.  Interpolation and approximation of sparse multivariate polynomials over GF(2).  SIAM J. Comput., 20(2):291–314, 1991.  doi:10.1137/0220019.
  * [26] Ronitt Rubinfeld and Madhu Sudan.  Robust characterizations of polynomials with applications to program testing.  SIAM J. Comput., 25(2):252–271, 1996.  doi:10.1137/S0097539793255151.
  * [27] Mert Saglam.  Near log-convexity of measured heat in (discrete) time and consequences.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 967–978, 2018\.  doi:10.1109/FOCS.2018.00095.
  * [28] Robert E. Schapire and Linda Sellie.  Learning sparse multivariate polynomials over a field with queries and counterexamples.  J. Comput. Syst. Sci., 52(2):201–213, 1996.  doi:10.1006/jcss.1996.0017.
  * [29] Leslie G. Valiant.  A theory of the learnable.  Commun. ACM, 27(11):1134–1142, 1984.  doi:10.1145/1968.1972.