Questions tagged [gr.group-theory]
The gr.group-theory tag has no usage guidance.
73 questions
46
votes
12
answers
5k
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 in ...
- 18.3k
19
votes
1
answer
524
views
Are there other proofs for Barrington's theorem?
I know that you can use other non-solvable groups, but is there a proof that uses a completely different approach?
In case someone would not know the theorem:
http://en.wikipedia.org/wiki/NC_(...
- 14.2k
17
votes
2
answers
727
views
Complexity of the coset intersection problem
Given the symmetry group $S_n$ and two subgroups $G, H\leq S_n$, and $\pi\in S_n$, does $G\pi\cap H=\emptyset$ hold?
As far as I know, the problem is known as the coset intersection problem. I am ...
- 1,365
16
votes
1
answer
863
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
...
- 651
14
votes
6
answers
3k
views
Book for self study of algorithms in group theory
I am a math major interested on TCS.
I want to self-study the algorithms, and complexity of them for solving the group theoretical problems like find order of elements, coset enumeration, find ...
- 560
14
votes
2
answers
1k
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 ...
- 1,311
14
votes
2
answers
751
views
Are There Highly Symmetric NP- or P-complete Languages?
Does there exist $L$, an NP- or P-complete language which has some family of symmetry groups $G_n$ (or groupoid, but then the algorithmic questions become more open) acting (in polynomial time) on ...
- 1,582
14
votes
2
answers
393
views
Difficulty in understanding the quantum algorithm for the abelian hidden subgroup problem
I've difficulty in understanding the last steps of the AHSP algorithm. Let $G$ be an abelian group and $f$ be the function which hides the subgroup $H$. Let $G^*$ represent the dual group of $G$.
...
- 291
14
votes
1
answer
324
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 ...
- 346
13
votes
2
answers
927
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 arbitrary-...
13
votes
0
answers
186
views
Deterministic context-free languages that can be represented as the word problem of a group
Consider a group $G$. We call $G$ virtually free is it contains a free subgroup of finite index.
If $G$ is finitely generated by some set $X \subseteq G$ one can consider the word problem $W\!P(G)$ ...
- 231
12
votes
1
answer
1k
views
What is the hardest instance for the group isomorphism problem?
Two groups $(G,\cdot)$ and $(H, \times)$ are said to be isomorphic iff there exists a homomorphism from $G$ to $H$ which is bijective. The group isomorphism problem is as follows: given two groups, ...
- 177
11
votes
2
answers
298
views
Determining what can be achieved by a permutation of elements of a noncommutative group
Fix a finite group $G$. I am interested in the following decision problem: the input is some elements of $G$ with a partial order on them, and the question is whether there is a permutation of the ...
- 9,838
11
votes
1
answer
141
views
Encoding sets of permutations with a generating set and a set of excluded elements
Polynomial-time algorithms are known for finding generating sets of permutation groups, which is interesting since we can then represent those groups succinctly without giving up on polynomial-time ...
- 3,264
11
votes
0
answers
312
views
Generalizations of the determinant/permanent problem?
A tantalizing open question in computational complexity is to understand the 'behavioral differences' between the determinant and the permanent. While the former is computable in polynomial time with ...
- 1,312
10
votes
2
answers
684
views
Complexity of computing the order of a permutation group
Given two permutations $g$ and $h$ over $n$ elements (i.e., members of $S_n$), what is the complexity of computing the order of the subgroup generated by $g,h$? Or just of deciding whether the ...
- 10.6k
10
votes
1
answer
354
views
Recent progress in permutation groups algorithms?
I am interested in algorithms for finite groups as implemented in the GAP package. It seems that all known algorithms in this field deal with permutation groups/matrix groups; two fundamental ones are ...
- 101
10
votes
1
answer
186
views
Diameter of Cayley graphs of subgroups of $S_n$ without inverses
Babai and Seress proved that given a subgroup $G \leq S_n$ and a generating set $S$ of $G$, any permutation in $G$ can be written as a product of generators and their inverses of length $e^{(1+o(1))\...
- 14.5k
10
votes
1
answer
258
views
Is this "subgroup packing" polytope integral?
Let $\Gamma$ be a finite abelian group, and let $P$ be the polytope in $\mathbb{R}^\Gamma$ defined to be the points $x$ satisfying the following inequalities:
$$\begin{array}{cl}
\sum_{g\in G} x_g \...
- 1,439
10
votes
1
answer
291
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, ...
user6973
9
votes
2
answers
879
views
Number of Automorphisms of a graph for graph isomorphism
Let $G$ and $H$ be two $r$-regular connected graphs of size $n$.
Let $A$ be the set of permutations $P$ such that $PGP^{-1}=H$.
If $G=H$ then $A$ is the set of automorphisms of $G$.
What is the ...
- 553
9
votes
2
answers
183
views
Complexity of Computing Lexicographically Minimal Element of Orbit
Given strong generators for a group $(G \leq S_n, *)$ acting on bitstrings of length $n$ and an element $s \in \{0, 1\}^n$, how hard is it to compute the lexicographically minimal element of $G.s$, ...
- 1,582
9
votes
1
answer
210
views
What is the probability that a random Boolean function has a trivial automorphism group?
Given a Boolean function $f$, we have the automorphism group $Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \}$.
Are there any known bounds on $Pr_f(Aut(f) \neq 1)$? Is there ...
- 1,582
8
votes
1
answer
312
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, ...
- 183
8
votes
1
answer
552
views
Quasi-polynomial time algorithm for permutation group isomorphism
Is there a known $n^{\alpha \log n+O(1)}$ algorithm for permutation group isomorphism? Here $n$ is the size of the group, and the isomorphism must be a permutational isomorphism.
My hope for such an ...
- 3,103
8
votes
0
answers
219
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 ...
- 3,313
7
votes
2
answers
422
views
possible bridge between group growth theory and complexity theory?
RJ Lipton conjectures a link between group growth theory and complexity theory. Group growth theory has undergone rapid advance in the last decade and has many surface similarities/ parallels with ...
- 11.1k
7
votes
1
answer
127
views
Problem with a group as complexity parameter?
I am currently studying a complexity problem related to symmetries, and am considering a study of the parameterized complexity of the problem.
In theory, any part of the input can be fixed as a ...
- 570
7
votes
0
answers
176
views
Recognition of a primitive root
Adleman and McCurley published a paper in 1994 called "Open problems in number theoretic complexity, II" (http://ww.cstheory.com/papers/open.ps.gz)
Problem 18 of this list of open problems is about ...
- 560
7
votes
0
answers
70
views
Explicit error bounds on the abelian hidden subgroup problem
What are some explicit forms for the error probability in the typical quantum abelian hidden subgroup algorithm as a function of oracles queries?
Ettinger, Hoyer, and Knill give a result that the ...
- 91
6
votes
0
answers
123
views
Computational complexity of finding paths with specified product in a (group-labeled) directed graph
This question came up in the analysis of the puzzle game Swish. One way of representing the solvability problem is this: given a directed graph $G$ where each edge of the graph is labeled with an ...
- 1,396
5
votes
2
answers
1k
views
Relation between group theory and information theory
Motivation: I am interested about the application of group theory to information theory. To be precise, I am interested in data compression (source coding theory).
Question:
Is there any paper/survey ...
- 553
5
votes
3
answers
272
views
What are interesting algorithmic questions for groups in table representation?
I am currently reading about research problems in nilpotent groups ( assume table representation ). As we know that solvable group isomorphism is known to be in the (almost ) intersection of $\mathcal{...
- 151
5
votes
1
answer
291
views
Complexity of finding graph automorphism group vs. canonization
Given a generating set for the automorphism group of a graph, can we efficiently find a canonical labeling? What about the other way around?
Both problems of finding a graph automorphism group and ...
- 329
5
votes
1
answer
155
views
Do there exists reversible gate sets of intermediate growth?
Suppose that $f_{1},...,f_{k}:\{0,1\}^{r}\rightarrow\{0,1\}^{r}$ are bijective functions.
For all $n\geq r$, let $G_{f_{1},...,f_{k};r}=\subseteq S(\{0,1\}^{n})$ be the subgroup generated by
i. the ...
- 596
5
votes
0
answers
126
views
When do cellular automata on non-abelian groups not offer a computational speed up?
Suppose that $G$ is a finitely generated group and $A$ is a finite set. Then we shall give $A$ the discrete topology and $A^{G}$ the product topology; in particular $A^{G}$ is compact and totally ...
- 596
4
votes
2
answers
381
views
TCS oriented refs/survey on group theoretic word problem
The word problem for groups was shown to be Turing-complete in 1955 but has many decidable subcases. This problem arose more in mathematical group theory than in theoretical computer science, but now ...
- 11.1k
4
votes
1
answer
210
views
How to find largest supergroup in polynomial time?
Let $G \le S_n$, and G acts on set $[n]$ via a map $\pi$:
$$\pi : G \times [n]\mapsto [n] $$
In Input generating set of $G$ is given.
Question : I need to find the largest supergroup $G^{'}$ (...
- 177
4
votes
1
answer
159
views
Some nuances on Group and Subgroup Isomorphism?
(1) Is it known Group Isomorphism is in $\mathsf{coNP}$ and is the conjecture so? Is there a good reference for $\mathsf{coNP}$-ness in similar situations?
(2) Is subgroup isomorphism $\mathsf{NP\...
user34945
4
votes
1
answer
247
views
Complexity of permutation group intersection
Given generating sets for two subgroups of some finite symmetric group $S_n$, what is known about the complexity of computing a generating set of their group intersection?
Of course, we can brute-...
- 329
4
votes
2
answers
231
views
Is there any hidden subgroup of a symmetric group which can be efficiently determined?
There have been a number of cases where efficient hidden subgroup algorithms have been found for specific non-Abelian groups with very specific structures. Why haven't we found any efficient quantum ...
- 661
4
votes
1
answer
367
views
$\ell_1$ norm of Fourier coefficients vector for the hypercube
Let $G$ be the normzlied hypercube graph on $2^d$. It is a Cayley graph and it is well known that its eigenvalues are given by $\lambda_r = 1-2\frac{|r|}{d}$ for every $r \in \{0,1\}^d$.
Given a ...
- 225
4
votes
1
answer
507
views
Construction of a Global Isomorphism(permutation) for Graph Isomorphism using Local Isomorphism
Given two graphs $G, H$ (each has $n$ vertices). We, split $G$ into subgraphs $G_1, G_2... G_x$ (total $x$ vertex set). Similarly,assume $H$ has subgraphs $H_1, H_2... H_x$ (total $x$ vertex set).
...
- 553
3
votes
1
answer
131
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 ...
- 951
3
votes
1
answer
183
views
Efficient generation of permutational invariant quantum states
Starting from $|00\cdots 0\rangle$, can permutational invariant quantum states, i.e. the following one:
$$
|\psi_n\rangle = \frac1{n!} \sum \prod_{\pi\in S_n} |\pi(0)\rangle|\pi(1)\rangle\cdots|\pi(n-...
- 155
3
votes
3
answers
173
views
On proving it is hard to compute $g^{rb}$ with knowledge of $r$, given $g, g^a, g^{ab}$
I am trying to prove the following
Given $g, g^a, g^{ab}$ it is hard to compute $r, g^r, g^{rb}$, for some arbitrarily chosen value of $r$
where $g ∈ \mathbb{G}, \mathbb{G}$ is a cyclic group of ...
- 841
3
votes
1
answer
192
views
Complexity class for some group and graph homomorphism problems
Given two groups $G_1$ and $G_2$ what is the complexity class in which the following problem belongs?
$$\mathsf{Is }|Hom(G_1,G_2)|>0$$
Given two graphs $H_1$ and $H_2$ what is the complexity ...
user34945
3
votes
0
answers
57
views
Complexity of minimizing the index of a subgroup of the free group
Let $\Sigma$ be a finite alphabet and $G$ the free group generated by $\Sigma$. Let $W$ be a finite subset of $G$. (Represented as a list of formal expressions of the form $a_1^{\pm 1}\ldots a_n^{\pm ...
- 2,181
3
votes
0
answers
91
views
How many arithmetic and max operations does it take to compute Dynnikov's action of the braid groups on $\mathbb{Z}^{2n}$?
A function $f:X^{2}\rightarrow X^{2}$ is said to satisfy the Yang-Baxter equation if
$$(f\times\textrm{Id}_{X})\circ(\textrm{Id}_{X}\times f)\circ(f\times\textrm{Id}_{X})=(\textrm{Id}_{X}\times f)\...
- 596
3
votes
0
answers
110
views
Embedding distortion under group quotient
The high level question is as follows: Suppose some group (here assumed to be a vector space of $\mathbf{F}_2^n$) has a low-distortion embedding into $l_1$. Under what condition does the quotient of ...
- 1,224