On Testing Computability by Small Width OBDDs

DOI10.1007/978-3-642-15369-3_43zbMath1305.68330OpenAlexW1537743430MaRDI QIDQ3588436

Oded Goldreich

Publication date: 10 September 2010

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-15369-3_43

zbMATH Keywords

property testingsmall width OBDDs

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Related Items (12)

An optimal tester for \(k\)-linear ⋮ Second-order finite automata ⋮ On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing ⋮ An optimal tester for \(k\)-Linear ⋮ On the minimization of (complete) ordered binary decision diagrams ⋮ Lower Bounds for Testing Computability by Small Width OBDDs ⋮ Property testing lower bounds via a generalization of randomized parity decision trees ⋮ Property testing lower bounds via communication complexity ⋮ On Approximating the Number of Relevant Variables in a Function ⋮ Testing computability by width-two OBDDs ⋮ Partially Symmetric Functions Are Efficiently Isomorphism Testable ⋮ Exponentially improved algorithms and lower bounds for testing signed majorities

This page was built for publication: On Testing Computability by Small Width OBDDs