O'Donnell, Ryan ;
Zhao, Yu
Polynomial Bounds for Decoupling, with Applications
Abstract
Let f(x) = f(x_1, ..., x_n) = sum_{S<=k} a_S prod_{i in S} x_i be an nvariate real multilinear polynomial of degree at most k, where S subseteq [n] = {1, 2, ..., n}. For its oneblock 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 tailbound 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).
BibTeX  Entry
@InProceedings{odonnell_et_al:LIPIcs:2016:5852,
author = {Ryan O'Donnell and Yu Zhao},
title = {{Polynomial Bounds for Decoupling, with Applications}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {24:124:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5852},
URN = {urn:nbn:de:0030drops58520},
doi = {10.4230/LIPIcs.CCC.2016.24},
annote = {Keywords: Decoupling, Query Complexity, Fourier Analysis, Boolean Functions}
}
2016
Keywords: 

Decoupling, Query Complexity, Fourier Analysis, Boolean Functions 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

2016 