The gr.group-theory tag has no wiki summary.
8
votes
0answers
115 views
Complexity of checking if AB intersects C
Let $A,B,C$ be subsets of a nonabelian group $G$,
and assume we know the structure of $G$ "fairly well"
(e.g., $G = S_n$ or $A_n$).
Assume that group operations take $O(1)$ time.
Is it ...
7
votes
0answers
138 views
Is there a candidate for a post-quantum one-way group action?
Is there a known family of group actions with a designated element
in the set that is being acted on, where it is known how to efficiently
$\:$ sample (essentially uniformly) from the groups, ...
1
vote
2answers
185 views
Primitive Recursive Isomorphisms
What is the relationship between invertible primitive recursive functions (that is, a primitive recursive function that is an isomorphism) and all primitive recursive functions? Can every primitive ...
14
votes
1answer
197 views
Complexity of recognizing vertex-transitive graphs
I am not knowledgeable in the area of complexity theory involving groups so I apologize if this is a well known result.
Question 1. Let $G$ be a simple undirected graph of order $n$. What is the
...
29
votes
11answers
734 views
Applications of representation theory of the symmetric group
Inspired by this question and in particular the final paragraph of Or's answer, I have the following question:
Do you know of any applications of the representation theory of the symmetric group ...
12
votes
2answers
488 views
Gaussian Elimination in terms of Group Action
Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to ...
3
votes
1answer
96 views
Choices for the group in Public Key Cryptography
I am only aware of two alternatives for the group used in Diffie-Hellman scheme (and similar ones) where logarithms are conjectured to be hard. Those are $\mathbb{F}_p$ and Elliptic Curves. Are there ...
6
votes
1answer
208 views
What is the most efficient algorithm for deciding if an element is the least in its orbit?
Given a group $G$ acting on a set $X$ with a total order $\leq$ and an $x\in X$, what is the most efficient algorithm for deciding whether or not x is the least element in its orbit, in other words, ...
12
votes
2answers
389 views
Complexity of Membership-Testing for finite abelian groups
Consider the following abelian-subgroup membership-testing problem.
Inputs:
A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with ...
11
votes
0answers
134 views
Do there exist groups with word problems in arbitrary P-degrees?
It has been known for a long time that, given any r.e. Turing degree, there is a finitely presented group whose word problem is in that degree. My question is whether the same thing is true for ...
