Lower Bounds for Testing Computability by Small Width OBDDs

DOI10.1007/978-3-642-20877-5_32zbMath1331.68088MaRDI 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

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W20: Randomized algorithms

Related Items

On the minimization of (complete) ordered binary decision diagrams, Property testing lower bounds via communication complexity, Testing computability by width-two OBDDs, An adaptivity hierarchy theorem for property testing, 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