Spectral properties of threshold functions

DOI10.1007/BF01305949MaRDI QIDQ1323477zbMATH OpenOpenAlexFDO

Authors 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

Boolean functionsFourier transformlinear threshold functionsspectrumWalsh functions

Mathematics Subject Classification ID

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

Recommendations

• Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms
• Harmonic Analysis of Polynomial Threshold Functions
• Spectral norm of symmetric functions
• Improved approximation of linear threshold functions

Cites work

• An identity in combinatorial extremal theory
• Chow Parameters in Threshold Logic
• Harmonic Analysis of Polynomial Threshold Functions
• scientific article; zbMATH DE number 3271087 (Why is no real title available?)
• Hyperplane cuts of an n-cube
• Neural networks and physical systems with emergent collective computational abilities
• Non-uniform automata over groups
• On mod \(p\) transversals
• Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms
• The best constants in the Khintchine inequality

Cited in

(23)

• Threshold functions
• A sensitivity estimate for Boolean functions
• Vector analysis of threshold functions
• On the ``majority is least stable conjecture
• Separation results for Boolean function classes
• Combined weight and density bounds on the polynomial threshold function representation of Boolean functions
• Inferring Boolean functions via higher-order correlations
• An upper bound for the relative influence of variables on Boolean functions
• Sign-representation of Boolean functions using a small number of monomials
• Harmonic Analysis of Polynomial Threshold Functions
• The average sensitivity of an intersection of half spaces
• Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms
• Locally monotone Boolean and pseudo-Boolean functions
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• scientific article; zbMATH DE number 2114156 (Why is no real title available?)
• The correct exponent for the Gotsman-Linial conjecture
• Anticoncentration for subgraph statistics
• scientific article; zbMATH DE number 7297102 (Why is no real title available?)
• Biased halfspaces, noise sensitivity, and local Chernoff inequalities
• Local maxima of quadratic Boolean functions
• The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions
• Resolution of the quadratic Littlewood-Offord problem
• Nondegenerate hyperplane covers of the hypercube

This page was built for publication: Spectral properties of threshold functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1323477)