Testing Juntas Optimally with Samples

Abstract

We prove tight upper and lower bounds of (1( 2^k nk + nk )) on the number of samples required for distribution-free k-junta testing. This is the first tight bound for testing a natural class of Boolean functions in the distribution-free sample-based model. Our bounds also hold for the feature selection problem, showing that a junta tester must learn the set of relevant variables. For tolerant junta testing, we prove a sample lower bound of (2^(1-o(1)) k + nk) showing that, unlike standard testing, there is no large gap between tolerant testing and learning.

Tasks

Reproductions