Abstract
We show that RL ⊆ L/O(n), i.e., any language computable in randomized logarithmic space can be computed in deterministic logarithmic space with a linear amount of non-uniform advice. To prove our result we use an ultra-low space walk on the Gabber-Galil expander graph due to Gutfreund and Viola.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Adleman, L.: Two theorems on random polynomial time. In: Proceedings of the 19th IEEE Symposium on Foundations of Computer Science, pp. 75–83. IEEE, New York (1978)
Allender, E., Barrington, D., Hesse, W.: Uniform circuits for division: Consequences and problems. In: Annual IEEE Conference on Computational Complexity, vol. 16 (2001)
Bar-Yossef, Z., Goldreich, O., Wigderson, A.: Deterministic amplification of space-bounded probabilistic algorithms. In: Proceedings of the 14th IEEE Conference on Computational Complexity, pp. 188–199. IEEE, New York (1999)
Chiu, A., Davida, G., Litow, B.: Division in logspace-uniform NC1. RAIRO - Theoretical Informatics and Applications 35, 259–275 (2001)
Cohen, A., Wigderson, A.: Dispensers, deterministic amplification, and weak random sources (extended abstract). In: Proc. 30th Ann. IEEE Symp. on Foundations of Computer Science, Research Triangle Park, NC, oct, pp. 14–25. IEEE Computer Society Press, Los Alamitos (1989)
Gabber, O., Galil, Z.: Explicit constructions of linear-sized superconcentrators. Journal of Computer and System Sciences 22(3), 407–420 (1981)
Goldreich, O., Wigderson, A.: Derandomization that is rarely wrong from short advice that is typically good. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol. 2483, Springer, Heidelberg (2002)
Gutfreund, D., Viola, E.: Fooling parity tests with parity gates. In: Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM) (2004)
Impagliazzo, R., Zuckerman, D.: How to recycle random bits. In: Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pp. 248–253. IEEE, New York (1989)
Karp, R., Lipton, R.: Some connections between nonuniform and uniform complexity classes. In: Proceedings of the 12th ACM Symposium on the Theory of Computing, pp. 302–309. ACM, New York (1980)
Linial, N., Wigderson, A.: Lecture notes on expander graphs and their applications (2002), http://www.math.ias.edu/~boaz/ExpanderCourse/index.html
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1997)
Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica 12(4), 449–461 (1992)
Reingold, O.: Undirected st-connectivity in log-space. In: Proceedings of the 36th ACM Symposium on the Theory of Computing, ACM Press, New York (2005)
Reingold, O., Trevisan, L., Vadhan, S.: Pseudorandom walks in biregular graphs and the RL vs. L problem. Technical Report TR05-022, Electronic Colloquium on Computational Complexity (2005)
Saks, M., Zhou, S.: BP H SPACE(S) ⊆ DPSPACE(S3/2). Journal of Computer and System Sciences 58(2), 376–403 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fortnow, L., Klivans, A.R. (2006). Linear Advice for Randomized Logarithmic Space. In: Durand, B., Thomas, W. (eds) STACS 2006. STACS 2006. Lecture Notes in Computer Science, vol 3884. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11672142_38
Download citation
DOI: https://doi.org/10.1007/11672142_38
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32301-3
Online ISBN: 978-3-540-32288-7
eBook Packages: Computer ScienceComputer Science (R0)