Evaluating matrix circuits

DOI10.1007/978-3-319-21398-9_19zbMATH Open1386.68061arXiv1502.03540OpenAlexW2962914768MaRDI QIDQ3196387FDOQ3196387

Authors: Markus Lohrey, D. König 

Publication date: 29 October 2015

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

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.

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

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

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)

Cites Work

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

Cited In (9)

• Logspace and compressed-word computations in nilpotent groups
• Parallel complexity for nilpotent groups
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Knapsack in graph 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)