On the de-randomization of space-bounded approximate counting problems

DOI10.1016/j.ipl.2015.03.005zbMath1329.68287OpenAlexW1974611482WikidataQ62398447 ScholiaQ62398447MaRDI QIDQ2348703

Amnon Ta-Shma, Dean Doron

Publication date: 15 June 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.03.005

zbMATH Keywords

computational complexityapproximation algorithmsrandomized algorithmsspace-bounded computationspace-bounded quantum computationspace-bounded approximation schemes

Mathematics Subject Classification ID

Approximation algorithms (68W25) Randomized algorithms (68W20) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (1)

On approximating the eigenvalues of stochastic matrices in probabilistic logspace

Cites Work

• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• Pseudorandomness for approximate counting and sampling
• Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• In a World of P=BPP
• On Approximation Algorithms for # P
• Inverting well conditioned matrices in quantum logspace

This page was built for publication: On the de-randomization of space-bounded approximate counting problems