Boolean functions with low average sensitivity depend on few coordinates
From MaRDI portal
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)- 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
- Secure non-interactive simulation from arbitrary joint distributions
- A structure theorem for almost low-degree functions on the slice
- Linear transformations of monotone functions on the discrete cube
- A generalization of a theorem of Rothschild and van Lint
- On the failure of concentration for the _-ball
- Simple juntas for shifted families
- Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
- Geometric influences
- On regular 3-wise intersecting families
- A structure theorem for Boolean functions with small total influences
- Log-Sobolev inequality for the multislice, with applications
- scientific article; zbMATH DE number 6351494 (Why is no real title available?)
- An orthogonal basis for functions over a slice of the Boolean hypercube
- Boolean functions: influence, threshold and noise
- Intersecting Families are Essentially Contained in Juntas
- On the round complexity of randomized Byzantine agreement
- A stability result for balanced dictatorships in \(S_n\)
- Stability for vertex isoperimetry in the cube
- Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
- Shadows of ordered graphs
- Sharp thresholds of graph properties, and the $k$-sat problem
- Vertex-isoperimetric stability in the hypercube
- Pseudo-average block sensitivity equals average sensitivity
- Hypercontractivity for global functions and sharp thresholds
- Noise sensitivity of Boolean functions and applications to percolation
- Randomly colouring graphs (a combinatorial view)
- On the structure of subsets of the discrete cube with small edge boundary
- Noise stability of functions with low influences: invariance and optimality
- A stability result for the cube edge isoperimetric inequality
- A simple reduction from a biased measure on the discrete cube to the uniform measure
- The average sensitivity of square-freeness
- Hypercontractivity on the symmetric group
- Around two theorems and a lemma by Lucio Russo
- scientific article; zbMATH DE number 7559077 (Why is no real title available?)
- Towards a proof of the Fourier-entropy conjecture?
- On the influences of variables on Boolean functions in product spaces
- scientific article; zbMATH DE number 1966606 (Why is no real title available?)
- On the efficiency of the probabilistic neutral bits method in statistical cryptanalysis of synchronous stream ciphers
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- KKL's influence on me
- Mathematics of computation through the lens of linear equations and lattices
- Average sensitivity of nested canalizing multivalued functions
- 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
- Improved approximation of linear threshold functions
- The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
- Friedgut-Kalai-Naor theorem for slices of the Boolean cube
- Decision Trees and Influences of Variables Over Product Probability Spaces
- Optimal bounds on approximation of submodular and XOS functions by juntas
- Dimension-free discretizations of the uniform norm by small product sets
- Juntas in the \(\ell_{1}\)-grid and Lipschitz maps between discrete tori
- Edge-Isoperimetric Inequalities and Influences
- Quantitative relation between noise sensitivity and influences
- A quasi-stability result for dictatorships in \(S_n\)
- On a biased edge isoperimetric inequality for the discrete cube
- Sharp threshold for the Ising perceptron model
- Intersecting families of permutations
- On the Fourier tails of bounded functions over the discrete cube
- Fourier analysis and large independent sets in powers of complete graphs
- A generalization of a theorem of Rothschild and van Lint
- 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)
