Boolean functions whose Fourier transform is concentrated on the first two levels.
From MaRDI portal
Publication:1866179
DOI10.1016/S0196-8858(02)00024-6zbMath1039.91014WikidataQ62111464 ScholiaQ62111464MaRDI QIDQ1866179
Assaf Naor, Ehud Friedgut, Gil Kalai
Publication date: 3 April 2003
Published in: Advances in Applied Mathematics (Search for Journal in Brave)
Related Items
Boolean degree 1 functions on some classical association schemes, An orthogonal basis for functions over a slice of the Boolean hypercube, Application of hypergraph Hoffman's bound to intersecting families, Probabilistic view of voting, paradoxes, and manipulation, Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions, Boolean functions with small second-order influences on the discrete cube, On the \(\Phi \)-stability and related conjectures, Boolean functions on $S_n$ which are nearly linear, KKL's influence on me, Shadows of ordered graphs, Stability for intersecting families in \(\mathrm{PGL}(2,q)\), An isoperimetric inequality for the Hamming cube and some consequences, Unnamed Item, Unnamed Item, On a biased edge isoperimetric inequality for the discrete cube, Randomly colouring graphs (a combinatorial view), A structure theorem for almost low-degree functions on the slice, Between Arrow and Gibbard-Satterthwaite. A representation theoretic approach, Almost Isoperimetric Subsets of the Discrete Cube, LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY, Fourier analysis and large independent sets in powers of complete graphs, Decision Trees and Influences of Variables Over Product Probability Spaces, On the structure of subsets of the discrete cube with small edge boundary, Revisiting alphabet reduction in Dinur’s PCP., Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality, A quasi-stability result for dictatorships in \(S_n\), Intersecting families of permutations, On the Fourier tails of bounded functions over the discrete cube, On the measure of intersecting families, uniqueness and stability, Noise stability of functions with low influences: invariance and optimality, Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width, Stability versions of Erdős-Ko-Rado type theorems via isoperimetry, A generalization of a theorem of Rothschild and van Lint, Removal and Stability for Erdös--Ko--Rado, A generalization of a theorem of Rothschild and van Lint, Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas, FKN theorem for the multislice, with applications, A stability result for balanced dictatorships in Sn
Cites Work
- Unnamed Item
- Inequalities in Fourier analysis
- A note on the edges of the n-cube
- Boolean functions with low average sensitivity depend on few coordinates
- A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- On the best constants in the Khinchin inequality
- Projection constants of symmetric spaces and variants of Khintchine's inequality
