Skip to content

Mohammad Bavarian: Equivalence of Read-Once Branching Programs

by on February 19, 2012

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.

Advertisements
Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: