We investigate the computational complexity of the Boolean Isomorphism problem (BI): on input of two Boolean formulas F and G decide whether there exists a permutation of the variables of G such that F and G become equivalent. Our main result is a one-round interactive proof for $\overline{BI}$, where the ... more >>>

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 proof ... more >>>

For a permutation group $G$ acting on the set $\Omega$ we say that two strings $x,y\,:\,\Omega\to\boole$ are {\em $G$-isomorphic} if they are equivalent under the action of $G$, \ie, if for some $\pi\in G$ we have $x(i^{\pi})=y(i)$ for all $i\in\Omega$. Cyclic Shift, Graph Isomorphism and Hypergraph Isomorphism are special cases, ... more >>>