Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-078 | 9th May 2011 12:05

On Approximating the Number of Relevant Variables in a Function

RSS-Feed




TR11-078
Authors: Dana Ron, Gilad Tsur
Publication: 9th May 2011 14:10
Downloads: 3058
Keywords: 


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.



ISSN 1433-8092 | Imprint