Lower Bounds for Testing Computability by Small Width OBDDs

DOI10.1007/978-3-642-20877-5_32MaRDI QIDQ3010413zbMATH OpenOpenAlexFDO

Authors Joshua Brody, Kevin Matulef, Chenggang Wu

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

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Recommendations

• On testing computability by small width OBDDs
• Testing computability by width-two OBDDs
• Testing Computability by Width Two OBDDs
• Testing computability by width-2 OBDDs where the variable order is unknown
• scientific article; zbMATH DE number 1335889
• Lower Bounds on OBDD Proofs with Several Orders
• Lower bounds for the lengths of single tests for Boolean circuits
• scientific article; zbMATH DE number 4087011
• Fine-grained complexity lower bounds for problems in computer aided verification
• On the size of (generalized) OBDDs for threshold functions

Cites work

• Algorithmic and analysis techniques in property testing
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Communication Complexity
• Improved Bounds for Testing Juntas
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Lower bounds for sparse recovery
• Monotonicity testing over general poset domains
• On learning width two branching programs
• On testing computability by small width OBDDs
• On the exact space complexity of sketching and streaming small norms
• Property testing and its connection to learning and approximation
• Property testing lower bounds via communication complexity
• Recognizing well-parenthesized expressions in the streaming model
• Self-testing/correcting with applications to numerical problems
• Testing Basic Boolean Formulae
• Testing Computability by Width Two OBDDs
• Testing computability by width-2 OBDDs where the variable order is unknown
• Testing computability by width-two OBDDs
• Testing juntas
• Testing juntas nearly optimally
• Testing monotonicity
• The randomized communication complexity of set disjointness

Cited in

(13)

• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• An adaptivity hierarchy theorem for property testing
• Exponentially improved algorithms and lower bounds for testing signed majorities
• Testing computability by width-2 OBDDs where the variable order is unknown
• On testing computability by small width OBDDs
• Finding Small OBDDs for Incompletely Specified Truth Tables Is Hard
• Testing Computability by Width Two OBDDs
• scientific article; zbMATH DE number 1500659 (Why is no real title available?)
• On the minimization of (complete) ordered binary decision diagrams
• 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: Lower Bounds for 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 Q3010413)