On the Size of Weights for Threshold Gates

From MaRDI portal
Publication:4307054

DOI10.1137/S0895480192235878zbMath0811.68100OpenAlexW2098730982MaRDI QIDQ4307054

Johan T. Håstad

Publication date: 26 September 1994

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480192235878



Related Items

Weights of exact threshold functions, Monotone Boolean formulas can approximate monotone linear threshold functions, Combined weight and density bounds on the polynomial threshold function representation of Boolean functions, On PAC learning algorithms for rich Boolean function classes, Breaking the Minsky--Papert Barrier for Constant-Depth Circuits, General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results, Trading transforms of non-weighted simple games and integer weights of weighted simple games, On the number of irreducible points in polyhedra, A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting, Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs, A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length, Improved approximation of linear threshold functions, The inverse Shapley value problem, Sparse weighted voting classifier selection and its linear programming relaxations, Patience of matrix games, The hardest halfspace, A Better Upper Bound on Weights of Exact Threshold Functions, The communication complexity of addition, On the constructive characterization of threshold functions, Vectors in a box, Degree-uniform lower bound on the weights of polynomials with given sign function, Perceptrons of large weight, A linear relation between input and first layer in neural networks, Quantum matchgate computations and linear threshold gates, Unnamed Item, Monotone circuits for monotone weighted threshold functions, Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors