On Learning Embedded Midbit Functions

Abstract

A midbit function on l binary inputs x _1, … , x l outputs the middle bit in the binary representation of x _1 + ⋯ + x l . We consider the problem of PAC learning embedded midbit functions, where the set S ⊂ x _1, . . . , x _n of relevant variables on which the midbit depends is unknown to the learner. To motivate this problem, we first show 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 log n time. Finally, we give a polynomial time algorithm for learning embedded midbit functions under the uniform distribution.