8
Apr
Speaker: Eric Blais
Title: Testing juntas
Date: 2008-04-09 12:00
Place: NSH 1507
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.
