On the geometric separability of Boolean functions

DOI10.1016/0166-218X(94)00161-6zbMath0854.68034OpenAlexW2057727486MaRDI QIDQ1917289

Nimrod Megiddo, Tibor Hegedűs

Publication date: 13 January 1997

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

Full work available at URL: https://doi.org/10.1016/0166-218x(94)00161-6

zbMATH Keywords

Boolean functionsMEMBERSHIP problem

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Boolean functions (06E30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results ⋮ On connected Boolean functions ⋮ On the complexity of problems on simple games ⋮ Simple games versus weighted voting games: bounding the critical threshold value ⋮ Training a Single Sigmoidal Neuron Is Hard ⋮ On the Nonlearnability of a Single Spiking Neuron ⋮ Enumerating Hassett’s Wall and Chamber Decomposition of the Moduli Space of Weighted Stable Curves

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The threshold order of a Boolean function
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• Recognition problems for special classes of polynomials in 0-1 variables
• The Complexity of the Partial Order Dimension Problem
• Computational limitations on learning from examples
• The minimum consistent DFA problem cannot be approximated within any polynomial
• Threshold Numbers and Threshold Completions

This page was built for publication: On the geometric separability of Boolean functions