Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

There has been some efforts to attack graph isomorphism problem using quantum random walk of hard-core bosons (symmetric but no double occupancy). Symmetric power of adjacency matrix, which seemed promising, was proved to be incomplete for general graphs in this paper by Amir Rahnamai Barghi and Ilya Ponomarenko. Other similar approach was also refuted in this paper by Jamie Smith. In both of these papers, they use the idea of coherent configuration (schemes) and alternative but equivalent formulation of cellular algebra (matrix subalgebra indexed by a finite set -here vertex set- closed under point-wise multiplication, complex conjugate transpose, and containing Identity matrix I and all-one matrix J) respectively to provide necessary counter arguments.

I find it very difficult to follow those arguments and even if I follow individual arguments vaguely I do not understand the core idea. I would like to know if the essence of the arguments can be explained in generic terms -may be at the cost of slight rigour- without using the language of scheme theory or cellular algebra.

share|cite|improve this question
up vote 4 down vote accepted

You can do much better than checking all n! permutations when brute forcing a solution, The grail is showing that you can't do much better than that, or exploiting the fact that most graphs have no symmetry in them and using this to speed calculation.

share|cite|improve this answer
The paper of yours referenced from OEIS shows a bound on the size of a set $S \subseteq S_n$ such that $S$ intersects every nontrivial subgroup of $S_n$. I'm probably just being slow here, but how does having such a set help you solve either a) the hidden subgroup problem for $S_n$ or b) graph isomorphism (a special case of (a))? – Joshua Grochow Nov 29 '12 at 23:46
If you test one nontrivial permutation from each prime cycle you have checked every possible subgroup of Sn. It is still huge. Also, it is for checking graph automorphism which is "easier" than isomorphism. – Chad Brewbaker Nov 30 '12 at 20:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.