On Approximating the Eigenvalues of Stochastic Matrices in Probabilistic Logspace
| Autor: | Amnon Ta-Shma, Dean Doron, Amir Sarid |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
General Mathematics 010102 general mathematics Probabilistic logic 0102 computer and information sciences Random walk 01 natural sciences Hermitian matrix Theoretical Computer Science Computational Mathematics Computational Theory and Mathematics 010201 computation theory & mathematics Spectral gap 0101 mathematics Algebraic number Constant (mathematics) Self-adjoint operator Eigenvalues and eigenvectors Mathematics |
| Zdroj: | computational complexity. 26:393-420 |
| ISSN: | 1420-8954 1016-3328 |
| DOI: | 10.1007/s00037-016-0150-y |
| Popis: | We show that approximating the second eigenvalue of stochastic operators is BPL-complete, thus giving a natural problem complete for this class. We also show that approximating any eigenvalue of a stochastic and Hermitian operator with constant accuracy can be done in BPL. This work together with related work on the subject reveal a picture where the various space-bounded classes (e.g., probabilistic logspace, quantum logspace and the class DET) can be characterized by algebraic problems (such as approximating the spectral gap) where, roughly speaking, the difference between the classes lies in the kind of operators they can handle (e.g., stochastic, Hermitian or arbitrary). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink