A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy

DOI10.1007/978-3-319-58741-7_13zbMath1489.68398OpenAlexW2612590159MaRDI QIDQ2011643

Stefan Arnold, Jacobo Toran

Publication date: 4 August 2017

Full work available at URL: https://doi.org/10.1007/978-3-319-58741-7_13

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching is as easy as matrix inversion
• Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
• Modified branching programs and their computational power
• The Polynomially Bounded Perfect Matching Problem Is in NC 2
• Graph-Based Algorithms for Boolean Function Manipulation
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
• Branching Programs and Binary Decision Diagrams
• Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
• Decomposable negation normal form