__
TR11-078 | 9th May 2011 12:05
__

#### On Approximating the Number of Relevant Variables in a Function

**Abstract:**
In this work we consider the problem of approximating the number of relevant variables in a function given query access to the function. Since obtaining a multiplicative factor approximation is hard in general, we consider several relaxations of the problem. In particular, we consider relaxations in which we have a promise that the function belongs to a certain family of functions (e.g., linear functions), and we consider a relaxation of the property testing variant of the problem. In the latter relaxation the task is to distinguish between the case that the number of relevant variables is at most $k$, and the case in which it is far from any function in which the number of relevant variable is more than $(1+\gamma)k$ for a parameter $\gamma$. We give both upper bounds and almost matching lower bounds for the relaxations we study.