On Approximating the Number of Relevant Variables in a Function
Dana Ron, Gilad Tsur · ACM Transactions on Computation Theory · 2013
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 a relaxation of the property testing variant of the problem and we consider relaxations in which we have a promise that the function belongs to a certain family of functions (e.g., linear functions). In the former 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 variables is more than (1 + γ ) k for a parameter γ . We give both upper bounds and almost matching lower bounds for the relaxations we study.