On learning embedded midbit functions Author: Rocco A. Servedio Source: Theoretical Computer Science Vol. 350, Issue 1, January 2006, pp. 13-23 (Special Issue Algorithmic Learning Theory (ALT 2002)). Abstract. A midbit function on ℓ binary inputs x1,…,xℓ outputs the middle bit in the binary representation of x1 + ··· + xℓ. We consider the problem of Probably Approximately Correct (PAC) learning embedded midbit functions, where the set S ⊂ {x1,…,xn} of relevant variables on which the midbit depends is unknown to the learner. To motivate this problem, we first point out that a result of Green et al. implies that a polynomial time learning algorithm for the class of embedded midbit functions would immediately yield a fairly efficient (quasipolynomial time) (PAC) learning algorithm for the entire complexity class ACC. We then give two different subexponential learning algorithms, each of which learns embedded midbit functions under any probability distribution in 2√n log n time. Finally, we give a polynomial time algorithm for learning embedded midbit functions under the uniform distribution. Keywords: PAC learning; Embedded midbit functions

©Copyright 2005 Elsevier Science B.V.