ECCC-Report TR11-078https://eccc.weizmann.ac.il/report/2011/078Comments and Revisions published for TR11-078en-usMon, 09 May 2011 14:10:25 +0300
Paper TR11-078
| On Approximating the Number of Relevant Variables in a Function |
Gilad Tsur,
Dana Ron
https://eccc.weizmann.ac.il/report/2011/078In 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.Mon, 09 May 2011 14:10:25 +0300https://eccc.weizmann.ac.il/report/2011/078