الفهرس | Only 14 pages are availabe for public view |
Abstract Given an unknown Boolean function with oracle access, can we determine which input variable the function depends on, and which does not? The junta property testing is considered as a typical problem, for instance, in machine learning in which there is often no way to explicitly discriminate between relevant features to the learning process from other irrelevant features. Therefore, it is necessary useful to use an adequate algorithm for testing the existence of such property and narrowing the number of features that have impact on the learning process. This thesis studies the problem of junta testing of variables in black-box Boolean functions, and the potentials of such knowledge in learning about those black-boxes. |