On learning width two branching programs

DOI10.1016/S0020-0190(97)00204-4MaRDI QIDQ293246zbMATH OpenFDO

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

zbMATH Keywords

branching programPAC learning

Mathematics Subject Classification ID

Computational learning theory (68Q32)

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

Cites work

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

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
• Testing computability by width-two OBDDs
• Efficient learning algorithms yield circuit lower bounds

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)