Processing succinct matrices and vectors

DOI10.1007/s00224-015-9666-9zbMath1378.68087arXiv1402.3452OpenAlexW1902950374MaRDI 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

zbMATH Keywords

matrix computationmulti-terminal decision diagramssuccinct matrix representations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Data structures (68P05)

Related Items (1)

The complexity of counting models of linear-time temporal logic

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

This page was built for publication: Processing succinct matrices and vectors