Speaker: Eric Blais
Title: Testing juntas

Abstract:
A function on n variables is called a k-junta if it depends on at most k of the variables.  A randomized algorithm A is an algorithm for testing k-junta if it can reliably distinguish the case where a given function f is a k-junta from the case where f is "far" from being a k-junta using only a few queries to f.
In this talk, we will explore the following question: What is the minimum number of queries required by to test k-juntas? Until recently, all known algorithms for testing k-juntas required at least O(k^2) queries.  I will introduce a new algorithm for testing k-juntas with only O(k^1.5) queries.