27

Here are a few other examples. Diaconis and Shahshahani (1981) studied how many random transpositions are required in order to generate a near uniform permutation. They proved a sharp threshold of 1/2 n log(n) +/- O(n). Generating a Random Permutation with Random Transpositions. Kassabov (2005) proved that one can build a bounded degree expander on the ...


16

It really makes a difference what the input to the algorithm is: how do you specify a group? If you want groups given by generators and relators, I would suggest Combinatorial Group Theory, by Magnus, Karrass, and Solitar (but algorithms there are sparse because too many of the important problems are undecidable). If you want automatic groups (groups whose ...


15

$p$-groups of class 2 and exponent $p$ are widely believed to be the hardest case of Group Isomorphism ($p > 2$). (For $p=2$, we need to consider exponent 4, since all groups of exponent 2 are abelian - easy exercise for the reader.) Although there is as yet no reduction from general GpIso to this class of groups (though see point 0.5 below), there are ...


14

I don't have a complete answer, but I think both problems are open. The paper by Jajcay, Malnič, Marušič [3] is related to your first question. They provide some tools to test vertex-transitivity. They say in the introduction that: For a given finite graph $\Gamma$, it is decidedly hard to determine whether $\Gamma$ is vertex-...


14

Here is one example that I know: ``On the 'Log-Rank' Conjecture in Communication Complexity'', R.Raz, B.Spieker, Proceeding of the 34th FOCS, 1993, pp. 168-177 Combinatorica 15(4) (1995) pp. 567-588 I believe that there much more.


14

A very good question. I don't know the full answer and would like to know it myself. However, you may find the following interesting. If, instead of the group $S_n$, we consider its 0-Hecke monoid $H_0(S_n)$, it has a representation on a certain class of integer matrices which acts by tropical $(\min,+)$-multiplication. This has a lot of interesting ...


12

In the case of determinant, Gaussian elimination can indeed be seen as equivalent to the idea that the determinant has a large symmetry group (of a particular form) and is characterized by that symmetry group (meaning any other homogeneous degree $n$ polynomial in $n^2$ variables with those symmetries must be a scalar multiple of the determinant). (And, as ...


12

The order of permutation groups can be computed in polynomial-time. In fact, I believe even in $\mathsf{NC}$ and also nearly linear Las Vegas time. See, e.g., the book by Seress. For reference, subgroups of $S_n$ (and algorithms related thereto) are typically called "permutation groups" rather than merely "subgroups (of $S_n$)". So you can google "...


12

For NP, this seems hard to construct. In particular, if you can also sample (nearly) uniform elements from your group - which is true for many natural ways of constructing groups - then if an NP-complete language has a poly-time group action with few orbits, PH collapses. For, with this additional assumption about sampleability, the standard $\mathsf{coAM}$ ...


11

Moderately exponential time and $\mathsf{coAM}$ (for the opposite of the problem as stated: Coset Intersection is typically considered to have a "yes" answer if the cosets intersect, opposite of how it's stated in the OQ.) Luks 1999 (free author's copy) gave a $2^{O(n)}$-time algorithm, while Babai (see his 1983 Ph.D. thesis, also Babai-Kantor-Luks FOCS ...


11

Here's an example from quantum computing: Roland, Jeremie; Roetteler, Martin; Magnin, Loïck; Ambainis, Andris (2011), "Symmetry-Assisted Adversaries for Quantum State Generation", Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity, CCC '11, IEEE Computer Society, pp. 167–177, doi:10.1109/CCC.2011.24 They show that the quantum ...


10

Knuth 3rd volume of The Art of Computer Programming is devoted to searching and sorting and devote much to combinatorics and permutations and to the Robinson-Schensted-Knuth correspondence, which is central in representation theory of the symmetric group. There are several papers by Ellis-Friedgut-Pilpel, and Ellis-Friedgut-Filmus which solve extremal ...


9

Consider the complement, i.e. where you are asked to test whether $G \pi \cap H \not= \emptyset$. As I pointed out in this answer, testing whether $g \in \langle g_1, \ldots, g_k\rangle$ is in $\text{NC} \subseteq \text{P}$ [1]. So you can guess $g, h \in S_n$ and test in polynomial time whether $g \in G$, $h \in H$ and $g \pi = h$. This yields an $\text{NP}$...


9

As a complement to Joshua Grochow's answer: Computing the order of a permutation group given generators is in P by Schreier–Sims algorithm, see also p. 8-9 of these lectures notes by Luks. Just as membership in permutation groups, the problem was believed to be P-complete by many researchers, but it was finally shown to be in NC by Babai, Luks & Seress. ...


9

Wormald has shown that if $G$ is a connected $3$-regular graph with 2n vertices then the number of automorphisms of $G$ divides $3n\cdot 2^n$. In particular this gives a non-trivial exponential upper-bound for the $3$-regular case. Maybe there are results in this line for general $k$-regular graphs. For a lower bound, consider formula $F$ with $n$ inputs ...


8

Dan Boneh's survey article on the decisional Diffie Hellman problem lists several candidate groups for which the DDH problem is hard, reproduced here: Let $p=2p_1 + 1$ where both $p$ and $p_1$ are prime. Let $Q_p$ be the subgroup of quadratic residues in $\mathbb{Z}^*_p$. It is a cyclic group of prime order. This family of groups is parameterized by $p$...


8

Certainly there has been tons of progress! (And if you really meant to ask about the last 50 years, then that includes the algorithms of Schreier-Sims and Butler that you already mentioned...) For example, see Seress's book [1], which includes many algorithms that upgrade standard tasks into $\mathsf{NC}$ and/or quasi-linear (sometimes Las Vegas) time, such ...


8

One family of results not mentioned in the excellent references of @Marzio's answer is relations between the isoperimetric (Dehn) function of a group $G$ and the nondeterministic time complexity of the word problem in $G$. For example: For finitely generated groups $G$, $WP(G) \in \mathsf{NP}$ if and only if $G$ can be embedded in a finitely presented group ...


8

Maybe this is along the lines you are looking for: I wrote a blog post here explaining how you can use Gromov's theorem on groups of polynomial growth to show that non-uniform read once automata are no more powerful than linear time Turing machines for deciding word problems of groups. The basic idea is that groups with non-uniform read once automata ...


7

I think that you can start (and probably end, because it's a huge list :-) with the references in the recent Charles F. Miller's paper: "Turing machines to word problems" (2013). And another recent paper that surveys the connections between group theory and theory of automata and formal languages and hase a huge (>100 entries) reference section is: Tullio ...


7

There are cases where the symmetries of a problem ( seem to ) characterize its complexity. One very interesting example is constraint satisfaction problems (CSPs). Definition of CSP A CSP is given by a domain $U$, and a constraint language $\Gamma$ ($k$-ary functions from $U^k$ to $\{0, 1\}$). A constraint satisfaction instance is given by a set of ...


7

The answer is yes, we can improve the upper bound to $\mathrm{e}^{(1 + o(1))\sqrt{n\ln n}}$. It was proved in a more recent paper of Babai (Corollary 2.9).


7

Yes, they can. Recall that any reversible classical function can be computed in superposition. Now, generate the state $$ \frac{1}{\sqrt{n!}}\left(\sum_{i=1}^n |i \rangle \right) \left( \sum_{i=1}^{n-1} |i \rangle \right)\left(\sum_{i=1}^{n-2} |i\rangle \right) \ldots \left(\sum_{i=1}^2 |i\rangle \right) \bigg(| 1\rangle \bigg) . $$ This is the ...


7

There has been some recent work in terms of characterizing automorphism groups of strongly regular graphs using asymptotic group theory (e.g. this paper), which (for many reasons) is likely very closely related to the complexity of algorithms on strongly regular graphs that use group-theoretic methods, although exploiting such properties algorithmically is ...


6

I think this is not known. (I apologize - I think I was also one of the people that said I had remembered reading this somewhere.) For example, I believe that Sapir-Birget-Rips, Annals of Math 2002 were the first to show the existence of a group with $\mathsf{NP}$-complete word problem (which would be a trivial consequence of the result asked for in this ...


6

The Symmetric Group Defies Strong Fourier Sampling by Moore, Russell, Schulman "we show that the hidden subgroup problem over the symmetric group cannot be efficiently solved by strong Fourier sampling... These results apply to the special case relevant to the Graph Isomorphism problem." with a connection to solving the Graph Isomorphism problem via QM ...


6

Yes, the best known algorithm is still the algorithm from Babai and Luks, with runtime $\exp(O(\sqrt{n \log n}))$, where $n$ is the number of vertices in the graphs. Unless I'm mistaken, even the best known conondeterministic algorithm for graph isomorphism has exponential runtime. Babai and Luks' algorithm is plausibly near-optimal for deterministic ...


6

(1) In terms of structural complexity classes (as opposed to just upper bounds on deterministic time), for general Group Isomorphism, the known upper bounds are essentially the same as for Graph Isomorphism, namely $\mathsf{coAM} \cap \mathsf{SZK}$. However, Arvind and Toran showed that Solvable Group Isomorphism is in $\mathsf{NP} \cap \mathsf{coNP}$ under ...


6

The most modern and comprehensive reference is probably "Handbook of Computational Group Theory" by Holt, Eick and O'Brien (link) A classic reference is "Computation in Finitely Presented Groups" by Charles Simms.


6

If you're interested in the group theory that's relevant for Graph Isomorphism, then in addition to Seress's book that David Eppstein mentioned, I would highly recommend Dixon and Mortimer's Permutation Groups The above is a book on "just" group theory, but of the books on pure group theory, it is probably the most relevant to Graph Isomorphism. A book ...


Only top voted, non community-wiki answers of a minimum length are eligible