Monotone Boolean formulas can approximate monotone linear threshold functions

DOI10.1016/J.DAM.2004.02.003MaRDI QIDQ1878411zbMATH OpenOpenAlexFDO

Authors Rocco A. Servedio

Publication date 19 August 2004

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2004.02.003

zbMATH Keywords

Boolean formulasLinear threshold functionsMonotone computation

Mathematics Subject Classification ID

Boolean functions (06E30) Analysis of algorithms and problem complexity (68Q25)

Cites work

• scientific article; zbMATH DE number 176869 (Why is no real title available?)
• scientific article; zbMATH DE number 741240 (Why is no real title available?)
• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• Majority gates vs. general weighted threshold gates
• Noise sensitivity of Boolean functions and applications to percolation
• On the Size of Weights for Threshold Gates
• Short monotone formulae for the majority function
• Simulating Threshold Circuits by Majority Circuits
• Sorting in \(c \log n\) parallel steps

Cited in

(6)

• Monotone circuits for monotone weighted threshold functions
• Associative and commutative tree representations for Boolean functions
• scientific article; zbMATH DE number 3877103 (Why is no real title available?)
• A sprouting tree model for random boolean functions
• Biased halfspaces, noise sensitivity, and local Chernoff inequalities
• Reducing the share size of weighted threshold secret sharing schemes via Chow parameters approximation

This page was built for publication: Monotone Boolean formulas can approximate monotone linear threshold functions

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