Monotone Boolean formulas can approximate monotone linear threshold functions

DOI10.1016/j.dam.2004.02.003zbMath1122.68067OpenAlexW2048563093MaRDI QIDQ1878411

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

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

Related Items (4)

Biased halfspaces, noise sensitivity, and local Chernoff inequalities ⋮ A sprouting tree model for random boolean functions ⋮ Associative and commutative tree representations for Boolean functions ⋮ Monotone circuits for monotone weighted threshold functions

Cites Work

• Sorting in \(c \log n\) parallel steps
• Majority gates vs. general weighted threshold gates
• Short monotone formulae for the majority function
• On the Size of Weights for Threshold Gates
• Simulating Threshold Circuits by Majority Circuits
• Noise sensitivity of Boolean functions and applications to percolation
• Unnamed Item
• Unnamed Item
• Unnamed Item

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