Lower Bounds for Testing Computability by Small Width OBDDs
From MaRDI portal
Publication:3010413
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
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
