Biased halfspaces, noise sensitivity, and local Chernoff inequalities
From MaRDI portal
Publication:5211012
DOI10.19086/da.10234zbMath1480.42010arXiv1710.07429OpenAlexW2979607832MaRDI QIDQ5211012
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
Combinatorial probability (60C05) Combinatorial inequalities (05A20) Probabilistic methods for one variable harmonic analysis (42A61) Boolean functions (94D10)
Related Items (1)
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