تقرير
A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers
| العنوان: | A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers |
|---|---|
| المؤلفون: | Blanc, Guy, Koch, Caleb, Strassle, Carmen, Tan, Li-Yang |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms |
| الوصف: | 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. Comment: 44 pages, 1 figure, FOCS 2023 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2307.04039 |
| رقم الأكسشن: | edsarx.2307.04039 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |