Weights of exact threshold functions

DOI10.1070/IM9113MaRDI QIDQ5033984zbMATH OpenOpenAlexFDO

Authors László Babai, Kristoffer Arnsfelt Hansen, Xiaoming Sun, Vladimir V. Podolskii

Publication date 24 February 2022

Published in Izvestiya: Mathematics (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/izv9113

zbMATH Keywords

anti-Hadamard matricesBoolean functionscomputational complexitypolynomial threshold functionsthreshold functions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Boolean functions (94D10)

Recommendations

• Weights of exact threshold functions
• A better upper bound on weights of exact threshold functions
• Degree-uniform lower bound on the weights of polynomials with given sign function
• Lower bound on weights of large degree threshold functions
• Lower bound on weights of large degree threshold functions

Cites work

• A better upper bound on weights of exact threshold functions
• A complex-number Fourier technique for lower bounds on the mod-\(m\) degree
• A construction for sets of integers with distinct subset sums
• A linear lower bound on the unbounded error probabilistic communication complexity.
• A Lower Bound of the Number of Threshold Functions
• A Uniform Lower Bound on Weights of Perceptrons
• An improved lower bound on the greatest element of a sum-distinct set of fixed order
• Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
• Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates
• Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
• Determinants Whose Elements Are 0 and 1
• Geometric sets of low information content
• scientific article; zbMATH DE number 3121715 (Why is no real title available?)
• scientific article; zbMATH DE number 1301088 (Why is no real title available?)
• scientific article; zbMATH DE number 1538119 (Why is no real title available?)
• scientific article; zbMATH DE number 872005 (Why is no real title available?)
• scientific article; zbMATH DE number 7250146 (Why is no real title available?)
• scientific article; zbMATH DE number 3331985 (Why is no real title available?)
• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
• On the Size of Weights for Threshold Gates
• Perceptrons of large weight
• Perceptrons, PP, and the polynomial hierarchy
• Polynomial threshold functions and Boolean threshold circuits
• Siegel's Lemma and sum-distinct sets
• Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
• Theory of majority decision elements
• Threshold circuits of bounded depth
• Weights of exact threshold functions

Cited in

(4)

• Threshold functions
• A better upper bound on weights of exact threshold functions
• Weights of exact threshold functions
• scientific article; zbMATH DE number 3313265 (Why is no real title available?)

This page was built for publication: Weights of exact threshold functions

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