Testing computability by width-two OBDDs

DOI10.1016/J.TCS.2011.11.007zbMATH Open1234.68462OpenAlexW2052134969MaRDI QIDQ764366FDOQ764366

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

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

zbMATH Keywords

property testingordered binary decision diagram (OBDD)

Mathematics Subject Classification ID

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

Cites Work

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