On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace

DOI10.1007/978-3-662-47672-7_34zbMath1440.68332OpenAlexW2293668387WikidataQ62398444 ScholiaQ62398444MaRDI QIDQ3448804

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

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

Related Items (3)

On approximating the eigenvalues of stochastic matrices in probabilistic logspace ⋮ Unnamed Item ⋮ A Complete Characterization of Unitary Quantum Space

Cites Work

• Pseudorandom generators for space-bounded computation
• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• Space-bounded quantum complexity
• Uniform approximation of \(\text{sgn} (x)\) by polynomials and entire functions
• Undirected connectivity in log-space
• A taxonomy of problems with fast parallel algorithms
• Fast Parallel Matrix Inversion Algorithms
• Polynomial Approximation of Piecewise Analytic Functions
• Bounded Independence Fools Halfspaces
• Inverting well conditioned matrices in quantum logspace
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace