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) Analysis of algorithms and problem complexity (68Q25) Quantum algorithms and complexity in the theory of computing (68Q12) Approximation algorithms (68W25) Stochastic matrices (15B51)

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

• 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?)
• A taxonomy of problems with fast parallel algorithms
• Bounded Independence Fools Halfspaces
• Fast Parallel Matrix Inversion Algorithms
• 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
• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)

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
• Probabilistic logarithmic-space algorithms for Laplacian solvers
• A complete characterization of unitary quantum space

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)