7:36 AM
@ThomasKlimpel, indeed this general permutation test is for graph with colored edges - I don't know if it can be polynomially converted to standard GI?
But generally I posted it in Mathematics as I believe algorithmic treatment, way of thinking is useful for this problem - instead of local vertex descriptions with canonical labelization, use global descriptors/invariants - to get complete description modulo permutation
Testing similarity is a simple example ensuring orthogonal O between two matrices - there remains question if there is permutation among them
So we need complementing tests to restrict the space of possible O matrices, hopefully down to permutations - and finally after a year of (among others) working on this I am able to distinguish the toughest cases this way: SRGs
3 hours later…
10:54 AM
0
Assume we have two real symmetric $n\times n$ matrices: $A, B$. We can easily test their similarity: $\textrm{Tr}(A^k)=\textrm{Tr}(B^k)$ for $k=1..n$. In this case both can be rotated to the same diagonal matrix $D=\textrm{diag}(\{\lambda_i\})$ made of their eigenvalues - there exist orthogonal $...
11:23 AM
@JarekDuda Yes, colored edges and colored vertices can be many-one reduced to standard GI. First you number the colors (edges and vertices can be numbered separately), then you replace them by simple "devices" which basically just encode the number. Miller's paper provides one typical construction, but it should be easy to come up with your own construction instead.
There is one crucial difference between physics and mathematics (including TCS), which is why I ping you here. Most questions in mathematics have clear and definitive answers, even if it may be difficult to find those answers. Mathematicians are always eager to help other people who search such clear answers, but they also prefer those question with clear answers. Your questions are often asked in a way to prevent such simple answers, hence quite a number of your questions are still unanswered.
« first day (1916 days earlier) ← previous day next day → last day (1713 days later) »
Transcript for
Sep26
Sep '1827
Sep28
theory salon
theoretical computer science. highlight reel vzn1.wordpress.co...