On approximating the eigenvalues of stochastic matrices in probabilistic logspace

DOI10.1007/s00037-016-0150-yzbMath1378.68049OpenAlexW2561287843WikidataQ62398443 ScholiaQ62398443MaRDI QIDQ2410679

Amir Sarid, Dean Doron, Amnon Ta-Shma

Publication date: 18 October 2017

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-016-0150-y

zbMATH Keywords

random walksrandomized algorithmscomplete problemsbounded space computation

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items (5)

Unary probabilistic and quantum automata on promise problems ⋮ Unnamed Item ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ A Complete Characterization of Unitary Quantum Space ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
• Symmetric space-bounded computation
• Pseudorandom generators for space-bounded computation
• \(\text{RL}\subseteq \text{SC}\)
• Hardness vs randomness
• Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems
• Space-bounded quantum complexity
• On the de-randomization of space-bounded approximate counting problems
• Equivalence of polynomial identity testing and polynomial factorization
• Uniform approximation of \(\text{sgn} (x)\) by polynomials and entire functions
• Pseudorandom walks on regular digraphs and the RL vs. L problem
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace
• 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
• A compendium of problems complete for symmetric logarithmic space

This page was built for publication: On approximating the eigenvalues of stochastic matrices in probabilistic logspace