Processing succinct matrices and vectors
From MaRDI portal
Publication:2411035
DOI10.1007/s00224-015-9666-9zbMath1378.68087arXiv1402.3452MaRDI QIDQ2411035
Markus Lohrey, Manfred Schmidt-Schauss
Publication date: 20 October 2017
Published in: Theory of Computing Systems, Computer Science - Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1402.3452
68Q25: Analysis of algorithms and problem complexity
68W30: Symbolic computation and algebraic computation
15B33: Matrices over special rings (quaternions, finite fields, etc.)
68P05: Data structures
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Leaf languages and string compression
- The complexity of tree automata and XPath on grammar-compressed trees
- More concise representation of regular languages by automata and regular expressions
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- A very hard log-space counting class
- Nondeterministic \(NC^1\) computation
- The complexity of tensor calculus
- Finite presentations of infinite structures: Automata and interpretations
- Functions computable in polynomial space
- On the complexity of pattern matching for highly compressed two-dimensional texts.
- On the complexity of the multivariate resultant
- Isomorphism of regular trees and words
- The complexity of tensor circuit evaluation
- Algorithmics on SLP-compressed strings: A survey
- Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs
- The Complexity of Counting Models of Linear-time Temporal Logic
- Polynomial Space Counting Problems
- Integer Programming with a Fixed Number of Variables
- Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes
- Evaluating Matrix Circuits
- Succinct representations of graphs
- PP is as Hard as the Polynomial-Time Hierarchy
- SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS
- A taxonomy of problems with fast parallel algorithms
- Graph-Based Algorithms for Boolean Function Manipulation
- Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
- The size of reduced OBDD's and optimal read-once branching programs for almost all Boolean functions
- Threshold Circuits for Iterated Matrix Product and Powering
