Evaluation of circuits over nilpotent and polycyclic groups

DOI10.1007/s00453-017-0343-zzbMath1390.68311OpenAlexW2725306094MaRDI QIDQ1750355

Daniel König, Markus Lohrey

Publication date: 18 May 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-017-0343-z

Mathematics Subject Classification ID

Related Items (12)

Parallel algorithms for power circuits and the word problem of the Baumslag group ⋮ Knapsack and the power word problem in solvable Baumslag–Solitar groups ⋮ Improved parallel algorithms for generalized Baumslag groups ⋮ Post's correspondence problem: from computer science to algebra ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parallel identity testing for skew circuits with big powers and applications ⋮ 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\) ⋮ Compression techniques in group theory

Cites Work

• Conjugacy in Baumslag's group, generic case complexity, and division in power circuits
• The complexity of membership problems for circuits over sets of integers
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• On uniform circuit complexity
• A very hard log-space counting class
• Finite central height in linear groups
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Predicting nonlinear cellular automata quickly by decomposing them into linear ones
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• The complexity of matrix rank and feasible systems of linear equations
• Subset sum problem in polycyclic groups
• On a problem of Philip Hall
• Free subgroups in linear groups
• Algorithmics on SLP-compressed strings: A survey
• Parallel Identity Testing for Skew Circuits with Big Powers and Applications
• On certain classes of infinite solvable groups
• Primality and identity testing via Chinese remaindering
• Very Fast Parallel Polynomial Arithmetic
• On the Complexity of Numerical Analysis
• A taxonomy of problems with fast parallel algorithms
• Finite monoids and the fine structure of NC ¹
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• On the parallel complexity of linear groups
• Computing Algebraic Formulas Using a Constant Number of Registers
• Word Problems Solvable in Logspace
• The Commutator Subgroup of a Group Generated by Two Operators
• Finite Monoids: From Word to Circuit Evaluation
• TC^0 circuits for algorithmic problems in nilpotent groups
• Rational subsets of unitriangular groups
• Computational Complexity
• The Compressed Word Problem for Groups
• Word Problems and Membership Problems on Compressed Words
• Shorter Notes: Representations of Polycyclic Groups
• Formal Theories for Linear Algebra
• Derandomizing polynomial identity tests means proving circuit lower bounds
• A presentation for the unipotent group over rings with identity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Evaluation of circuits over nilpotent and polycyclic groups