Questions tagged [gr.group-theory]
The gr.group-theory tag has no usage guidance.
73 questions
2
votes
0
answers
151
views
Determining diameters of NxNxN Rubik's cubes - is NP-hard problem?
For general finite groups computations of diameters is NP-hard:
"NP-hard even for elementary abelian 2-groups (Even, Goldreich 1981)"
(quote from page 4 of Ákos Seress slides).
Question: For ...
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 ...
- 38.5k
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 ...
- 38.5k
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-...
- 38.5k
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_(...
- 38.5k
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
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 ...
CommunityBot
- 1
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
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
2
votes
0
answers
123
views
Relation between automorphism group of a linear code and its dual code
Are there any strong connections between automorphism groups of codes that are dual codes of each other? I am looking for statements like one charcterizes other or one gives bounds on other etc.
In ...
- 387
0
votes
1
answer
82
views
Generating set of a group and relation to diameter?
Is there an efficient algorithm to test if a given subset of symmetric group generates the symmetric group?
Drawing the Cayley graph and testing for all pairs reachability is one way however that ...
- 193
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, ...
- 38.5k
2
votes
1
answer
155
views
Circuit complexity of group actions
Suppose that $G$ is a group with $|G|=n$. Suppose that $G$ is generated by elements $g_{1},\dots,g_{k}$. Let $\iota:G\rightarrow S_{2^{N}}$ be an injective group homomorphism such that $\iota(g_{i}):\{...
- 38.5k
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, ...
- 156
2
votes
0
answers
55
views
Is topological conventional computation possible?
A function $f:X^{2}\rightarrow X^{2}$ is said to satisfy the Yang-Baxter equation if
$$(f\times\mathrm{Id}_{X})\circ(\mathrm{Id}_{X}\times f)\circ(f\times \mathrm{Id}_{X})=(\mathrm{Id}_{X}\times f)\...
- 596
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
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
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
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
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{...
- 2,327
2
votes
0
answers
71
views
Can we compute encodings of binary strings under arbitrary permutation groups?
Given a permutation group $G \leq S_n$, can you construct non-uniformly a circuit computing a function $f : \{0, 1\}^n \rightarrow \{0, 1\}^{ceil(log|\{0, 1\}^n/G_n|)}$ with size $O_n(\frac{|\{0, 1\}^...
- 1,582
1
vote
1
answer
107
views
What is the relationship between this notion of symmetry compressibility and Kolmogorov complexity?
If we have some string $x$ and a permutation $g$ which preserves the bits of $x$, we can store the value of $x$ on each of its $g$-orbits as well as $g$ instead of storing $x$ and we can reconstruct $...
- 38.5k
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 ...
- 38.5k
1
vote
0
answers
96
views
Easy instances for coset intersection problem
Coset Intersection Problem
Given : $K,H \le S_n$, and $\sigma \in S_n$
Find : $K \cap H\sigma$
Known results are :
$n^{O(\sqrt n )}$ time algorithm by L.Babai.
$n^{O(1)} m^{O(\sqrt m )}$, where $...
- 358
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^{'}$ (...
- 38.5k
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 ...
- 51.2k
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 ...
CommunityBot
- 1
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$, ...
- 570
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 ...
- 38.5k
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 ...
- 6,985
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
2
votes
1
answer
207
views
Is there any efficient algorithm for computing all semigroups of order n? [closed]
Is there any efficient algorithm for computing all semigroups of order n?
I found the following paper which solves a bit different problem.
Veronique Froidure and Jean-Eric Pin, "Algorithms for ...
CommunityBot
- 1
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 ...
- 2,369
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 ...
- 4,765
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 ...
CommunityBot
- 1
1
vote
1
answer
102
views
How the hardness of hidden subgroup problem in $S_n$ changes as the order of the subgroup grows?
In Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In this paper it is showed that no hidden subgroup algorithm can distinguish the trivial ...
- 2,369
2
votes
0
answers
133
views
Why hidden subgroup problem is easy for very large subgroup?
I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE
NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et al. On page 2, it is said that solving the hidden subgroup problem becomes very easy when the ...
- 14.5k
0
votes
1
answer
123
views
Question about discarding the second register in the standard approach of hidden subgroup algorithm
My questions:
What does discarding the second register mean for the standard approach of hidden subgroup algorithm?
Why does discarding let the first register end up in a mixed state?
My ...
- 1,405
17
votes
2
answers
728
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 ...
CommunityBot
- 1
0
votes
2
answers
630
views
Complexity of simple undirected graph isomorphism problem
We define a simple undirected graph as a graph where no vertex has a loop and there is only zero or one undirected, unweighted edge between any pair of vertices.
My question:
What is the complexity ...
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 ...
- 2,806
-3
votes
1
answer
152
views
Dimension of the Fourier transform for $S_5$ [closed]
My question:
What is the dimension of the Fourier transform for $S_5$?
My effort:
The dimensions of the seven irreps of $S_5$ are $1,1,4,4,5,5,6$. According to the notes of Andrew Childs, the ...
- 25k
-2
votes
1
answer
442
views
Are Graph and Group Isomorphism problems random self-reducible?
Are Graph and Group Isomorphism problems known to be random self-reducible? If so is there a good proof?
Are there other non-trivial examples of random self-reducibility? Is there a good reference?
- 38.5k
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
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 ...
CommunityBot
- 1
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\...
- 38.5k
1
vote
0
answers
60
views
First register in the hidden subgroup representations of Simon's and graph isomorphism problems
The Simon's problem involves a function which takes binary strings as inputs. One seeks to find the period of the function which acts on those inputs. In the standard method, the first register has ...
- 661
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 ...
10
votes
2
answers
685
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 ...
- 2,592
1
vote
0
answers
38
views
Coset state of $3$-node graph isomorphism problem
The hidden subgroup representation of a $3$-node graph isomorphism problem is defined over the symmetric group, $G = S_6$. So, any hidden subgroup algorithm that wishes to solve the problem should ...
- 661