Lower Bounds for Testing Computability by Small Width OBDDs

DOI10.1007/978-3-642-20877-5_32zbMath1331.68088OpenAlexW1807114442MaRDI QIDQ3010413

Chenggang Wu, Joshua Brody, Kevin Matulef

Publication date: 1 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20877-5_32

Mathematics Subject Classification ID

Related Items (5)

An adaptivity hierarchy theorem for property testing ⋮ On the minimization of (complete) ordered binary decision diagrams ⋮ Property testing lower bounds via communication complexity ⋮ Testing computability by width-two OBDDs ⋮ Exponentially improved algorithms and lower bounds for testing signed majorities

Cites Work

• Unnamed Item
• Unnamed Item
• On learning width two branching programs
• Testing juntas
• Property testing lower bounds via communication complexity
• Testing computability by width-two OBDDs
• Self-testing/correcting with applications to numerical problems
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Recognizing well-parenthesized expressions in the streaming model
• Property testing and its connection to learning and approximation
• Improved Bounds for Testing Juntas
• Testing Computability by Width-2 OBDDs Where the Variable Order is Unknown
• Monotonicity testing over general poset domains
• On Testing Computability by Small Width OBDDs
• Testing Computability by Width Two OBDDs
• Testing Basic Boolean Formulae
• Communication Complexity
• Testing juntas nearly optimally
• lgorithmic and Analysis Techniques in Property Testing
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Lower Bounds for Sparse Recovery
• Testing monotonicity

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