TC^0 circuits for algorithmic problems in nilpotent groups

DOI10.4230/LIPICS.MFCS.2017.23zbMath1441.68044arXiv1702.06616OpenAlexW2593181919MaRDI QIDQ5111237

Armin Weiß, Alexei G. Myasnikov

Publication date: 26 May 2020

Full work available at URL: https://arxiv.org/abs/1702.06616

zbMATH Keywords

abelian groupsword problemnilpotent groupsconjugacy problemgreatest common divisorssubgroup membership problem\(\mathsf{TC}^0\)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nilpotent groups (20F18) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (9)

Parallel complexity for nilpotent groups ⋮ The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ Evaluation of circuits over nilpotent and polycyclic groups ⋮ TC^0 circuits for algorithmic problems in nilpotent groups ⋮ Unnamed Item ⋮ The power word problem in graph products ⋮ Low-complexity computations for nilpotent subgroup problems ⋮ The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\) ⋮ Two general schemes of algebraic cryptography

Cites Work

• Non-commutative lattice problems
• The Post correspondence problem in groups.
• Random nilpotent groups, polycyclic presentations, and Diophantine problems
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
• Evaluating Matrix Circuits
• Word Problems Solvable in Logspace
• Symbolic Collection using Deep Thought
• On homomorphisms onto finite groups
• Logspace and compressed-word computations in nilpotent groups
• TC^0 circuits for algorithmic problems in nilpotent groups
• Conjugacy in Nilpotent Groups
• Computational algorithms for deciding some problems for nilpotent groups
• The word problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: TC^0 circuits for algorithmic problems in nilpotent groups