Evaluation of circuits over nilpotent and polycyclic groups
From MaRDI portal
Publication:1750355
DOI10.1007/s00453-017-0343-zzbMath1390.68311OpenAlexW2725306094MaRDI QIDQ1750355
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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 1
- 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
