The tag has no wiki summary.

learn more… | top users | synonyms

6
votes
0answers
42 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 ...
4
votes
1answer
131 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 ...
7
votes
1answer
109 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 ...
11
votes
0answers
208 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 ...
3
votes
2answers
129 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 ...
-5
votes
1answer
179 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 ...
0
votes
1answer
190 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 ...
2
votes
0answers
112 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 ...
3
votes
3answers
119 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 ...
9
votes
1answer
78 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 ...
1
vote
0answers
60 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?
0
votes
1answer
95 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 ...
12
votes
0answers
215 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: ...
10
votes
2answers
246 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$. ...
8
votes
0answers
130 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
158 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
236 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
314 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 ...
31
votes
12answers
1k 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
549 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
105 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
214 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
462 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
143 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 ...