Title: Testing Juntas
Speaker: Guy Kindler, Rutgers University
Date: Monday, December 1, 2003, 1:10 pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Combinatorial property testing deals with the following task: for a fixed property P, and an input f, one has to distinguish with high probability between the case where f satisfies P and the case where f is 'far' from satisfying it, accessing the least possible number of bits from f.
In this talk the input, f, is a boolean function over n boolean variables. f is said to be a j-junta if it depends, in fact, on at most j of its variables (the origin of the term junta comes from regarding f as a voting scheme with n voters - a j-junta is a system where j voters always determine the outcome of the elections). We present a test that distinguishes with high probability between the case where f is a j-junta, and the case where f is 'epsilon-far' from any j-junta. The number of queries made is polynomial in j and epsilon, and the test is non-adaptive and one-sided.
Joint work with Eldar Fischer, Dana Ron, Shmuel Safra, and Alex Samorodnitsky.