On learning monotone DNF under product distributions.
We show that the class of monotone 2<sup>O(log<i>n</i>)</sup>-term DNF formulae can be PAC learned in polynomial time under the uniform distribution from random examples only. This is an exponential improvement over the best previous polynomial-time algorithms in this model, which could learn monotone o(log<sup>2</sup> <i>n</i>)-term DNF. We also show that various classes of small constant-depth circuits which compute monotone functions are PAC learnable in polynomial time under the uniform distribution. All of our results extend to learning under any constant-bounded product distribution.
Introduction
A disjunctive normal form formula, or DNF, is a disjunction of conjunctions of Boolean literals.
The size of a DNF is the number of conjunctions (also known as terms) which it contains. In a
seminal 1984 paper [26] Valiant introduced the distribution-free model of Probably Approximately
Correct (PAC) learning from random examples and posed the question of whether polynomial-size
DNF are PAC learnable in polynomial time. Over the past fifteen years the DNF learning
problem has been widely viewed as one of the most important - and challenging - open questions
in computational learning theory. This paper substantially improves the best previous results for
a well-studied restricted version of the DNF learning problem.
1.1 Previous Work
The lack of progress on Valiant's original question - are polynomial-size DNF learnable from random
examples drawn from an arbitrary distribution in polynomial time? - has led many researchers to
study restricted versions of the DNF learning problem. As detailed below, the restrictions which
have been considered include:
ffl allowing the learner to make membership queries for the value of the target function at points
selected by the learner;
ffl requiring that the learner succeed only under restricted distributions on examples, such as
the uniform distribution, rather than all distributions;
ffl requiring that the learner succeed only for restricted subclasses of DNF formulae such as DNF
with a bounded number of terms.
A SAT-k DNF is a DNF in which each truth assignment satisfies at most k terms. Khardon [19]
gave a polynomial time membership query algorithm for learning polynomial-size SAT-1 DNF under
the uniform distribution; this result was later strengthened by Blum et al. [3] to SAT-k DNF for any
constant k: Bellare [5] gave a polynomial time membership query algorithm for learning O(log n)-
term DNF under the uniform distribution (a somewhat more general result was given by Blum
and Rudich [6]). Mansour [23] gave a n O(log log n) -time membership query algorithm which learns
arbitrary polynomial-size DNF under the uniform distribution. In a celebrated result, Jackson
[15] gave a polynomial-time membership query algorithm for learning polynomial-size DNF under
constant-bounded product distributions. His algorithm, the efficiency of which was subsequently
improved by several authors [8, 20], is the only known polynomial time algorithm for learning the
unrestricted class of polynomial size DNF in any nontrivial learning model.
In the standard PAC model without membership queries positive results are known for various
subclasses of DNF under restricted distributions. A read-k DNF is one in which each variable
appears at most k times. Kearns, Li, Pitt and Valiant [17, 18] showed that read-once DNF are
PAC learnable under the uniform distribution in polynomial time. Hancock [12] extended this
result to read-k DNF for any constant k: Verbeurgt [27] gave an algorithm for learning arbitrary
polynomial-size DNF under the uniform distribution in time n O(log n) ; and Linial et al. [22] gave an
algorithm for learning any AC 0 circuit (constant depth, polynomial size, unbounded fanin AND/OR
gates) under the uniform distribution in n poly(log n) time.
A monotone DNF is a DNF with no negated variables. Hancock and Mansour [13] gave a
polynomial time algorithm for learning monotone read-k DNF under constant-bounded product
distributions. Verbeurgt [28] gave a polynomial time uniform distribution algorithm for learning
poly-disjoint one-read-once monotone DNF and read-once factorable monotone DNF. Kucera et
al. [21] gave a polynomial-time algorithm which learns monotone k-term DNF under the uniform
distribution using hypotheses which are monotone k-term DNF. This was improved by Sakai and
Maruoka [25] who gave a polynomial-time algorithm for learning monotone O(log n)-term DNF
under the uniform distribution using hypotheses which are monotone O(log n)-term DNF. Subsequently
Bshouty and Tamon [9] gave a polynomial-time algorithm for learning a class which includes
monotone O(log 2 n=(log log n) 3 )-term DNF under constant-bounded product distributions.
1.2 Our Results
We give a simple polynomial time algorithm for learning monotone 2 O(
log n) -term DNF under the
uniform distribution. This is the first polynomial time algorithm which uses only random examples
drawn from a nontrivial distribution and successfully learns monotone DNF formulae with more
than a polylogarithmic number of terms. We also show that essentially the same algorithm learns
various classes of small constant-depth circuits which compute monotone functions on few variables.
Both results extend to learning under any constant-bounded product distribution.
Our algorithm combines ideas from Linial et al.'s influential paper [22] on learning AC 0 functions
using the Fourier transform and Bshouty and Tamon's paper [9] on learning monotone functions
using the Fourier transform. By analyzing the Fourier transform of AC 0 functions, Linial et al.
showed that almost all of the Fourier "power spectrum" of any AC 0 function is contained in "low"
Fourier coefficients, i.e. coefficients which correspond to small subsets of variables. Their learning
algorithm estimates each low Fourier coefficient by sampling and constructs an approximation to
f using these estimated Fourier coefficients. If c is the size bound for low Fourier coefficients, then
since there are
c
coefficients corresponding to subsets of c variables the algorithm requires
roughly n c time steps. Linial et al. showed that for AC 0 circuits c is essentially poly(log n); this
result was later sharpened for DNF formulae by Mansour [23].
Our algorithm extends this approach in the following way: Let C ae AC 0 be a class of Boolean
functions which we would like to learn. Suppose that C has the following properties:
1. For every f 2 C there is a set S f of "important" variables such that almost all of the power
spectrum of f is contained in Fourier coefficients corresponding to subsets of
2. There is an efficient algorithm which identifies the set S f from random examples.
(Such an algorithm, which we give in Section 3.1, is implicit in [9] and requires only that f be
monotone.) We can learn an unknown function f from such a class C by first identifying the set
estimating the low Fourier coefficients which correspond to small subsets of S f and using
these estimates to construct an approximation to f: To see why this works, note that since f is in
almost all of the power spectrum of f is in the low Fourier coefficients; moreover, property (1)
implies that almost all of the power spectrum of f is in the Fourier coefficients which correspond
to subsets of Consequently it must be the case that almost all of the power spectrum of f is
in low Fourier coefficients which correspond to subsets of S f : Thus in our setting we need only
estimate the roughly
c
Fourier coefficients which correspond to "small" subsets of variables in
then this is much more efficient than estimating all
c
low Fourier coefficients.
In Section 2 we formally define the learning model and give some necessary facts about Fourier
analysis over the Boolean cube. In Section 3 we give our learning algorithm for the uniform
distribution, and in Section 4 we describe how the algorithm can be modified to work under any
constant-bounded product distribution.
Preliminaries
We write [n] to denote the set ng and use capital letters for subsets of [n]: We write
jAj to denote the number of elements in A: Barred lowercase letters denote bitstrings, i.e.
In this paper Boolean circuits are composed of AND/OR/NOT gates where
AND and OR gates have unbounded fanin and negations occur only on inputs. We view Boolean
functions on n variables as real valued functions which map f0; 1g n to f\Gamma1; 1g: A Boolean function
changing the value of an input bit from 0 to 1 never causes
the value of f to change from 1 to \Gamma1:
If D is a distribution and f is a Boolean function on f0; 1g n ; then as in [9, 13] we say that the
influence of x i on f with respect to D is the probability that f(x) differs from f(y); where y is x
with the i-th bit flipped and x is drawn from D: For ease of notation let f i;0 denote the function
obtained from f by fixing x i to 0 and let f i;1 be defined similarly. We thus have
I D;i
For monotone f this can be further simplified to
I D;i
We use the following version of Chernoff bounds on sums of independent random variables [11]:
Theorem 1 Let x independent identically distributed random variables with E[x i
implies that Pr
2.1 The Learning Model
Our learning model is a distribution-specific version of Valiant's Probably Approximately Correct
model [26] and has been studied by many researchers, e.g. [3, 5, 8, 9, 10, 13, 15, 19, 21, 22,
23, 27, 28]. Let C be a class of Boolean functions over f0; 1g n ; let D be a probability distribution
over f0; 1g n ; and let f 2 C be an unknown target function. A learning algorithm A for C takes as
input an accuracy parameter confidence parameter During its execution
the algorithm has access to an example oracle EX(f;D) which, when queried, generates a random
labeled example hx; f(x)i where x is drawn according to D: The learning algorithm outputs a
hypothesis h which is a Boolean function over f0; 1g n ; the error of this hypothesis is defined to be
We say that A learns C under D if for every f 2 C and
with probability at least outputs a hypothesis h which has error(h; f) - ffl:
2.2 The Discrete Fourier Transform
Let U denote the uniform distribution over f0; 1g n : The set of all real valued functions on f0; 1g n
may be viewed as a 2 n -dimensional vector space with inner product defined as
\Gamman
and norm defined as
hf; fi: Given any subset A ' [n]; the Fourier basis function -A :
defined by -A is the subset of [n] defined by i 2 X
It is well known that the 2 n basis functions -A (where A ranges over all subsets of [n]) form
an orthonormal basis for the vector space of real valued functions on f0; 1g n ; we refer to this basis
as the - basis. In particular, any function f can be uniquely expressed as
A
where the values -
are known as the Fourier coefficients of f with respect to the - basis. Since
the functions -A form an orthonormal basis, the value of -
is hf; -A i; also, by linearity we
have that f(x)
g(A))- A (x): Another easy consequence of orthonormality is
Parseval's identity
If f is a Boolean function then this value is exactly 1. Finally, if g is any real valued function on
f0; 1g n we have [9, 22]
Pr
U
where sign(z) takes value 1 if z - 0 and takes value 0:
3 Learning under Uniform Distributions
3.1
The following lemma, which is implicit in [9], gives an efficient algorithm for identifying the important
variables of a monotone Boolean function. We refer to this algorithm as FindVariables.
be a monotone Boolean function. There is an algorithm which
has access to EX(f;U); runs in poly(n; 1=ffl; log 1=ffi) time steps for all ffl; ffi ? 0; and with probability
at least outputs a set S f ' [n] such that
A:i2A
A:i2A
Proof: Kahn et al. ([16] Section have shown that
I U ;i
A:i2A
To prove the lemma it thus suffices to show that I U ;i (f) can be estimated to within accuracy ffl=4
with high probability. By Equation (1) from Section 2 this can be done by estimating E U [f i;1
and E U [f i;0 ]: Two applications of Chernoff bounds finish the proof: the first is to verify that with
high probability a large sample drawn from EX(f;U) contains many labeled examples which have
and many which have x and the second is to verify that a collection of many labeled
examples with x with high probability yields an accurate estimate of E U [f i;b ]:
3.2 The Learning Algorithm
Our learning algorithm, which we call LearnMonotone, is given below:
Use FindVariables to identify a set S f of important variables.
labeled examples hx from EX(f;U): For every A ' S f with
For every A such that jAj ? c or A 6' S f set ff A = 0:
ffl Output the hypothesis sign(g(x)); where
A ff A-A (x):
The algorithm thus estimates -
by sampling and constructs a hypothesis
using these approximate Fourier coefficients. The values of m and c and the parameter settings for
FindVariables are specified below.
3.3 Learning Monotone 2 O(
log n) -term DNF
be a monotone k-term DNF. The proof that algorithm LearnMonotone
learns f uses a DNF called f 1 to show that FindVariables identifies a small set of variables S f
and uses another DNF called f 2 to show that f can be approximated by approximating Fourier
coefficients which correspond to small subsets of
be the DNF which is obtained from f by removing every term which contains more than
log 32kn
ffl variables. Since there are at most k such terms each of which is satisfied by a random
example with probability less than ffl=32kn; we have Pr U [f(x)
(this argument was
first used by Verbeurgt [27]). Let R ' [n] be the set of variables which f 1 depends on; it is clear
that jRj - k log 32kn
since I U ;i (f 1
equation (3) from Section 3.1 implies
that -
Since f and f 1 are Boolean functions,
ffl=8n: By Parseval's identity we have
A
A'R
A6'R
A'R
A6'R
Thus
A6'R
consequently we have
A:i2A
We set the parameters of FindVariables so that with high probability
A:i2A
A:i2A
Inequalities (4) and (5) imply that S f ' R; so jS f j - k log 32kn
Furthermore, since A 6' S f implies
The following lemma is due to Mansour ([23] Lemma 3.2):
Lemma 3 Let f be a DNF with terms of size at most d: Then for all ffl ? 0
jAj?20d log(2=ffl)
One approach at this point is to use Mansour's lemma to approximate f by approximating the
Fourier coefficients of all subsets of S f which are smaller than 20d log(2=ffl); where
ffl is
the maximum size of any term in f 1 : However, this approach does not give a good bound because d is
too large. Instead we consider another DNF with smaller terms than f 1 which closely approximates
f: By using this stronger bound on term size in Mansour's lemma we get a better final result.
More precisely, let f 2 be the DNF obtained from f by removing every term which contains at
least log 32k
ffl variables. Let
log 8
implies that
Moreover, we have Pr U [f
U
A
Let ff A and g(x) be as defined in LearnMonotone. We have
A
where
To bound X; we observe that ff so by (7) we have
To bound Y; we note that ff
A
by inequalities (8) and (9) respectively.
It remains to bound Z =
As in Linial et al. [22] this sum can be
made less than ffl=4 by taking m sufficiently large so that with high probability each estimate ff A
differs from the true value -
f(A) by at most
straightforward Chernoff bound argument
shows that taking suffices.
Thus, we have Recalling our bounds on jS f j and c; we have proved:
Theorem 4 Under the uniform distribution, for any ffl; ffi ? 0; algorithm LearnMonotone learns
k-term monotone DNF in time polynomial in n; (k log kn
ffl and log(1=ffi):
Taking
log n) we obtain the following corollary:
Corollary 5 For any constant ffl algorithm LearnMonotone learns 2 O(
log n) -term monotone DNF
in poly(n; log(1=ffi)) time under the uniform distribution.
We note that Bshouty and Tamon's algorithm [9] for learning monotone O((log n) 2 =(log log n) 3 )-
term DNF also requires that ffl be constant in order to achieve poly(n) runtime.
3.4 Learning Small Constant-Depth Monotone Circuits on Few Variables
Let C be the class of depth d; size M circuits which compute monotone functions on r out of
variables. An analysis similar to that of the last section (but simpler since we do not need to
introduce auxiliary functions f 1 and f 2 ) shows that algorithm LearnMonotone can be used to learn
C: Instead of Mansour's lemma we use the main lemma of Linial et al. [22] which bounds the
Fourier spectrum of constant-depth circuits:
Lemma 6 Let f be a Boolean function computed by a circuit of depth d and size M and let c be
any integer. Then X
Taking in LearnMonotone we obtain:
Theorem 7 Fix d - 1 and let C be the class of depth d, size M circuits which compute monotone
functions on r out of n variables. Under the uniform distribution, for any ffl; ffi ? 0; algorithm
LearnMonotone learns class C in time polynomial in n; r (log(M=ffl)) d
and log(1=ffi):
One interesting corollary is the following:
Corollary 8 Fix d - 1 and let C be the class of depth d; size 2 O((log n) 1=(d+1) ) circuits which compute
monotone functions on 2 O((log n) 1=(d+1) ) variables. Then for any constant ffl algorithm LearnMonotone
learns class C in poly(n; log(1=ffi)) time.
While this class C is rather limited from the perspective of Boolean circuit complexity, from
a learning theory perspective it is fairly rich. We note that C strictly includes the class of depth
d; size 2 O((log n) 1=(d+1) ) circuits on 2 O((log n) 1=(d+1) ) variables which contain only unbounded fanin
AND/OR gates. This follows from results of Okol'nishnikova [24] and Ajtai and Gurevich [1] (see
also Section 3.6) which show that there are monotone functions which can be computed by AC 0
circuits but are not computable by AC 0 circuits which have no negations.
4 Learning under Product Distributions
A product distribution over f0; 1g n is characterized by parameters -
Such a distribution D assigns values independently to each variable, so for a 2 f0; 1g n we have
a
a
: The uniform distribution is a product distribution with each
1=2: The standard deviation of x i under a product distribution is oe
product
distribution D is constant-bounded if there is some constant c 2 (0; 1) independent of n such that
Throughout the rest
of this paper D denotes a product distribution.
Given a product distribution D we define a new inner product over the vector space of real
valued functions on f0; 1g n as
and a corresponding norm
We refer to this norm as the D-norm. For
let z Given A ' [n]; let OE A be defined as OE A
As noted by Bahadur
[4] and Furst et al. [10], the 2 n functions OE A form an orthonormal basis for the vector space of
real valued functions on f0; 1g n with respect to the D-norm, i.e. hOE A ; OE B i D is 1 if
otherwise. We refer to this basis as the OE basis. The following fact is useful:
Fact 9 ([4, 10]) The OE basis is the basis which would be obtained by Gram-Schmidt orthonormalization
(with respect to the D-norm) of the - basis performed in order of increasing jAj:
By the orthonormality of the OE basis, any real function on f0; 1g n can be uniquely expressed as
A
~
f(A)OE A (x) where ~
is the Fourier coefficient of A with respect to the OE
basis. Note that we write ~
for the OE basis Fourier coefficient and -
for the - basis Fourier
coefficient. Also by orthonormality we have Parseval's identity
~
which is 1 for Boolean f: Finally, for any real valued function g we have ([10] Lemma 10)
Pr
Furst et al. [10] analyzed the OE basis Fourier spectrum of AC 0 functions and gave product
distribution analogues of Linial et al.'s results on learning AC 0 circuits under the uniform distribu-
tion. In Section 4.1 we sharpen and extend some results from [10], and in Section 4.2 we use these
sharpened results together with techniques from [10] to obtain product distribution analogues of
our algorithms from Section 3.
4.1 Some OE Basis Fourier Lemmas
A random restriction ae p;D is a mapping from fx to f0; 1; \Lambdag where x i is mapped to   with
probability and to 0 with probability is a
Boolean function then fdae represents the function f(ae p;D (x)) whose variables are those x i which
are mapped to   and whose other x i are instantiated as 0 or 1 according to ae p;D :
The following is a variant of H-astad's well known switching lemma [14]:
D be a product distribution with parameters - i and fi as defined above, let f be a
each clause has at most d literals, and let ae p;D be a random restriction. Then
with probability at least 1
1. the function fdae can be expressed as a DNF formula where each term has at most s literals;
2. the terms of such a DNF all accept disjoint sets of inputs.
Proof sketch: The proof is a minor modification of arguments given in Section 4 of [2].
The following corollary is a product distribution analogue of ([22] Corollary 1):
Corollary 11 Under the conditions of Lemma 10, with probability at least 1 \Gamma (4fipd) s we have
that g
s:
Proof: Linial et al. [22] show that if fdae satisfies properties (1) and (2) of Lemma 10 then
d
s: Hence such a fdae is in the space spanned by f-A : jAj - sg: By Fact 9
and the nature of Gram-Schmidt orthonormalization, this is the same space which is spanned by
and the corollary follows.
Corollary 11 is a sharpened version of a similar lemma, implicit in [10], which states that under
the same conditions with probability at least 1 \Gamma (5fipd=2) s we have g
Armed with the sharper Corollary 11, using arguments from [10] it is straightforward to prove
Lemma 12 For any Boolean function f; for any integer t;
jAj?t
~
ae p;D
Boolean duality implies that Lemma 10 and Corollary 11 also hold if f is a DNF with each term
of length at most d: Taking
ffl in this DNF version of Corollary 11 and
ffl in Lemma 12, we obtain the following analogue of Mansour's lemma (Lemma
the OE basis:
f be a DNF with terms of size at most d: Then for all ffl ? 0
jAj?16fid log(4=ffl)
~
Again using arguments from [10], Corollary 11 can also be used to prove the following version
of the main lemma from [10]:
Lemma 14 Let f be a Boolean function computed by a circuit of depth d and size M and let c be
any integer. Then X
~
The version of this lemma given in [10] has 1=(d + 2) instead of 1=d in the exponent of c: This
new tighter bound enables us to give stronger guarantees on our learning algorithm's performance
under product distributions than we could obtain using the lemma from [10].
4.2 Learning under Product Distributions
4.2.1 Identifying Relevant Variables
We have the following analogue to Lemma 2 for product distributions:
Lemma be a monotone Boolean function. There is an algorithm
which has access to EX(f;D); runs in poly(n; fi; 1=ffl; log 1=ffi) time steps for all ffl; ffi ? 0; and with
probability at least outputs a set S f ' [n] such that
A:i2A
~
A:i2A
~
The proof uses the fact ([9] Lemma 4.1) that 4oe 2
I D;i
A:i2A
~
Boolean function
f and any product distribution D: The algorithm uses sampling to approximate each - i (and thus
to approximate I D;i (f): We call this algorithm FindVariables2.
4.2.2 The Learning Algorithm
We would like to modify LearnMonotone so that it uses the OE basis rather than the - basis. However,
as in [10] the algorithm does not know the exact values of - i so it cannot use exactly the OE basis;
instead it approximates each - i by a sample value - 0
i and uses the resulting basis, which we call
the OE 0 basis. In more detail, the algorithm is as follows:
Use FindVariables2 to identify a set S f of important variables.
labeled examples hx
ffl For every A ' S f with jAj - c set ff 0
A
A
For every A such that jAj ? c or A 6' S f set ff 0
ffl Output the hypothesis sign(g(x)); where
A ff 0
A -A (x):
We call this algorithm LearnMonotone2. As in [10] we note that setting ff 0
A to \Sigma1 if jff 0
only bring the estimated value closer to the true value of ~
4.2.3 Learning Monotone 2 O(
log n) -term DNF
For the most part only minor changes to the analysis of Section 3.3 are required. Since a term of
size greater than d is satisfied by a random example from D with probability less than
the
new term size bound for f 1 is log fi
ffl ); so we now have jS f
ffl We
similarly obtain a term size bound of \Theta(fi log k
ffl We use the OE basis Parseval identity and
inequality (10) in place of the - basis identity and inequality (2) respectively. Lemma 13 provides
the required analogue of Mansour's lemma for product distributions; using with the new term size
bound on f 2 we obtain
The one new ingredient in the analysis of LearnMonotone2 comes in bounding the quantity
In addition to the sampling error which would be present even if - 0
were exactly must also deal with error due to the fact that ff 0
A is an estimate of the OE 0 basis
coefficient rather than the OE basis coefficient ~
An analysis entirely similar to that of Section
5.2 of [10] shows that taking suffices. We thus have
Theorem 16 Under any product distribution D; for any ffl; ffi ? 0; algorithm LearnMonotone2 learns
k-term monotone DNF in time polynomial in n; (fik log kn
Since a constant-bounded distribution D has
Corollary 17 For any constant ffl and any constant-bounded product distribution D; algorithm
learns 2 O(
log n) -term monotone DNF in poly(n; log(1=ffi)) time.
4.2.4 Learning Small Constant-Depth Monotone Circuits on Few Variables
Using Lemma 14 and an analysis similar to the above, we obtain
Theorem let C be the class of depth d, size M circuits which compute monotone
functions on r out of n variables. Under any product distribution D; for any ffl; ffi ? 0; algorithm
LearnMonotone2 learns class C in time polynomial in n; r (fi log M
and log(1=ffi):
Corollary 19 Fix d - 1 and let C be the class of depth d; size 2 O((log n) 1=(d+1) ) circuits which compute
monotone functions on 2 O((log n) 1=(d+1) ) variables. Then for any constant ffl and any constant-
bounded product distribution D; algorithm LearnMonotone2 learns class C in poly(n; log(1=ffi)) time.
5 Open Questions
The major open problem in this area is clearly to find a polynomial time algorithm which learns
arbitrary polynomial size DNF under an arbitrary distribution; however this seems to be a very
difficult problem. Even the discovery of a polynomial time algorithm for t(n)-term DNF under the
uniform distribution, for some would be a substantial step forward. From another
angle, the positive results reported in this paper provide some hope for a polynomial time algorithm
for polynomial size monotone DNF under the uniform distribution.
6

Acknowledgements

We thank Les Valiant for his advice and enouragement.



--R

Monotone versus positive
A switching lemma primer.
"Proc. 26th Ann. Symp. on Theory of Computing"
A representation of the joint distribution of responses to n dichotomous items
"Proc. Fifth Ann. Workshop on Comp. Learning Theory"
Fast learning of k-term DNF formulas with queries
The complexity of finite functions
"Proc. 12th Ann. Conf. on Comp. Learning Theory"
On the Fourier spectrum of monotone functions
"Proc. Fourth Ann. Workshop on Comp. Learning Theory"
A guided tour to Chernoff bounds
The complexity of learning formulas and decision trees that have restricted reads
"Proc. 4th Ann. Workshop on Comp. Learning Theory"
Computational Limitations for Small Depth Circuits.
An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
"Proc. 29th Ann. Symp. on Found. of Comp. Sci."
"Proc. 19th Ann. ACM Symp. on Theory of Computing"
Learning boolean formulas
On using the Fourier transform to learn disjoint DNF
"Proc. 40th Ann. Symp. on Found. of Comp. Sci."
On learning monotone DNF formulae under uniform distributions
Constant depth circuits
An O(n log log n
On the influence of negations on the complexity of a realization of monotone Boolean functions by formulas of bounded depth
"Proc. Seventh Conf. on Comp. Learning Theory"
A theory of the learnable
"Proc. 3rd Ann. Workshop on Comp. Learning Theory"
"Proc. 9th Conf. on Algorithmic Learning Theory"
--TR
A theory of the learnable
Computational limitations of small-depth circuits
On the learnability of Boolean formulae
Monotone versus positive
A guided tour of Chernoff bounds
Learning DNF under the uniform distribution in quasi-polynomial time
Learning monotone <italic>ku</italic> DNF formulas on product distributions
Improved learning of AC<supscrpt>0</supscrpt> functions
The complexity of finite functions
A technique for upper bounding the spectral norm with applications to learning
Constant depth circuits, Fourier transform, and learnability
On using the Fourier transform to learn Disjoint DNF
Learning monotone log-term DNF formulas
Weakly learning DNF and characterizing statistical query learning using Fourier analysis
Learning Boolean formulas
An <italic>O(n<supscrpt>log log n</supscrpt>)</italic> learning algorithm for DNF under the uniform distribution
Exact learning Boolean functions via the monotone theory
On the Fourier spectrum of monotone functions
An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
More efficient PAC-learning of DNF with membership queries under the uniform distribution
Queries and Concept Learning
Boosting and Hard-Core Sets
computational learning theory;DNF formula;PAC learning;monotone boolean function