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

DOI10.1007/978-3-319-58741-7_13MaRDI QIDQ2011643zbMATH OpenOpenAlexFDO

Authors Stefan Arnold, Jacobo Torán

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

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

Recommendations

• A characterization and nearly linear-time equivalence test for -branching programs
• scientific article; zbMATH DE number 1962823
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 2102760
• scientific article; zbMATH DE number 1332670

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3594626 (Why is no real title available?)
• scientific article; zbMATH DE number 1220163 (Why is no real title available?)
• scientific article; zbMATH DE number 1946853 (Why is no real title available?)
• Branching Programs and Binary Decision Diagrams
• Decomposable negation normal form
• Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Graph-Based Algorithms for Boolean Function Manipulation
• Matching is as easy as matrix inversion
• Modified branching programs and their computational power
• On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
• Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
• The Polynomially Bounded Perfect Matching Problem Is in NC 2

Cited in

(3)

• A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict
• Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
• Deterministic identity testing for sum of read-once oblivious arithmetic branching programs

This page was built for publication: A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011643)