We consider two versions of the problem of testing graph isomorphism in the bounded-degree graph model: A version in which one graph is fixed, and a version in which the input consists of two graphs.
We essentially determine the query complexity of these testing problems in the special case of ... more >>>