2015/12/05 by Ryan O'Donnell, Yu Zhao, O'Donnell, Ryan +1
Computer Science · Mathematics · #60C05 #68Q17 #68Q87 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.DM #math.PR #msc:60C05 #msc:68Q17 #msc:68Q87
paper · pdf · doi:10.48550/arxiv.1512.01603
19 pages, including bibliography
arxiv created 2015/12/05 · arxiv updated 2015/12/08
Let f(x) = f(x1, ..., xn) = ∑|S| <= k aS ∏i ∈ S xi be an n-variate real multilinear polynomial of degree at most k, where S ⊆ [n] = 1, 2, ..., n. For its "one-block decoupled" version, f~(y,z) = ∑|S| <= k aS ∑i ∈ S yi ∏j ∈ Sı zj, we show tail-bound comparisons of the form Pr[|f~(y,z)| > Ck t] <= Dk Pr[f(x) > t]. Our constants Ck, Dk are significantly better than those known for "full decoupling". For example, when x, y, z are independent Gaussians we obtain Ck = Dk = O(k); when x, y, z, Rademacher random variables we obtain Ck = O(k2), Dk = kO(k). By contrast, for full decoupling only Ck = Dk = kO(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).