Paper Info
Title
A Deterministic Algorithm For Testing The Equivalence Of Read-Once Branching Programs With Small Discrepancy
Abstract
The problem to test the equivalence of two given read-once branching programs is a well-known problem in the class BPP that is not known to be solvable in deterministic polynomial time. The standard probabilistic algorithm to solve the problem reduces it to an instance of Polynomial Identity Testing and then applies the Schwartz-Zippel Lemma to test the equivalence. This method needs O(n log n) random bits, where n is the number of variables in the branching programs. We provide a new method for testing the equivalence of read-once branching programs that uses O(log n + log vertical bar D vertical bar) random bits, where D is the set of assignments for which the two branching programs compute different results. This means O(n) random bits in the worst case and a deterministic polynomial time algorithm when the discrepancy set D is at most polynomial.We also show that the equivalence test can be extended to the more powerful model of deterministic, decomposable negation normal forms (d-DNNFs).
Year
DOI
Venue
2017
10.1007/978-3-319-58741-7_13
UNVEILING DYNAMICS AND COMPLEXITY, CIE 2017
Field
DocType
Volume
Polynomial identity testing,Discrete mathematics,Binary logarithm,Randomized algorithm,Combinatorics,Polynomial,Equivalence (measure theory),Deterministic algorithm,Time complexity,Lemma (mathematics),Mathematics
Conference
10307
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
4
2
Name
Order
Citations
PageRank
Stefan Arnold100.34
Jacobo Torán256449.26