Re: C-equivalence aware hash function

David Wagner wrote:

> Given a matrix M, you can first canonicalize it with respect to
> polarity (e.g., by making each column have minimum number of positive
> elements), then canonicalize it with respect to column-swaps (by
> sorting the columns), and finally canonicalize it with respect to
> row-swaps (by sorting the rows). The result will be canonical
> representative for M with respect to C-equivalent. You can then
> hash that canonical representative.
>
> Does this work?

I don't think so.

Matrix 1: Matrix 2:

 -1 -1 -1 -1 -1 -1
 -1 -1 0 -1 -1 1
 -1 1 -1 -1 0 -1

All columns and rows are normalized to polarity, columns are sorted,
rows are sorted, so your algo does nothing to these. They are
different, but C-equivalent (just swap the row 2 and 3, then column 2
and 3).

To save your time, if you invert the Polarity step (maximize +
elements), the matrices would be:

 -1 0 1 -1 1 1
  1 -1 1 0 -1 1
  1 1 -1 1 1 -1

Perhaps someone could show this is as hard as a graph isomorphism?

  Milan
Received on Sat Dec 3 04:20:15 2005