Biased halfspaces, noise sensitivity, and local Chernoff inequalities

DOI10.19086/DA.10234MaRDI QIDQ5211012zbMATH OpenOpenAlexFDO

Authors Nathan Keller, Ohad Klein

Publication date 17 January 2020

Published in discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

biased Boolean functionsfirst-degree Fourier weight of halfspaces

Mathematics Subject Classification ID

Combinatorial inequalities (05A20) Probabilistic methods for one variable harmonic analysis (42A61) Combinatorial probability (60C05) Boolean functions (94D10)

Abstract: A halfspace is a function $fcolon{-1,1}^{n}ightarrow0,1$ of the form $f(x)=mathbb1(acdotx>t)$, where $su{m}_i{a}_i^2=1$. We show that if $f$ is a halfspace with $mathbbE[f]=epsilon$ and $a^{\prime }=ma{x}_i|a_i|$, then the degree-1 Fourier weight of $f$ is $W^1(f)=Theta(epsilo{n}^{2}log(1/epsilon))$, and the maximal influence of $f$ is $I_{max}(f)=Theta(epsilonmin(1,a^{\prime }sqrtlog(1/epsilon)))$. These results, which determine the exact asymptotic order of $W^1(f)$ and $I_{max}(f)$, provide sharp generalizations of theorems proved by Matulef, O'Donnell, Rubinfeld, and Servedio, and settle a conjecture posed by Kalai, Keller and Mossel. In addition, we present a refinement of the definition of noise sensitivity which takes into consideration the bias of the function, and show that (like in the unbiased case) halfspaces are noise resistant, and, in the other direction, any noise resistant function is well correlated with a halfspace. Our main tools are 'local' forms of the classical Chernoff inequality, like the following one proved by Devroye and Lugosi (2008): Let $x_i$ be independent random variables uniformly distributed in $-1,1$, and let $a_{i}inmathbb{R}_{+}$ be such that $su{m}_i{a}_i^2=1$. If for some $tgeq0$ we have $Pr[su{m}_i{a}_i{x}_i>t]=epsilon$, then $Pr[su{m}_i{a}_i{x}_i>t+delta]leqfracepsilon2$ holds for $deltaleqc/sqrtlog(1/epsilon)$, where $c$ is a universal constant.

Recommendations

• Half-spaces with influential variable
• Noise stability and correlation with half spaces
• scientific article; zbMATH DE number 6537946
• Testing Halfspaces
• Testing halfspaces

Cites work

• A Characterization of Weighted Voting
• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
• A polynomial bound in Freiman's theorem.
• A probability inequality for linear combinations of bounded random variables
• A tight Gaussian bound for weighted sums of Rademacher random variables
• A tight quantitative version of Arrow's impossibility theorem
• An entropic proof of Chang's inequality
• An introduction to support vector machines and other kernel-based learning methods.
• Average sensitivity and noise sensitivity of polynomial threshold functions
• Correlation inequalities on some partially ordered sets
• First passage percolation has sublinear distance variance.
• Half-spaces with influential variable
• How much are increasing sets positively correlated?
• scientific article; zbMATH DE number 5504150 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• scientific article; zbMATH DE number 3266648 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• KKL, Kruskal-Katona, and monotone nets
• Local tail bounds for functions of independent random variables
• Lost (and Found) in Translation: André's Actual Method and Its Application to the Generalized Ballot Problem
• Majority gates vs. general weighted threshold gates
• Monotone Boolean formulas can approximate monotone linear threshold functions
• Noise sensitivity of Boolean functions and applications to percolation
• Noise stability and correlation with half spaces
• Noise stability of functions with low influences: invariance and optimality
• On boundaries and influences
• On Russo's approximate zero-one law
• On the correlation of increasing families
• On the hardness of approximating minimum vertex cover
• On the structure of subsets of the discrete cube with small edge boundary
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Quantitative noise sensitivity and exceptional times for percolation
• Quantitative relation between noise sensitivity and influences
• Some optimal inapproximability results
• Spectral properties of threshold functions
• Testing Halfspaces
• The Chow parameters problem
• The Distribution of Rademacher Sums
• The Fourier spectrum of critical percolation
• Thresholds and Expectation Thresholds
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)

Cited in

(4)

• Proof of Tomaszewski's conjecture on randomly signed sums
• scientific article; zbMATH DE number 6537946 (Why is no real title available?)
• Half-spaces with influential variable
• Talagrand-type correlation inequalities for supermodular and submodular functions on the hypercube

This page was built for publication: Biased halfspaces, noise sensitivity, and local Chernoff inequalities

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