Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 ...
Joshua Grochow's user avatar
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-...
Joshua Grochow's user avatar
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 ...
Izaak Meckler's user avatar
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 ...
Chris Aldrich's user avatar
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 ...
Joshua Grochow's user avatar
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....
Joshua Grochow's user avatar
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. ...
Chao Xu's user avatar
  • 4,479
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 ...
David Eppstein's user avatar
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.
Boson's user avatar
  • 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 ...
Joshua Grochow's user avatar
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)$, ...
Joshua Grochow's user avatar
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-...
mic's user avatar
  • 336
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] ...
Turbo's user avatar
  • 12.9k
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 ...
yyyyyyy's user avatar
  • 156
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 ...
Joshua Grochow's user avatar
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 ...
James Mitchell's user avatar
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 ...
Joshua Grochow's user avatar
2 votes

Generating set of a group and relation to diameter?

The answer to the first part of your question is yes. Given a permutation group $G = \langle S \rangle$, there is a polynomial time algorithm (clearly more efficient than the brute force approach ...
thibo's user avatar
  • 193
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\}$ ...
Joshua Grochow's user avatar
2 votes

What are interesting algorithmic questions for groups in table representation?

The following paper by Barrington-Kadau-McKenzie-Lange studies the Cayley Group Membership problem (CGM): given a group as a multiplication table, a subset of elements $X$ and an element $t$ determine ...
SamiD's user avatar
  • 2,309
1 vote
Accepted

Circuit complexity of group actions

The number of isomorphism classes of groups of order $\leq n$ is asymptotically $n^{\Theta(\log^2 n)}$, so to even specify all such groups requires strings of length $\Omega(\log^3 n)$, so this is ...
Joshua Grochow's user avatar
1 vote

What are interesting algorithmic questions for groups in table representation?

Cameron and Wu investigated several algorithmic problems for groups, The complexity of the weight problem for permutation and matrix groups. They proved NP-completeness for some of them.
Mohammad Al-Turkistany's user avatar
1 vote

Construction of a Global Isomorphism(permutation) for Graph Isomorphism using Local Isomorphism

The computational complexity of of finding $P$ is polynomial in $\beta$. We construct the generating set of automorphism group of $H$ using $\beta_k$, for all $k$. As we know, constructing ...
Michael's user avatar
  • 533
1 vote

Is there any hidden subgroup of a symmetric group which can be efficiently determined?

Exact classical bounds are known, https://oeis.org/A186202 , you only have to sample certain prime cycles as they form a min dominating set on $S_n$ under a detection relation. Smaller than $n!$ but ...
Chad Brewbaker's user avatar
1 vote

Determining what can be achieved by a permutation of elements of a noncommutative group

With my coauthor, we have just posted a preprint which studies this problem more generally for regular languages. In the case of finite groups, we claim that the problem is tractable (in NL) in the ...
a3nm's user avatar
  • 9,419

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