On learning width two branching programs

DOI10.1016/S0020-0190(97)00204-4zbMath1339.68129MaRDI QIDQ293246

Nader H. Bshouty, Christino Tamon, David K. Wilson

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097002044?np=y

zbMATH Keywords

PAC learningbranching program

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Related Items (5)

On PAC learning algorithms for rich Boolean function classes ⋮ Lower Bounds for Testing Computability by Small Width OBDDs ⋮ Efficient learning algorithms yield circuit lower bounds ⋮ Testing computability by width-two OBDDs ⋮ An efficient query learning algorithm for ordered binary decision diagrams

Cites Work

• Occam's razor
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• When won't membership queries help?
• Queries and concept learning
• A theory of the learnable
• Bounds for Width Two Branching Programs

This page was built for publication: On learning width two branching programs