2026-08-17T14:59:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5852 2024-03-06T10:37:11Z ddc:004 open_access

Polynomial Bounds for Decoupling, with Applications O'Donnell, Ryan Zhao, Yu Decoupling Query Complexity Fourier Analysis Boolean Functions Let f(x) = f(x_1, ..., x_n) = sum_{|S|<=k} a_S prod_{i in S} x_i be an n-variate real multilinear polynomial of degree at most k, where S subseteq [n] = {1, 2, ..., n}. For its one-block decoupled version, vf(y,z) = sum_{abs(S)<=k} a_S sum_{i in S}} y_i prod_{j in S\{i}} z_j, we show tail-bound comparisons of the form Pr(abs(vf)(y,z)) > C_k t} <= D_k Pr(abs(f(x)) > t). Our constants C_k, D_k are significantly better than those known for "full decoupling". For example, when x, y, z are independent Gaussians we obtain C_k = D_k = O(k); when x, by, z are +/-1 random variables we obtain C_k = O(k^2), D_k = k^{O(k)}. By contrast, for full decoupling only C_k = D_k = k^{O(k)} is known in these settings. We describe consequences of these results for query complexity (related to conjectures of Aaronson and Ambainis) and for analysis of Boolean functions (including an optimal sharpening of the DFKO Inequality). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ryan O'Donnell and Yu Zhao 2016 Is Part Of LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2016.24 urn:nbn:de:0030-drops-58520 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.24 eng https://creativecommons.org/licenses/by/3.0/legalcode