On the problem of approximating the eigenvalues of undirected graphs in probabilistic logspace

DOI10.1007/978-3-662-47672-7_34MaRDI QIDQ3448804zbMATH OpenOpenAlexWikidataFDO

Authors Dean Doron, Amnon Ta-Shma

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-47672-7_34

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Stochastic matrices (15B51) Quantum algorithms and complexity in the theory of computing (68Q12) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• On approximating the eigenvalues of stochastic matrices in probabilistic logspace
• On the de-randomization of space-bounded approximate counting problems
• A quasi-random approach to matrix spectral analysis
• On the complexity of the multivariate Sturm-Liouville eigenvalue problem
• Inverting well conditioned matrices in quantum logspace

Cites work

• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• A taxonomy of problems with fast parallel algorithms
• Bounded Independence Fools Halfspaces
• Fast Parallel Matrix Inversion Algorithms
• scientific article; zbMATH DE number 3469437 (Why is no real title available?)
• scientific article; zbMATH DE number 3191390 (Why is no real title available?)
• scientific article; zbMATH DE number 3191538 (Why is no real title available?)
• Inverting well conditioned matrices in quantum logspace
• Polynomial Approximation of Piecewise Analytic Functions
• Pseudorandom generators for space-bounded computation
• Space-bounded quantum complexity
• Undirected connectivity in log-space
• Uniform approximation of \(\text{sgn} (x)\) by polynomials and entire functions

Cited in

(5)

• On the de-randomization of space-bounded approximate counting problems
• On approximating the eigenvalues of stochastic matrices in probabilistic logspace
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
• A complete characterization of unitary quantum space
• Probabilistic logarithmic-space algorithms for Laplacian solvers

This page was built for publication: On the problem of approximating the eigenvalues of undirected graphs in probabilistic logspace

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448804)