Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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 Therien). 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 >>>




ISSN 1433-8092 | Imprint