2026-07-20T05:29:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6500 2024-03-06T10:38:17Z ddc:004 open_access

A Note on the Advice Complexity of Multipass Randomized Logspace Dixon, Peter Mandal, Debasis Pavan, A. Vinodchandran, N. V. space-bounded computations randomized machines advice Investigating the complexity of randomized space-bounded machines that are allowed to make multiple passes over the random tape has been of recent interest. In particular, it has been shown that derandomizing such probabilistic machines yields a weak but new derandomization of probabilistic time-bounded classes. In this paper we further explore the complexity of such machines. In particular, as our main result we show that for any epsilon<1, every language that is accepted by an O(n^epsilon)-pass, randomized logspace machine can be simulated in deterministic logspace with linear amount of advice. This result extends an earlier result of Fortnow and Klivans who showed that RL is in deterministic logspace with linear advice. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peter Dixon and Debasis Mandal and A. Pavan and N. V. Vinodchandran 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.31 urn:nbn:de:0030-drops-65003 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.31 eng https://creativecommons.org/licenses/by/3.0/legalcode