speaker: Guy Kindler (Hebrew University)

title: "Testing Juntas"
                    
Abstract:
---------
A Boolean function f over n Boolean variables is called a k-junta, if it
depends on at most k of its variables. This term originates in the theory
of social choice, where the variables of f correspond to voters, their
assignment corresponds to an election, and the value of f is regarded as
the outcome of the election. In these terms, a k-junta is an election
scheme the outcome of which is completely determined by at most k voters.

The talk will discuss the problem of testing whether a given Boolean
function f is a k-junta or whether f is 'epsilon-far' from any k-junta,
making the least possible number of accesses to its truth table. In
particular, a test will be shown that makes a polynomial number, in k and
epsilon, of queries to f. Note that the number of queries is independent
of the number of variables of f.

Joint work with Eldar Fischer, Dana Ron, Shmuel Safra, and Alex
Samorodnitsky.