Boolean functions with low average sensitivity depend on few coordinates
From MaRDI portal
Publication:1280280
DOI10.1007/PL00009809zbMath0909.06008OpenAlexW1986296546WikidataQ62111466 ScholiaQ62111466MaRDI QIDQ1280280
Publication date: 14 March 1999
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/pl00009809
Related Items
Log-Sobolev inequality for the multislice, with applications ⋮ On the round complexity of randomized Byzantine agreement ⋮ On the failure of concentration for the \(\ell_\infty\)-ball ⋮ Boolean functions: influence, threshold and noise ⋮ Sharp thresholds of graph properties, and the $k$-sat problem ⋮ Bi-Lipschitz bijection between the Boolean cube and the Hamming ball ⋮ On regular 3-wise intersecting families ⋮ An orthogonal basis for functions over a slice of the Boolean hypercube ⋮ Around two theorems and a lemma by Lucio Russo ⋮ On the efficiency of the probabilistic neutral bits method in statistical cryptanalysis of synchronous stream ciphers ⋮ DNF sparsification and a faster deterministic counting algorithm ⋮ Improved approximation of linear threshold functions ⋮ Hypercontractivity for global functions and sharp thresholds ⋮ A stability result for the cube edge isoperimetric inequality ⋮ Secure non-interactive simulation from arbitrary joint distributions ⋮ Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions ⋮ Hypercontractivity on the symmetric group ⋮ KKL's influence on me ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Average sensitivity of nested canalizing multivalued functions ⋮ Stability for vertex isoperimetry in the cube ⋮ Geometric influences ⋮ Shadows of ordered graphs ⋮ High dimensional Hoffman bound and applications in extremal combinatorics ⋮ A structure theorem for Boolean functions with small total influences ⋮ A simple reduction from a biased measure on the discrete cube to the uniform measure ⋮ On a biased edge isoperimetric inequality for the discrete cube ⋮ Randomly colouring graphs (a combinatorial view) ⋮ Towards a proof of the Fourier-entropy conjecture? ⋮ A structure theorem for almost low-degree functions on the slice ⋮ Almost Isoperimetric Subsets of the Discrete Cube ⋮ Fourier analysis and large independent sets in powers of complete graphs ⋮ The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture ⋮ Decision Trees and Influences of Variables Over Product Probability Spaces ⋮ Intersecting Families are Essentially Contained in Juntas ⋮ On the structure of subsets of the discrete cube with small edge boundary ⋮ Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality ⋮ A quasi-stability result for dictatorships in \(S_n\) ⋮ Vertex cover might be hard to approximate to within \(2 - \varepsilon \) ⋮ Intersecting families of permutations ⋮ On the Fourier tails of bounded functions over the discrete cube ⋮ Noise sensitivity of Boolean functions and applications to percolation ⋮ On the sensitivity to noise of a Boolean function ⋮ On set systems without a simplex-cluster and the junta method ⋮ Noise stability of functions with low influences: invariance and optimality ⋮ On the structure of Boolean functions with small spectral norm ⋮ A note on the entropy/influence conjecture ⋮ Friedgut--Kalai--Naor theorem for slices of the Boolean cube ⋮ Unnamed Item ⋮ Edge-Isoperimetric Inequalities and Influences ⋮ Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems ⋮ Simple juntas for shifted families ⋮ On the Influences of Variables on Boolean Functions in Product Spaces ⋮ Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ Vertex-isoperimetric stability in the hypercube ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas ⋮ Juntas in theℓ1-grid and Lipschitz maps between discrete tori ⋮ Sharp threshold for the Ising perceptron model ⋮ Unnamed Item ⋮ Geometric stability via information theory ⋮ Linear transformations of monotone functions on the discrete cube ⋮ A stability result for balanced dictatorships in Sn ⋮ Concentration on the Boolean hypercube via pathwise stochastic analysis ⋮ Boolean functions whose Fourier transform is concentrated on the first two levels.
