Biased halfspaces, noise sensitivity, and local Chernoff inequalities

DOI10.19086/da.10234zbMath1480.42010arXiv1710.07429OpenAlexW2979607832MaRDI QIDQ5211012

Nathan Keller, Ohad Klein

Publication date: 17 January 2020

Published in: discrete Analysis (Search for Journal in Brave)

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 probability (60C05) Combinatorial inequalities (05A20) Probabilistic methods for one variable harmonic analysis (42A61) Boolean functions (94D10)

Related Items (1)

Proof of Tomaszewski's conjecture on randomly signed sums

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Fourier spectrum of critical percolation
• A tight quantitative version of Arrow's impossibility theorem
• On the correlation of increasing families
• On the hardness of approximating minimum vertex cover
• Noise stability of functions with low influences: invariance and optimality
• Quantitative noise sensitivity and exceptional times for percolation
• Majority gates vs. general weighted threshold gates
• Correlation inequalities on some partially ordered sets
• Spectral properties of threshold functions
• On Russo's approximate zero-one law
• On boundaries and influences
• First passage percolation has sublinear distance variance.
• Noise stability and correlation with half spaces
• A probability inequality for linear combinations of bounded random variables
• A polynomial bound in Freiman's theorem.
• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
• Monotone Boolean formulas can approximate monotone linear threshold functions
• How much are increasing sets positively correlated?
• A tight Gaussian bound for weighted sums of Rademacher random variables
• Quantitative relation between noise sensitivity and influences
• Local tail bounds for functions of independent random variables
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry
• The Chow Parameters Problem
• Testing Halfspaces
• Thresholds and Expectation Thresholds
• The Distribution of Rademacher Sums
• Lost (and Found) in Translation: André's Actual Method and Its Application to the Generalized Ballot Problem
• A Characterization of Weighted Voting
• On the structure of subsets of the discrete cube with small edge boundary
• An Entropic Proof of Chang's Inequality
• Half-Spaces with Influential Variable
• KKL, Kruskal--Katona, and Monotone Nets
• Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Noise sensitivity of Boolean functions and applications to percolation

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