16
votes
Book for self study of algorithms in group theory
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,...
- 50.9k
15
votes
Accepted
What is the hardest instance for the group isomorphism problem?
$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 ...
- 36.9k
12
votes
Accepted
Are There Highly Symmetric NP- or P-complete Languages?
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-...
- 36.9k
8
votes
possible bridge between group growth theory and complexity theory?
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 ...
- 431
7
votes
Accepted
Relation between group theory and information theory
Sadly, group structure is nearly so limited that there isn't much one can do with it to be of use in information theory, thus the literature is prone to be fairly sparse. Even Abelian groups aren't ...
- 186
6
votes
Accepted
Some nuances on Group and Subgroup Isomorphism?
(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 ...
- 36.9k
6
votes
Accepted
Book for self study of algorithms in group theory
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 ...
- 36.9k
6
votes
Book for self study of algorithms in group theory
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 ...
- 773
6
votes
Do there exist groups with word problems in arbitrary P-degrees?
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 ...
- 36.9k
6
votes
Accepted
How to find largest supergroup in polynomial time?
Yes, this can be solved in polynomial time (and, I think, even in $\mathsf{NC}$).
First, it's easy to reduce to the case of transitive $G$.
Next, find the minimal blocks of $G$. (See e.g. Section 3....
- 36.9k
5
votes
Accepted
Is this "subgroup packing" polytope integral?
Andrew(the asker) and I had discussed this over email, and we have shown the conjecture is false. The polytope is not integral for Abelian groups, not even for cyclic groups.
On the positive side.
...
- 4,367
5
votes
Are There Highly Symmetric NP- or P-complete Languages?
My intuition is that an NP-complete language of this type would cause a collapse of the polynomial hierarchy much like the one in the Karp–Lipton theorem.
More specifically, if you go up to the ...
- 50.9k
5
votes
Accepted
Complexity of Computing Lexicographically Minimal Element of Orbit
This problem is $FP^{NP}$-complete, as shown here.
It means that the lexicographical leader of the orbit is built in deterministic polynomial time with access to a $NP$-oracle.
- 560
5
votes
Complexity of Computing Lexicographically Minimal Element of Orbit
This problem is NP-hard.
Although it may be possible to find some canonical form for string isomorphism, say, in quasi-poly time, without upsetting our current guesses as to how the complexity world ...
- 36.9k
5
votes
Accepted
Dimension of the Fourier transform for $S_5$
A quantum Fourier transform is a unitary operation, so the number of basis states of the input and output must be the same.
The number of basis states before the Fourier transform is 120, the number ...
- 24.3k
4
votes
Is there a candidate for a post-quantum one-way group action?
Yes, there is an old proposal for this due to Couveignes, which was independently rediscovered by Rostovtsev and Stolbunov.
In both cases, the set of elliptic curves with some common endomorphism ...
- 156
4
votes
Accepted
Question about discarding the second register in the standard approach of hidden subgroup algorithm
Discarding in this context can be carried out by performing a Partial Trace. The system you're interested in is that of the first register. If you want to know only its state, as opposed to the ...
- 977
4
votes
Accepted
What is the probability that a random Boolean function has a trivial automorphism group?
Yes. To your first question, the probability goes to zero double-exponentially fast. This can be calculated as follows. For each permutation $\pi$, we can bound the probability that $\pi \in Aut(f)$, ...
- 36.9k
4
votes
Relation between group theory and information theory
Reference Goppa's information theory work.
http://iopscience.iop.org/article/10.1070/RM1984v039n01ABEH003062/meta;jsessionid=2978C0F66C0E4C77833FEDFE7B511F98.c1.iopscience.cld.iop.org
[CITATION] ...
- 12.8k
4
votes
What are interesting algorithmic questions for groups in table representation?
First, is it a group at all? A fundamental problem is checking whether a given operation (in table form) is associative. The obvious approach is cubic time, Rajagopalan and Schulman do it in near-...
- 336
3
votes
Is there any efficient algorithm for computing all semigroups of order n?
You asked the same question here
and I answered it. Jean-Eric's algorithm is for computing the elements (among other things) of a semigroup defined by a generating set, and is not related to your ...
- 131
3
votes
Book for self study of algorithms in group theory
Not a book but maybe A. Hulpke's Notes on Computational Group Theory are of interest?
- 11.4k
3
votes
Accepted
Is there any hidden subgroup of a symmetric group which can be efficiently determined?
From what I understand, it is partially because we don't have any techniques currently that take advantage of structure of the hidden subgroup itself. Weak Fourier sampling solves the problem whenever ...
- 36.9k
3
votes
Do there exists reversible gate sets of intermediate growth?
If you allow ancilla bits (which is more natural from the computational perspective, see, e.g. the third paragraph of Section 1.2 of Aaronson-Grier-Schaeffer), then the answer is no. In fact, I ...
- 36.9k
2
votes
Accepted
Complexity of simple undirected graph isomorphism problem
László Babai. Graph Isomorphism in Quasipolynomial Time, 84 pages. [Version 1. Fri, 11 Dec 2015]
From Abstract :
We show that the Graph Isomorphism (GI) problem and the related problems of String ...
2
votes
Accepted
Are Graph and Group Isomorphism problems random self-reducible?
If Graph Isomorphism is randomly self-reducible in the sense of the question (clarified in the comments), then it could be solved in poly time. The reason is that there is in fact an average-case ...
- 36.9k
2
votes
Book for self study of algorithms in group theory
If you're only concerned about finite permutation groups, I found the book "Fundamental Algorithms for Permutation Groups" by Gregory Butler very readable. It's only for finite permutation groups but ...
- 2,786
2
votes
Book for self study of algorithms in group theory
I cut my teeth on Combinatorial Algorithms Generation Enumeration Search, http://www.math.mtu.edu/~kreher/cages.html.
I would highly recommend it. You learn much faster coding group algorithms as by ...
- 2,359
2
votes
Accepted
Quasi-polynomial time algorithm for permutation group isomorphism
The answer is basically yes, if we take into account the hidden assumption that the degree of the group is at most $n$. More precisely, let $G_1, G_2$ with $|G_1|=| G_2|=n$ be finite permutation ...
- 3,033
2
votes
Accepted
What is the relationship between this notion of symmetry compressibility and Kolmogorov complexity?
They are equivalent. For any $x$, let $g_x$ be a permutation with just two cycles: one consisting of $\{i \in [n] : x_i = 0\}$ (say, in ascending order) and one consisting of $\{i \in [n] : x_i = 1\}$ ...
- 36.9k
Only top scored, non community-wiki answers of a minimum length are eligible