Re: C-equivalence aware hash function



Francois Grieu wrote:

> daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner) wrote:
>
> > Can we view the nxn matrix M as the adjacency matrix of a bipartite
> > graph G(M) on 2n vertices?

> Things get so easy when David explain them...
>

True, true.
In fact I have forgotten you could swap rows and columns independently.

> Thus my problem seems a (harder) variant of graph isomorphism, and
> probably similar techniques apply.

I hope I'm not leading you in a wrong way.
The paper about Nauty in fact describes "Hadamard equivalence" on p.
82+ that is exactly your definition of C-equivalence, and shows how to
convert matrix containing +-1 to a graph. Perhaps this would work with
0 elements as well.
I wish I understood how that Nauty works... but the paper expects too
deep knowledge. Perhaps someone in a math newsgroup could help you.

Milan
.