Testing computability by width-two OBDDs

DOI10.1016/J.TCS.2011.11.007MaRDI QIDQ764366zbMATH OpenOpenAlexFDO

Authors Dana Ron, Gilad Tsur

Publication date 13 March 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.11.007

zbMATH Keywords

property testingordered binary decision diagram (OBDD)

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• Testing Computability by Width Two OBDDs
• Testing computability by width-2 OBDDs where the variable order is unknown
• Lower Bounds for Testing Computability by Small Width OBDDs
• On testing computability by small width OBDDs
• On the Width of Ordered Binary Decision Diagrams

Cites work

• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• Algorithmic and analysis techniques in property testing
• An efficient query learning algorithm for ordered binary decision diagrams
• Communication Complexity
• Lower Bounds for Testing Computability by Small Width OBDDs
• On learning width two branching programs
• On testing computability by small width OBDDs
• On the distributional complexity of disjointness
• Property testing and its connection to learning and approximation
• Property testing lower bounds via communication complexity
• Query learning of bounded-width OBDDs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Testing Basic Boolean Formulae
• Testing Computability by Width Two OBDDs
• Testing Membership in Languages that Have Small Width Branching Programs
• Testing Reed–Muller Codes
• Testing computability by width-2 OBDDs where the variable order is unknown
• Testing juntas
• Testing low-degree polynomials over prime fields
• Testing problems with sublearning sample complexity

Cited in

(8)

• On testing computability by small width OBDDs
• An adaptivity hierarchy theorem for property testing
• Functions that have read‐twice constant width branching programs are not necessarily testable
• Lower Bounds for Testing Computability by Small Width OBDDs
• Exponentially improved algorithms and lower bounds for testing signed majorities
• Testing Computability by Width Two OBDDs
• On the minimization of (complete) ordered binary decision diagrams
• Testing computability by width-2 OBDDs where the variable order is unknown

This page was built for publication: Testing computability by width-two OBDDs

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