A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry

DOI10.1137/130919143zbMATH Open1339.68195arXiv1207.2229OpenAlexW2399370712MaRDI QIDQ2808162FDOQ2808162

Ilias Diakonikolas, Anindya De, Rocco A. Servedio

Publication date: 26 May 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: This paper makes two contributions towards determining some well-studied optimal constants in Fourier analysis ewa{of Boolean functions} and high-dimensional geometry. �egin{enumerate} item It has been known since 1994 cite{GL:94} that every linear threshold function has squared Fourier mass at least 1/2 on its degree-0 and degree-1 coefficients. Denote the minimum such Fourier mass by $w^{leq1}[ltf]$, where the minimum is taken over all $n$-variable linear threshold functions and all $nge0$. Benjamini, Kalai and Schramm cite{BKS:99} have conjectured that the true value of $w^{leq1}[ltf]$ is $2/pi$. We make progress on this conjecture by proving that $w^{leq1}[ltf]geq1/2+c$ for some absolute constant $c>0$. The key ingredient in our proof is a "robust" version of the well-known Khintchine inequality in functional analysis, which we believe may be of independent interest. item We give an algorithm with the following property: given any $eta>0$, the algorithm runs in time $2^{poly(1/eta)}$ and determines the value of $w^{leq1}[ltf]$ up to an additive error of $pmeta$. We give a similar $2^{poly(1/eta)}$-time algorithm to determine emph{Tomaszewski's constant} to within an additive error of $pmeta$; this is the minimum (over all origin-centered hyperplanes $H$) fraction of points in ${-1,1}^n$ that lie within Euclidean distance 1 of $H$. Tomaszewski's constant is conjectured to be 1/2; lower bounds on it have been given by Holzman and Kleitman cite{HK92} and independently by Ben-Tal, Nemirovski and Roos cite{BNR02}. Our algorithms combine tools from anti-concentration of sums of independent random variables, Fourier analysis, and Hermite analysis of linear threshold functions. end{enumerate}

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

Recommendations

• A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry
• Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
• On the distribution of the Fourier spectrum of Boolean functions
• Towards a proof of the Fourier-entropy conjecture?
• On the Best Possible Constants in the Khintchine Inequality for P ⩾ 3

zbMATH Keywords

Fourier analysishyperplanesKhintchine inequalityhalfspaceslinear threshold functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Combinatorial probability (60C05) Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) (42C10) Spaces of measurable functions ((L^p)-spaces, Orlicz spaces, Köthe function spaces, Lorentz spaces, rearrangement invariant spaces, ideal spaces, etc.) (46E30) Combinatorial inequalities (05A20) Boolean functions (06E30)

Cites Work

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

Cited In (11)

• Biased halfspaces, noise sensitivity, and local Chernoff inequalities
• Some explorations on two conjectures about Rademacher sequences
• Towards sharp Bohnenblust–Hille constants
• Tomaszewski's problem on randomly signed sums: breaking the 3/8 barrier
• A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry
• Stability of polydisc slicing
• Quantitative form of Ball’s cube slicing in ℝⁿ and equality cases in the min-entropy power inequality
• Proof of Tomaszewski's conjecture on randomly signed sums
• Resilience of cube slicing in \(\ell_p\)
• Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration
• Slicing \(\ell_p\)-balls reloaded: stability, planar sections in \(\ell_1\)

This page was built for publication: A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2808162)