# Tagged Questions

The tag has no usage guidance.

164 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 ...
109 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 ...
428 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). ...
47 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 ...
40 views

### Measurements in non-Abelian hidden subgroup algorithms

More than one measurement take place in a non-Abelian hidden subgroup algorithm. In this question, I would like to verify whether my understandings about them are right. I am using Andrew Childs' ...
18 views

### Choice of basis for non-Abelian hidden subgroup problems

I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et al. In section 1.1 it is said that, It is still possible that a clever choice of basis ...
99 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 ...
72 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 ...
52 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 ...
2k 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 ...
125 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 ...
160 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?
74 views

### Fourier transformation of the automorphism group of a graph

Following is an example of permutation cycle graph $\Gamma$ for a given permutation $\pi = \left(1\text{ } 2\right) \left(3\text{ } 4\text{ } 5\text{ } 6\right)$. The adjacency matrix $A$ is given ...
78 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 ...
106 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 ...
92 views

440 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 ...
53 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 ...
159 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 ...
203 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 ...
237 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 ...
323 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 ...
206 views

### Some questions (still) unresolved about braids?

I was looking for interesting questions pertaining to braid theory. I don't know if the following are considered important, but I'd like to ask: (1) in relation with the following link, is it true ...
194 views

### Classifying noetherian simple groups by order type?

A (possibly infinite) group $G$ is noetherian if it satisfies the following equivalent conditions: (1) every subgroup of $G$ is finitely generated, (2) there is no infinite strict ascending chain of ...
120 views

### Extending the notion of independence

Background I was looking for a formulation of 'free sets' and 'independent sets' from linear algebra that would extend to groups. This question was considered here but I couldn't find a satisfactory ...
126 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 ...
96 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 ...
74 views

### Upper bound on the number of vertex-transitive graphs

Is there a known upper bound on the number of vertex transitive graphs on $n$ vertices?
110 views

### How to go about finding the most “complex” function?

Intro Hi, I'm a hobbyist, with no formal education, tinkering with SAT solving and boolean algebra minimization. So expect bad terminology. I hope you will forgive me I'm asking a wrong question in a ...
249 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_(...
267 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$. ...
135 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 ...
166 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, ...
329 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 ...
464 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 ...
2k 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 ...
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 ...