Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MATRIX POWERING:
Reports tagged with Matrix Powering:
TR13-177 | 10th December 2013
Eric Allender, Nikhil Balaji, Samir Datta

#### Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs

Revisions: 1

We present improved uniform TC$^0$ circuits for division, matrix powering, and related problems, where the improvement is in terms of majority depth'' (initially studied by Maciel and Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in ... more >>>

TR20-087 | 8th June 2020
Uma Girish, Ran Raz, Wei Zhan

#### Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

Revisions: 2

We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most 1. The algorithm gets as an input an arbitrary $n\times n$ contraction matrix $A$, and a parameter $T \leq poly(n)$ and outputs the entries of $A^T$, up to (arbitrary) polynomially small additive ... more >>>

TR22-008 | 14th January 2022
Gil Cohen, Dean Doron, Ori Sberlo

#### Approximating Large Powers of Stochastic Matrices in Small Space

We give a deterministic space-efficient algorithm for approximating powers of stochastic matrices. On input a $w \times w$ stochastic matrix $A$, our algorithm approximates $A^{n}$ in space $\widetilde{O}(\log n + \sqrt{\log n}\cdot \log w)$ to within high accuracy. This improves upon the seminal work by Saks and Zhou (FOCS'95), that ... more >>>

TR22-149 | 7th November 2022
Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma

#### Approximating Iterated Multiplication of Stochastic Matrices in Small Space

Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem's space complexity as it constitutes the main route towards resolving the $\mathbf{BPL}$ vs. $\mathbf{L}$ problem. The seminal work by Saks and Zhou (FOCS 1995) ... more >>>

ISSN 1433-8092 | Imprint