« first day (1914 days earlier)      last day (1715 days later) » 

vzn
vzn
4:44 AM
 
 
3 hours later…
Jarek Duda
Jarek Duda
7:30 AM
space quantum force? :)
 
 
3 hours later…
Jarek Duda
Jarek Duda
10:06 AM
0
Q: Testing if two matrices differ only by permutation? (generalized graph isomorphism problem)

Jarek DudaIn graph isomorphism problem, for which Babai's quasi polynomial algorithm is currently under review (stack), we ask if two adjacency matrices: of $\{0,1\}$ coefficients differ only by a permutation. Is general problem: without coefficient restriction more difficult, or we can also assume that ...

linear-algebra matrices matrix-equations graph-isomorphism invariance
@ThomasKlimpel, simplified invariants above - directly for adjacency matrix, distinguish SRGs in tests
 
 
5 hours later…
vzn
vzn
3:32 PM
 
Jarek Duda
Jarek Duda
4:02 PM
Thanks, I will think about. Generally hard examples for standard approach (Weisfeiler-Leman) are different than for what I do - e.g. now trying to restrict the space of possible similarity matrices between them to only permutation.
We need operation which is invariant for permutation, but not for other orthogonal operations - and I finally got a simple one which distinguishes at least some SRGs ... the problem is showing that they provide sufficient condition
 

« first day (1914 days earlier)      last day (1715 days later) »