Polynomial bounds for decoupling, with applications
From MaRDI portal
(Redirected from Publication:5368758)
Abstract: 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, f~(y,z) = sum_{|S| <= k} a_S sum_{i in S} y_i prod_{j in Si} z_j, we show tail-bound comparisons of the form Pr[|f~(y,z)| > C_k t] <= D_k Pr[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, y, z, Rademacher 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).
Recommendations
- scientific article; zbMATH DE number 1149762
- Decoupling inequalities with exponential constants
- Decoupling inequalities for polynomial chaos
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- Decoupling inequalities for the tail probabilities of multivariate \(U\)- statistics
Cited in
(8)- Separation bounds for polynomial systems
- On the Fourier spectrum of functions on Boolean cubes
- Unifying presampling via concentration bounds
- Forrelation: a problem that optimally separates quantum from classical computing
- Polynomial threshold functions, hyperplane arrangements, and random tensors
- Computer Algebra in Scientific Computing
- Decoupling inequalities with exponential constants
- Local tail bounds for polynomials on the discrete cube
This page was built for publication: Polynomial bounds for decoupling, with applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368758)
