Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-078 | 9th May 2011 12:05

On Approximating the Number of Relevant Variables in a Function


Authors: Dana Ron, Gilad Tsur
Publication: 9th May 2011 14:10
Downloads: 1058


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.

ISSN 1433-8092 | Imprint