# Mohammad Bavarian: Equivalence of Read-Once Branching Programs

I was going to nominate NL=Co-NL but I thought some people might already comment on that.

For me, one of the very surprising algorithm I saw recently was the randomized algorithm for equivalence of read-once branching programs.

As usual when faced with such a problem, you tell yourself that two once-read branching programs could be almost but a single input out of 2^n possible inputs could behave the same so to efficiently decide the equivalency looks like an impossible task. The great thing is the read-once property allows you to extend the notion of branching programs to much larger set of inputs, *while preserving consistency*. By going over a suitably large finite field. you extend the input range of variables of the branching program, while preserving the fact that the (multilinear) polynomial you get from two branching program is the same iff they are equivalent. The equivalence test then follows from another great algorithm polynomial identity testing.

This whole consistent arithmetization I think is a wonderful and surprising gem in this case.