Boolean functions with low average sensitivity depend on few coordinates
From MaRDI portal
Publication:1280280
DOI10.1007/PL00009809zbMATH Open0909.06008OpenAlexW1986296546WikidataQ62111466 ScholiaQ62111466MaRDI QIDQ1280280FDOQ1280280
Authors: Ehud Friedgut 
Publication date: 14 March 1999
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/pl00009809
Recommendations
- A sensitivity estimate for Boolean functions
- scientific article; zbMATH DE number 6850428
- Sensitivity versus block sensitivity of Boolean functions
- Exclusion sensitivity of Boolean functions
- Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
- Sensitivity vs. block sensitivity of Boolean functions
- scientific article; zbMATH DE number 714510
- On the sensitivity to noise of a Boolean function
- Sensitivity of Boolean formulas
- scientific article; zbMATH DE number 2062211
Cited In (72)
- Secure non-interactive simulation from arbitrary joint distributions
- Title not available (Why is that?)
- 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
- Dimension-free discretizations of the uniform norm by small product sets
- The simplified weighted sum function and its average sensitivity
- Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions
- On set systems without a simplex-cluster and the junta method
- A structure theorem for almost low-degree functions on the slice
- A generalization of a theorem of Rothschild and van Lint
- Linear transformations of monotone functions on the discrete cube
- Simple juntas for shifted families
- On the failure of concentration for the \(\ell_\infty\)-ball
- Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
- On regular 3-wise intersecting families
- Log-Sobolev inequality for the multislice, with applications
- Geometric influences
- An orthogonal basis for functions over a slice of the Boolean hypercube
- A structure theorem for Boolean functions with small total influences
- Intersecting Families are Essentially Contained in Juntas
- Boolean functions: influence, threshold and noise
- A stability result for balanced dictatorships in \(S_n\)
- On the round complexity of randomized Byzantine agreement
- Sharp thresholds of graph properties, and the $k$-sat problem
- Stability for vertex isoperimetry in the cube
- Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
- Shadows of ordered graphs
- Vertex-isoperimetric stability in the hypercube
- Hypercontractivity for global functions and sharp thresholds
- Noise sensitivity of Boolean functions and applications to percolation
- Pseudo-average block sensitivity equals average sensitivity
- On the structure of subsets of the discrete cube with small edge boundary
- Randomly colouring graphs (a combinatorial view)
- Noise stability of functions with low influences: invariance and optimality
- A stability result for the cube edge isoperimetric inequality
- The average sensitivity of square-freeness
- A simple reduction from a biased measure on the discrete cube to the uniform measure
- Title not available (Why is that?)
- Around two theorems and a lemma by Lucio Russo
- Towards a proof of the Fourier-entropy conjecture?
- Title not available (Why is that?)
- On the influences of variables on Boolean functions in product spaces
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- On the efficiency of the probabilistic neutral bits method in statistical cryptanalysis of synchronous stream ciphers
- A note on the entropy/influence conjecture
- Hypergraph removal lemmas via robust sharp threshold theorems
- High dimensional Hoffman bound and applications in extremal combinatorics
- DNF sparsification and a faster deterministic counting algorithm
- Bi-Lipschitz bijection between the Boolean cube and the Hamming ball
- Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
- On the sensitivity to noise of a Boolean function
- Almost isoperimetric subsets of the discrete cube
- Boolean functions whose Fourier transform is concentrated on the first two levels.
- Geometric stability via information theory
- The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
- Improved approximation of linear threshold functions
- Friedgut-Kalai-Naor theorem for slices of the Boolean cube
- Decision Trees and Influences of Variables Over Product Probability Spaces
- Edge-Isoperimetric Inequalities and Influences
- Optimal bounds on approximation of submodular and XOS functions by juntas
- Juntas in the \(\ell_{1}\)-grid and Lipschitz maps between discrete tori
- Quantitative relation between noise sensitivity and influences
- Intersecting families of permutations
- On a biased edge isoperimetric inequality for the discrete cube
- Sharp threshold for the Ising perceptron model
- A quasi-stability result for dictatorships in \(S_n\)
- A generalization of a theorem of Rothschild and van Lint
- On the Fourier tails of bounded functions over the discrete cube
- Fourier analysis and large independent sets in powers of complete graphs
- Concentration on the Boolean hypercube via pathwise stochastic analysis
This page was built for publication: Boolean functions with low average sensitivity depend on few coordinates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1280280)
