On learning width two branching programs

DOI10.1016/S0020-0190(97)00204-4zbMATH Open1339.68129MaRDI QIDQ293246FDOQ293246

Authors: Nader H. Bshouty, C. 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

Recommendations

• Bounds for Width Two Branching Programs
• Query learning of bounded-width OBDDs
• Query learning of bounded-width OBDDs
• On learning monotone DNF under product distributions
• scientific article; zbMATH DE number 1804125

zbMATH Keywords

branching programPAC learning

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Cites Work

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

Cited In (5)

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

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

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