The Kushilevitz-Mansour, "low-degree", and Goldreich-Levin algorithms aim to learn a function $f: \{0,1\}^n \rightarrow \{0,1\}$ from a sufficiently large set of input-output examples $(x_i, f(x_i))$. But lets say that I have a function $g: \{0,1\}^n \rightarrow \{0,1\}^2$, and let $g_1, g_2 : \{0,1\}^n \rightarrow \{0,1\}$ be the mappings from the input to the "first" and "second" output bits of $g$, respectively. Given input-output examples $(x_i, g(x_i))$, one could (in theory) learn $g_1,g_2$ individually, by treating the observations $g(x_i)$ as paired observations of $g_1(x_i)$, $g_2(x_i)$, and ignoring the appropriate element. Naively, to learn $g_1$ you'd ignore the second element of the pair and apply your Boolean-function-learning algorithm, and likewise for $g_2$. In practice, one or both of these might fail, because (say) learning $g_1$ and/or $g_2$ requires too many input-output examples, individually. But these learning algorithms don't exploit the available side information, i.e., that $g_1,g_2$ are individual "slices" of $g$.

My question is this: are there versions of Boolean-function-learning algorithms that could exploit this side information?

  • $\begingroup$ What's the class of possibilities for $g$? Linear functions? Low-degree functions? Something else? I don't think the question is answerable without that. $\endgroup$
    – D.W.
    Commented Oct 9, 2022 at 18:44


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.