Spectral properties of threshold functions

DOI10.1007/BF01305949zbMath0810.94040OpenAlexW2060775054MaRDI QIDQ1323477

Craig Gotsman, Nathan Linial

Publication date: 18 April 1995

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01305949

zbMATH Keywords

Fourier transformWalsh functionsspectrumBoolean functionslinear threshold functions

Mathematics Subject Classification ID

Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) (42C10) Boolean functions (06E30)

Related Items

Separation results for Boolean function classes ⋮ Biased halfspaces, noise sensitivity, and local Chernoff inequalities ⋮ Sign-representation of Boolean functions using a small number of monomials ⋮ A sensitivity estimate for Boolean functions ⋮ Combined weight and density bounds on the polynomial threshold function representation of Boolean functions ⋮ The average sensitivity of an intersection of half spaces ⋮ Local Maxima of Quadratic Boolean Functions ⋮ Locally monotone Boolean and pseudo-Boolean functions ⋮ The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions ⋮ The correct exponent for the Gotsman-Linial conjecture ⋮ Inferring Boolean functions via higher-order correlations ⋮ A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry ⋮ Anticoncentration for subgraph statistics ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ On the ``majority is least stable conjecture

Cites Work

• Unnamed Item
• Non-uniform automata over groups
• An identity in combinatorial extremal theory
• On mod \(p\) transversals
• Hyperplane cuts of an n-cube
• Harmonic Analysis of Polynomial Threshold Functions
• The best constants in the Khintchine inequality
• Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
• Neural networks and physical systems with emergent collective computational abilities.
• Chow Parameters in Threshold Logic