Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Amir Sarid:

TR16-120 | 1st August 2016
Dean Doron, Amir Sarid, Amnon Ta-Shma

On approximating the eigenvalues of stochastic matrices in probabilistic logspace

Revisions: 1

Approximating the eigenvalues of a Hermitian operator can be solved
by a quantum logspace algorithm. We introduce the problem of
approximating the eigenvalues of a given matrix in the context of
classical space-bounded computation. We show that:

- Approximating the second eigenvalue of stochastic operators (in a
certain range of ... more >>>

ISSN 1433-8092 | Imprint