Spectral properties of threshold functions
From MaRDI portal
Publication:1323477
DOI10.1007/BF01305949zbMath0810.94040OpenAlexW2060775054MaRDI QIDQ1323477
Publication date: 18 April 1995
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01305949
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
- 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
- Unnamed Item
