Skip to main content

Questions tagged [gr.group-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
Sasho Nikolov's user avatar
17 votes
2 answers
697 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 ...
maomao's user avatar
  • 1,345
16 votes
1 answer
828 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 ...
Jernej's user avatar
  • 651
15 votes
0 answers
399 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_(...
domotorp's user avatar
  • 14k
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 ...
ricardorr's user avatar
  • 561
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 ...
DurgaDatta's user avatar
  • 1,301
14 votes
2 answers
747 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 ...
Samuel Schlesinger's user avatar
14 votes
2 answers
372 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$. ...
user774025's user avatar
14 votes
1 answer
319 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 ...
Aubrey da Cunha's user avatar
13 votes
2 answers
907 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
182 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)$ ...
dtell's user avatar
  • 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, ...
adc's user avatar
  • 177
11 votes
2 answers
290 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 ...
a3nm's user avatar
  • 9,547
11 votes
1 answer
136 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 ...
Anthony Labarre's user avatar
11 votes
0 answers
307 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 ...
NisaiVloot's user avatar
  • 1,292
10 votes
2 answers
664 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 ...
Aryeh's user avatar
  • 10.6k
10 votes
1 answer
350 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 ...
Charles Mosley's user avatar
10 votes
1 answer
179 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))\...
Yuval Filmus's user avatar
  • 14.5k
10 votes
1 answer
257 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 \...
Andrew Morgan's user avatar
10 votes
1 answer
283 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, ...
user avatar
9 votes
2 answers
798 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 ...
Michael's user avatar
  • 553
9 votes
2 answers
178 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$, ...
Samuel Schlesinger's user avatar
9 votes
1 answer
205 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 ...
Samuel Schlesinger's user avatar
8 votes
1 answer
296 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, ...
HaskellElephant's user avatar
8 votes
1 answer
538 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 ...
Thomas Klimpel's user avatar
8 votes
0 answers
212 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 ...
Geoffrey Irving's user avatar
7 votes
2 answers
411 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 ...
vzn's user avatar
  • 11k
7 votes
1 answer
123 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 ...
Boson's user avatar
  • 560
7 votes
0 answers
170 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 ...
ricardorr's user avatar
  • 561
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 ...
W. J. Zeng's user avatar
6 votes
0 answers
122 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 ...
Steven Stadnicki's user avatar
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 ...
Michael's user avatar
  • 553
5 votes
3 answers
271 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{...
alha hu's user avatar
  • 151
5 votes
1 answer
122 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 ...
Joseph Van Name's user avatar
5 votes
0 answers
124 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 ...
Joseph Van Name's user avatar
4 votes
2 answers
374 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 ...
vzn's user avatar
  • 11k
4 votes
1 answer
209 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^{'}$ (...
adc's user avatar
  • 177
4 votes
1 answer
152 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\...
user avatar
4 votes
2 answers
222 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 ...
Omar Shehab's user avatar
4 votes
1 answer
357 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 ...
Dean's user avatar
  • 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). ...
Michael's user avatar
  • 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 ...
aelguindy's user avatar
  • 951
3 votes
1 answer
182 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-...
draks ...'s user avatar
  • 155
3 votes
3 answers
171 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 ...
Subhayan's user avatar
  • 831
3 votes
1 answer
187 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 ...
user avatar
3 votes
0 answers
90 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)\...
Joseph Van Name's user avatar
3 votes
0 answers
107 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 ...
Lior Eldar's user avatar
  • 1,224
2 votes
1 answer
204 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 ...
David  Tsaturyan's user avatar
2 votes
1 answer
145 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}):\{...
Joseph Van Name's user avatar
2 votes
0 answers
113 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 ...
Root's user avatar
  • 387