A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry

DOI10.1137/130919143zbMath1339.68195arXiv1207.2229OpenAlexW2399370712MaRDI QIDQ2808162

Ilias Diakonikolas, Anindya De, Rocco A. Servedio

Publication date: 26 May 2016

Published in: SIAM Journal on Discrete Mathematics, Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1207.2229

zbMATH Keywords

Fourier analysisKhintchine inequalityhyperplaneslinear threshold functionshalfspaces

Mathematics Subject Classification ID

Related Items (10)

Biased halfspaces, noise sensitivity, and local Chernoff inequalities ⋮ Proof of Tomaszewski's conjecture on randomly signed sums ⋮ Tomaszewski's problem on randomly signed sums: breaking the 3/8 barrier ⋮ Quantitative form of Ball’s cube slicing in ℝⁿ and equality cases in the min-entropy power inequality ⋮ Stability of polydisc slicing ⋮ Towards sharp Bohnenblust–Hille constants ⋮ Some explorations on two conjectures about Rademacher sequences ⋮ A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry ⋮ Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration ⋮ Slicing \(\ell_p\)-balls reloaded: stability, planar sections in \(\ell_1\)

Cites Work

• Nonnegative \(k\)-sums, fractional covers, and probability of small deviations
• An asymptotically Gaussian bound on the Rademacher tails
• On the product of sign vectors and unit vectors
• Learning with restricted focus of attention
• Spectral properties of threshold functions
• Extremal probabilistic problems and Hotelling's \(T^ 2\) test under a symmetry condition
• On Hoeffding's inequalities.
• Comparison of moments of sums of independent random variables and differential inequalities
• Noise stability of weighted majority
• A tight Gaussian bound for weighted sums of Rademacher random variables
• Every linear threshold function has a low-weight approximator
• A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry
• Slip and slide method of factoring trinomials with integer coefficients over the integers
• The Chow Parameters Problem
• Testing Halfspaces
• Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces
• The Distribution of Rademacher Sums
• Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization
• On the best constants in the Khinchin inequality
• The best constants in the Khintchine inequality
• Projection constants of symmetric spaces and variants of Khintchine's inequality
• Robust Solutions of Uncertain Quadratic and Conic-Quadratic Problems
• Uniform-Distribution Learnability of Noisy Linear Threshold Functions with Restricted Focus of Attention
• Bounded Independence Fools Halfspaces
• Sharpening of the Upper Bound of the Absolute Constant in the Berry–Esseen Inequality
• Noise sensitivity of Boolean functions and applications to percolation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry