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

   To canonicalize, you also have to disambiguate the polarity reversal
criteria for matrices with an even number of rows or an even number of
columns. Both of the matrices

   1 -1
   1 -1

and

   1 -1
  -1 1

are canonical under Dr. Wagner's specification in that they have sorted
columns and rows, and do not invite polarity inversion. But they are
C-equivalent.

--Mike Amling
Received on Sat Dec 3 04:20:16 2005