On Learning Embedded Midbit Functions.
R. Servedio.
Theoretical Computer Science 350(1), 2006, pp. 13-23 (special issue for ALT 2002).
Preliminary version in Thirteenth International Conference on Algorithmic Learning Theory (ALT), 2002, pp. 69-82.

Abstract:

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