Testing computability by width-two OBDDs

DOI10.1016/j.tcs.2011.11.007zbMath1234.68462OpenAlexW2052134969MaRDI QIDQ764366

Gilad Tsur, Dana Ron

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

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

Related Items

An adaptivity hierarchy theorem for property testing, On the minimization of (complete) ordered binary decision diagrams, Lower Bounds for Testing Computability by Small Width OBDDs, Exponentially improved algorithms and lower bounds for testing signed majorities

Cites Work

• Unnamed Item
• On learning width two branching programs
• Testing juntas
• Property testing lower bounds via communication complexity
• On the distributional complexity of disjointness
• Self-testing/correcting with applications to numerical problems
• An efficient query learning algorithm for ordered binary decision diagrams
• Lower Bounds for Testing Computability by Small Width OBDDs
• Testing low-degree polynomials over prime fields
• Testing Membership in Languages that Have Small Width Branching Programs
• Property testing and its connection to learning and approximation
• Testing Reed–Muller Codes
• Testing Computability by Width-2 OBDDs Where the Variable Order is Unknown
• On Testing Computability by Small Width OBDDs
• Testing Computability by Width Two OBDDs
• Testing Basic Boolean Formulae
• Communication Complexity
• Robust Characterizations of Polynomials with Applications to Program Testing
• lgorithmic and Analysis Techniques in Property Testing
• Query learning of bounded-width OBDDs
• Testing problems with sublearning sample complexity