Evaluating Matrix Circuits

DOI10.1007/978-3-319-21398-9_19zbMath1386.68061arXiv1502.03540OpenAlexW2962914768MaRDI QIDQ3196387

Markus Lohrey, Daniel 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)

Related Items

Evaluating Matrix Circuits, Parallel complexity for nilpotent groups, Processing succinct matrices and vectors, Parallel Identity Testing for Skew Circuits with Big Powers and Applications, Logspace and compressed-word computations in nilpotent groups, Knapsack in graph groups, Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups, TC^0 circuits for algorithmic problems in nilpotent groups

Cites Work

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