Re: C-equivalence aware hash function

Milan VXdgsvt wrote:
>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.
>
>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).

Well, phooey. You're absolutely right, of course.

Greg Rose showed that my proposal still doesn't work even if we omit the
polarity issue. So this is considerably harder than I realized. Darn.

Thanks for correcting my error.
Received on Sat Dec 3 04:20:28 2005