Abstract
We introduce the problem of approximating the eigenvalues of a given stochastic/symmetric matrix in the context of classical space-bounded computation.
The problem can be exactly solved in \(\mathsf {DET}\subseteq \mathsf {NC}^2\). Recently, it has been shown that the approximation problem can be solved by a quantum logspace algorithm. We show a \(\mathsf {BPL}\) algorithm that approximates any eigenvalue with a constant accuracy. The result we obtain falls short of achieving the polynomially-small accuracy that the quantum algorithm achieves. Thus, at our current state of knowledge, we can achieve polynomially-small accuracy with quantum logspace algorithms, constant accuracy with probabilistic logspace algorithms, and no non-trivial result is known for deterministic logspace algorithms. The quantum algorithm also has the advantage of working over arbitrary, possibly non-stochastic Hermitian operators.
Our work raises several challenges. First, a derandomization challenge, trying to achieve a deterministic algorithm approximating eigenvalues with some non-trivial accuracy. Second, a de-quantumization challenge, trying to decide whether the quantum logspace model is strictly stronger than the classical probabilistic one or not. It also casts the deterministic, probabilistic and quantum space-bounded models as problems in linear algebra with differences between symmetric, stochastic and arbitrary operators. We therefore believe the problem of approximating the eigenvalues of a graph is not only natural and important by itself, but also important for understanding the relative power of deterministic, probabilistic and quantum logspace computation.
D. Doron—Supported by the Israel science Foundation grant no. 994/14, by the United States – Israel Binational Science Foundation grant no. 2010120 and by the Blavatnik Fund.
A. Ta-Shma—Supported by the Israel science Foundation grant no. 994/14 and by the United States – Israel Binational Science Foundation grant no. 2010120.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica 12, 449–461 (1992)
Saks, M.E., Zhou, S.: BP\(_{H}\)SPACE(S) \(\subseteq \) DSPACE(S\(^{{3/2}}\)). J. Comput. Syst. Sci. 58, 376–403 (1999)
Reingold, O.: Undirected connectivity in log-space. J. ACM 55 (2008)
Aleliunas, R., Karp, R.M., Lipton, R., Lovasz, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: 20th Annual Symposium on Foundations of Computer Science, pp. 218–223 (1979)
Cook, S.A.: A taxonomy of problems with fast parallel algorithms. Information and Control 64 (1985); International Conference on Foundations of Computation Theory
Csansky, L.: Fast parallel matrix inversion algorithms. SIAM Journal of Computing 5, 618–623 (1976)
Watrous, J.: Space-bounded quantum complexity. Journal of Computer and System Sciences 59, 281–326 (1999)
van Melkebeek, D., Watson, T.: Time-space efficient simulations of quantum computations. Electronic Colloquium on Computational Complexity (ECCC) 17, 147 (2010)
Ta-Shma, A.: Inverting well conditioned matrices in quantum logspace. In: Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing, STOC 2013, pp. 881–890. ACM, New York (2013)
Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009)
Ben-Or, M., Eldar, L.: Optimal algorithms for linear algebra by quantum inspiration. CoRR abs/1312.3717 (2013)
Hoffman, K.: Banach Spaces of Analytic Functions. Dover Books on Mathematics Series. Dover Publications, Incorporated (2007)
Saff, E.B., Totik, V.: Polynomial approximation of piecewise analytic functions. Journal of the London Mathematical Society s2–39, 487–498 (1989)
Eremenko, A., Yuditskii, P.: Uniform approximation of sgn(x) by polynomials and entire functions. Journal d’Analyse Mathématique 101, 313–324 (2007)
Diakonikolas, I., Gopalan, P., Jaiswal, R., Servedio, R.A., Viola, E.: Bounded independence fools halfspaces. SIAM Journal on Computing 39, 3441–3462 (2010)
Timan, A.: Theory of Approximation of Functions of a Real Variable. Dover books on advanced mathematics. Pergamon Press (1963)
Rivlin, T.: The Chebyshev polynomials. Pure and applied mathematics. Wiley (1974)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Doron, D., Ta-Shma, A. (2015). On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_34
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_34
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)