## Testing Juntas Nearly Optimally

by Eric Blais

Given the importance of dealing with functions that depend on few of their inputs (aka juntas), the problem of optimizing the complexity of testing juntas does deserve the attention it has received. The algorithm presented in this work is very appealing, and has query complexity $\tildeO(k/\epsilon)$, where $\epsilon$ is the proximity parameter.