On testing computability by small width OBDDs

DOI10.1007/978-3-642-15369-3_43MaRDI QIDQ3588436zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Testing Computability by Width Two OBDDs
• Lower Bounds for Testing Computability by Small Width OBDDs
• Testing computability by width-two OBDDs
• Testing computability by width-2 OBDDs where the variable order is unknown
• Query learning of bounded-width OBDDs

Cited in

(18)

• Property testing lower bounds via a generalization of randomized parity decision trees
• An optimal tester for \(k\)-linear
• Second-order finite automata
• Exponentially improved algorithms and lower bounds for testing signed majorities
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• An optimal tester for k-Linear
• Lower Bounds for Testing Computability by Small Width OBDDs
• Testing computability by width-2 OBDDs where the variable order is unknown
• Finding Small OBDDs for Incompletely Specified Truth Tables Is Hard
• Testing Computability by Width Two OBDDs
• On the minimization of (complete) ordered binary decision diagrams
• On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
• Partially symmetric functions are efficiently isomorphism testable
• On approximating the number of relevant variables in a function
• Query learning of bounded-width OBDDs
• Query learning of bounded-width OBDDs
• Property testing lower bounds via communication complexity
• Testing computability by width-two OBDDs

This page was built for publication: On testing computability by small width OBDDs

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