Thomas Thierauf

We investigate the computational complexity of the

isomorphism problem for one-time-only branching programs (BP1-Iso):

on input of two one-time-only branching programs B and B',

decide whether there exists a permutation of the variables of B'

such that it becomes equivalent to B.

Our main result is a two-round interactive ... more >>>