All Questions
Tagged with gr.group-theory circuit-complexity
3 questions
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}):\{...
- 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
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