## On Learning Correlated Boolean Functions Using Statistical Queries (Extended Abstract)
An interesting consequence of our results is that the class of
booleanized linear functions over a finite field
( _{}
(a)
= 1, where
x_{}
is an arbitrary boolean function that maps any elements in GF
to
_{p}_{} 1)
is not efficiently learnable. This result is useful since the hardness of
learning booleanized linear functions over a finite field is related to the
security of certain cryptosystems ([B01]). In particular, we prove that the
class of linear threshold functions over a finite field
(f(_{a,}_{b}() = 1 iff
xaxb)
cannot be learned efficiently using statistical query.
This contrasts with Blum et. al.'s result [BFK+96] that linear threshold
functions over reals (perceptions) are learnable using the SQ model.
Finally, we describe a PAC-learning algorithm that learns a class of linear threshold functions in time that is provably impossible for statistical query algorithms. With properly chosen parameters, this class of linear threshold functions become an example of PAC-learnable, but not SQ-learnable functions that are not parity functions.
©Copyright 2001 Springer |