A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
From MaRDI portal
Publication:2011643
DOI10.1007/978-3-319-58741-7_13zbMATH Open1489.68398OpenAlexW2612590159MaRDI QIDQ2011643FDOQ2011643
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
Recommendations
Cites Work
- Graph-Based Algorithms for Boolean Function Manipulation
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Branching Programs and Binary Decision Diagrams
- Title not available (Why is that?)
- On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
- Title not available (Why is that?)
- Matching is as easy as matrix inversion
- Decomposable negation normal form
- Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
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)
