Evaluating matrix circuits

DOI10.1007/978-3-319-21398-9_19MaRDI QIDQ3196387zbMATH OpenOpenAlexFDO

Authors Markus Lohrey, D. König

Publication date 29 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Abstract: The circuit evaluation problem (also known as the compressed word problem) for finitely generated linear groups is studied. The best upper bound for this problem is $mathsfcoRP$, which is shown by a reduction to polynomial identity testing. Conversely, the compressed word problem for the linear group $mathsf{SL}_3(mathbbZ)$ is equivalent to polynomial identity testing. In the paper, it is shown that the compressed word problem for every finitely generated nilpotent group is in $mathsfDETsubseteqmathsf{NC}^2$. Within the larger class of polycyclic groups we find examples where the compressed word problem is at least as hard as polynomial identity testing for skew arithmetic circuits.

Recommendations

• Evaluation of circuits over nilpotent and polycyclic groups
• Finite Monoids: From Word to Circuit Evaluation
• scientific article; zbMATH DE number 512861
• Parallel identity testing for skew circuits with big powers and applications
• Parallel identity testing for skew circuits with big powers and applications

Cites work

• scientific article; zbMATH DE number 3642708 (Why is no real title available?)
• scientific article; zbMATH DE number 3875506 (Why is no real title available?)
• scientific article; zbMATH DE number 706263 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• A presentation for the unipotent group over rings with identity
• A taxonomy of problems with fast parallel algorithms
• A very hard log-space counting class
• Algorithmics on SLP-compressed strings: a survey
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Evaluating matrix circuits
• Finite Monoids: From Word to Circuit Evaluation
• Finite central height in linear groups
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• On a problem of Philip Hall
• On the Complexity of Numerical Analysis
• Parallel identity testing for skew circuits with big powers and applications
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• Rational subsets of unitriangular groups.
• Shorter Notes: Representations of Polycyclic Groups
• The Compressed Word Problem for Groups
• The complexity of matrix rank and feasible systems of linear equations
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Word Problems Solvable in Logspace
• Word Problems and Membership Problems on Compressed Words

Cited in

(9)

• Logspace and compressed-word computations in nilpotent groups
• Parallel complexity for nilpotent groups
• Knapsack in graph groups
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Evaluation of circuits over nilpotent and polycyclic groups
• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
• Parallel identity testing for skew circuits with big powers and applications
• Parallel identity testing for skew circuits with big powers and applications
• Evaluating matrix circuits

This page was built for publication: Evaluating matrix circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196387)