A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers
share
We prove a strong composition theorem for junta complexity and show how such theorems can be used to generically boost the performance of property testers. The ε-approximate junta complexity of a function f is the smallest integer r such that f is ε-close to a function that depends only on r variables. A strong composition theorem states that if f has large ε-approximate junta complexity, then g ∘ f has even larger ε'-approximate junta complexity, even for ε' ≫ε. We develop a fairly complete understanding of this behavior, proving that the junta complexity of g ∘ f is characterized by that of f along with the multivariate noise sensitivity of g. For the important case of symmetric functions g, we relate their multivariate noise sensitivity to the simpler and well-studied case of univariate noise sensitivity. We then show how strong composition theorems yield boosting algorithms for property testers: with a strong composition theorem for any class of functions, a large-distance tester for that class is immediately upgraded into one for small distances. Combining our contributions yields a booster for junta testers, and with it new implications for junta testing. This is the first boosting-type result in property testing, and we hope that the connection to composition theorems adds compelling motivation to the study of both topics.
READ FULL TEXT