A midbit function on $\ell$ binary inputs $x_1,\dots,x_\ell$ outputs the middle bit in the binary representation of $x_1 + \cdots + x_\ell.$ We consider the problem of PAC learning {\em embedded} midbit functions, where the set $S \subset \{x_1,\dots,x_n\}$ 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 {\em 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^{\sqrt{n} \log n}$ time. Finally, we give a polynomial time algorithm for learning embedded midbit functions under the uniform distribution.
Postscript or
pdf of conference version
pdf of journal version