Learning a Function of R Relevant Variables
Abstract
This problem has been around for a while but is one of my favorites. I will state it here in three forms, discuss a number of known results (some easy and some more intricate), and finally end with small financial incentives for various kinds of partial progress. This problem appears in various guises in [2, 3, 10]. To begin we need the following standard definition: a boolean function f over 0,1^ n has (at most) r relevant variables if there exist r indices i _1, ..., i _ r such that $f(x) = g(x_{i_1}, \ldots, x_{i_r})$ for some boolean function g over 0,1^ r . In other words, the value of f is determined by only a subset of r of its n input variables. For instance, the function $f(x) = x_1\bar{x}_2 \vee x_2\bar{x}_5 \vee x_5\bar{x}_1$ has three relevant variables. The “class of boolean functions with r relevant variables” is the set of all such functions, over all possible g and sets i _1, ..., i _ r .
Cite
Text
Blum. "Learning a Function of R Relevant Variables." Annual Conference on Computational Learning Theory, 2003. doi:10.1007/978-3-540-45167-9_54Markdown
[Blum. "Learning a Function of R Relevant Variables." Annual Conference on Computational Learning Theory, 2003.](https://mlanthology.org/colt/2003/blum2003colt-learning/) doi:10.1007/978-3-540-45167-9_54BibTeX
@inproceedings{blum2003colt-learning,
title = {{Learning a Function of R Relevant Variables}},
author = {Blum, Avrim},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2003},
pages = {731-733},
doi = {10.1007/978-3-540-45167-9_54},
url = {https://mlanthology.org/colt/2003/blum2003colt-learning/}
}