Abstract
The van Lambalgen theorem is a surprising result in algorithmic information theory concerning the symmetry of relative randomness. It establishes that for any pair of infinite sequences A and B, B is Martin-Löf random and A is Martin-Löf random relative to B if and only if the interleaved sequence \(A \uplus B\) is Martin-Löf random. This implies that A is relative random to B if and only if B is random relative to A [1,2,3]. This paper studies the validity of this phenomenon for different notions of time-bounded relative randomness.
We prove the classical van Lambalgen theorem using martingales and Kolmogorov compressibility. We establish the failure of relative randomness in these settings, for both time-bounded martingales and time-bounded Kolmogorov complexity. We adapt our classical proofs when applicable to the time-bounded setting, and construct counterexamples when they fail. The mode of failure of the theorem may depend on the notion of time-bounded randomness.
D. Chakraborty has been supported by the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement n. 616787.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
It is also common to use \(\oplus \), but we want to avoid confusion with the bitwise xor operation.
- 2.
Considering time bound that is dependent on output length is not unnatural for decompressors. To make it input-length dependent it is customary to append \(1^l\) as an additional input where l is the output length.
References
van Lambalgen, M.: Random Sequences. Academish Proefschri’t, Amsterdam (1987)
Nies, A.: Computability and Randomness. Oxford University Press, Inc., Oxford (2009)
Downey, R., Hirschfeldt, D.: Algorithmic randomness and complexity. Book Draft (2006)
Yu, L.: When van Lambalgen’s theorem fails. Proc. Am. Math. Soc. 135(3), 861–864 (2007)
Goldreich, O.: The Foundations of Cryptography. Basic Techniques, vol. 1. Cambridge University Press, Cambridge (2001)
Longpré, L., Watanabe, O.: On symmetry of information and polynomial-time invertibility. Inf. Comput. 121, 14–22 (1995)
Lee, T., Romaschenko, A.: Resource-bounded symmetry of information revisited. Theor. Comput. Sci. 345, 386–405 (2005)
Li, M., Vitányi, P.M.B.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer, Berlin (2008)
Lutz, J.H.: Resource-bounded measure. In: Proceedings of the 13th IEEE Conference on Computational Complexity, pp. 236–248. IEEE Computer Society Press, New York (1998)
Allender, E., Buhrman, H., Koucký, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. SIAM J. Comput. 35(4), 1467–1493 (2006)
Miller, J.S., Yu, L.: On initial segment complexity and degrees of randomness. Trans. Am. Math. Soc. 360(6), 3193–3210 (2008)
Acknowledgments
The authors would like to acknowledge Jack Lutz, Manjul Gupta and Michal Koucký for helpful discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Chakraborty, D., Nandakumar, S., Shukla, H. (2017). On Resource-Bounded Versions of the van Lambalgen Theorem. In: Gopal, T., Jäger , G., Steila, S. (eds) Theory and Applications of Models of Computation. TAMC 2017. Lecture Notes in Computer Science(), vol 10185. Springer, Cham. https://doi.org/10.1007/978-3-319-55911-7_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-55911-7_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-55910-0
Online ISBN: 978-3-319-55911-7
eBook Packages: Computer ScienceComputer Science (R0)