Testing juntas |
| |
Authors: | Eldar Fischer Guy Kindler Shmuel Safra Alex Samorodnitsky |
| |
Affiliation: | a Faculty of Computer Science, Technion-Israel Institute of Technology, 32000 Haifa, Israel b School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv, Israel c Department of Electrical Engineering, Tel-Aviv University, Tel-Aviv, Israel d School of Computer Science and Engineering, The Hebrew University of Jerusalem, Jerusalem, Israel |
| |
Abstract: | We show that a boolean valued function over n variables, where each variable ranges in an arbitrary probability space, can be tested for the property of depending on only J of them using a number of queries that depends only polynomially on J and the approximation parameter ε. We present several tests that require a number of queries that is polynomial in J and linear in ε−1. We show a non-adaptive test that has one-sided error, an adaptive version of it that requires fewer queries, and a non-adaptive two-sided version of the test that requires the least number of queries. We also show a two-sided non-adaptive test that applies to functions over n boolean variables, and has a more compact analysis.We then provide a lower bound of on the number of queries required for the non-adaptive testing of the above property; a lower bound of for adaptive algorithms naturally follows from this. In establishing this lower bound we also prove a result about random walks on the group Zq2 that may be interesting in its own right. We show that for some , the distributions of the random walk at times t and t+2 are close to each other, independently of the step distribution of the walk.We also discuss related questions. In particular, when given in advance a known J-junta function , we show how to test a function for the property of being identical to up to a permutation of the variables, in a number of queries that is polynomial in J and ε−1. |
| |
Keywords: | Property testing Boolean functions Discrete Fourier Analysis Juntas |
本文献已被 ScienceDirect 等数据库收录! |
|