Linear Advice for Randomized Logarithmic Space

DOI10.1007/11672142_38MaRDI QIDQ5449822zbMATH OpenOpenAlexFDO

Authors Adam R. Klivans, Lance Fortnow

Publication date 19 March 2008

Published in STACS 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11672142_38

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• A note on the advice complexity of multipass randomized logspace
• Space hierarchy results for randomized models
• \(\text{RL}\subseteq \text{SC}\)
• THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA
• Space hierarchy results for randomized and other semantic models

Cited in

(4)

• On probabilistic space-bounded machines with multiple access to random tape
• Pseudorandom generators for combinatorial checkerboards
• A note on the advice complexity of multipass randomized logspace
• Typically-correct derandomization for small time and space

This page was built for publication: Linear Advice for Randomized Logarithmic Space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5449822)