Polynomial Bounds for Decoupling, with Applications
Ryan W. O’Donnell, Yu Zhao · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
Let f(x) = f(x_1, ..., x_n) = sum_{|S| C_k t} 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).