On the problem of approximating the eigenvalues of undirected graphs in probabilistic logspace
DOI10.1007/978-3-662-47672-7_34zbMATH Open1440.68332OpenAlexW2293668387WikidataQ62398444 ScholiaQ62398444MaRDI QIDQ3448804FDOQ3448804
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
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
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)
Cites Work
- Title not available (Why is that?)
- Undirected connectivity in log-space
- A taxonomy of problems with fast parallel algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Bounded Independence Fools Halfspaces
- Fast Parallel Matrix Inversion Algorithms
- Pseudorandom generators for space-bounded computation
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- Uniform approximation of \(\text{sgn} (x)\) by polynomials and entire functions
- Polynomial Approximation of Piecewise Analytic Functions
- Space-bounded quantum complexity
- Inverting well conditioned matrices in quantum logspace
Cited In (4)
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)
