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 (8)

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

This page was built for publication: Evaluating Matrix Circuits