Re: C-equivalence aware hash function

In article <dmju8r$d9$2@agate.berkeley.edu>,
David Wagner <daw-usenet@taverner.cs.berkeley.edu> wrote:
<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.

Our error... indeed it is a hard (and
interesting) problem. Francois seems to have
already thought of everything that I was thinking
of.

The only thing I can think of to contribute at
this point is that it should be possible to define
some sort of holistic metric for a matrix, and
then use hill-climbing or simulated annealing. But
neither of these techniques will ever *prove* that
you've reached a canonical form, they'll just make
finding counterexamples harder.

Greg.

-- 
Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au