On Approximating the Eigenvalues of Stochastic Matrices in Probabilistic Logspace
On Approximating the Eigenvalues of Stochastic Matrices in Probabilistic Logspace
复制标题
关于概率对数空间中随机矩阵特征值的逼近
DOI：
10.1007/s00037-016-0150-y
复制
发表时间：
2017
影响因子：
1.4
通讯作者：
A. Ta
中科院分区：
文献类型：
--
作者：
Dean Doron;Amir Sarid;A. Ta
我们证明了近似随机算子的第二特征值是bpl完备的，从而给出了该类的一个自然完备问题。我们还证明了在BPL中可以近似任意具有恒定精度的随机和厄米算子的特征值。这项工作与该主题的相关工作一起揭示了一个图像，其中各种空间有界类（例如，概率对数空间，量子对数空间和类DET）可以用代数问题（例如近似谱间隙）来表征，其中，粗略地说，类之间的区别在于它们可以处理的算子的种类（例如，随机，厄米或任意）。
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).