A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers

• Published in: arXiv.org 2023-07
• Main Authors: Blanc, Guy, Koch, Caleb, Strassle, Carmen, Li-Yang, Tan
• Format: Article
• Language: English
• Subjects: Algorithms; Complexity; Composition; Mathematical analysis; Multivariate analysis; Noise sensitivity; Theorems
• ISSN: 2331-8422

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 \(\varepsilon\)-approximate junta complexity of a function \(f\) is the smallest integer \(r\) such that \(f\) is \(\varepsilon\)-close to a function that depends only on \(r\) variables. A strong composition theorem states that if \(f\) has large \(\varepsilon\)-approximate junta complexity, then \(g \circ f\) has even larger \(\varepsilon'\)-approximate junta complexity, even for \(\varepsilon' \gg \varepsilon\). We develop a fairly complete understanding of this behavior, proving that the junta complexity of \(g \circ 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.