Book Reviews
Book reviews do not contain an abstract.
You may download the entire review from the links below.
- MathSciNet review: 4076538
- Full text review in PDF
- This review is available free of charge
- Kolmogorov complexity and algorithmic randomness by Alexander Shen, Vladimir A. Uspensky and Nikolay K. Vereshchagin
- Bull. Amer. Math. Soc. 57 (2020), 339-346
- Additional book information: Mathematical Surveys and Monographs, Vol. 220, American Mathematical Society, Providence, RI, 2017, xviii+511 pp., ISBN 9781470431822
References
- Leonard Adleman, Two theorems on random polynomial time, 19th Annual Symposium on Foundations of Computer Science (Ann Arbor, Mich., 1978) IEEE, Long Beach, CA, 1978, pp. 75–83. MR 539832
- D. Adrian, K. Bhargavan, Z. Durumeric, P. Gaudry, M. Green, J. A. Halderman, N. Heninger, D. Springall, E. Thomé, L. Valenta, B. VanderSloot, E. Wustrow, S. Zanella-Béguelin, and P. Zimmermann, Imperfect forward secrecy: how Diffie-Hellman fails in practice, Comm. Amer. Comput. Mach., January 2019, Vol. 62, No. 1, pp. 106–114. doi 10.1145/3292035
- Sanjeev Arora and Boaz Barak, Computational complexity, Cambridge University Press, Cambridge, 2009. A modern approach. MR 2500087, DOI 10.1017/CBO9780511804090
- Eric Bach and Jeffrey Shallit, Algorithmic number theory. Vol. 1, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. Efficient algorithms. MR 1406794
- Charles H. Bennett and John Gill, Relative to a random oracle $A$, $\textbf {P}^{A}\not =\textbf {NP}^{A}\not =\textrm {co}-\textbf {NP}^{A}$ with probability $1$, SIAM J. Comput. 10 (1981), no. 1, 96–113. MR 605606, DOI 10.1137/0210008
- M. Blum, e-mail communication, March 23, 2019.
- Manuel Blum and Silvio Micali, How to generate cryptographically strong sequences of pseudorandom bits, SIAM J. Comput. 13 (1984), no. 4, 850–864. MR 764183, DOI 10.1137/0213053
- Persi Diaconis, Susan Holmes, and Richard Montgomery, Dynamical bias in the coin toss, SIAM Rev. 49 (2007), no. 2, 211–235. MR 2327054, DOI 10.1137/S0036144504446436
- Oded Goldreich, In a world of $\textbf {P}=\textbf {BPP}$, Studies in complexity and cryptography, Lecture Notes in Comput. Sci., vol. 6650, Springer, Heidelberg, 2011, pp. 191–232. MR 2844264, DOI 10.1007/978-3-642-22670-0_{2}0
- Parikshit Gopalan, Daniel M. Kane, and Raghu Meka, Pseudorandomness via the discrete Fourier transform, SIAM J. Comput. 47 (2018), no. 6, 2451–2487. MR 3892445, DOI 10.1137/16M1062132
- Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman, An introduction to mathematical cryptography, 2nd ed., Undergraduate Texts in Mathematics, Springer, New York, 2014. MR 3289167, DOI 10.1007/978-1-4939-1711-2
- Valentine Kabanets and Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Comput. Complexity 13 (2004), no. 1-2, 1–46. MR 2105971, DOI 10.1007/s00037-004-0182-6
- R. Impagliazzo and A. Wigderson, $\mathbf {P}\!=\!\mathbf {BPP}$ unless $E$ has subexponential circuits: derandomizing the XOR Lemma, Proceedings of the 29th STOC, pp. 220–229, 1997.
- V. Kabanets, Derandomization: a brief overview, in Current Trends in Theoretical Computer Science: The Challenge of the New Century, Vol 1: Algorithms and Complexity, edited by G. Paun, G. Rosenberg, and A. Salomaa, World Scientific Publishing Company, 2004.
- Ming Li and Paul Vitányi, An introduction to Kolmogorov complexity and its applications, 3rd ed., Texts in Computer Science, Springer, New York, 2008. MR 2494387, DOI 10.1007/978-0-387-49820-1
- Raghu Meka and David Zuckerman, Pseudorandom generators for polynomial threshold functions, SIAM J. Comput. 42 (2013), no. 3, 1275–1301. MR 3504629, DOI 10.1137/100811623
- Noam Nisan, Using hard problems to create pseudorandom generators, ACM Distinguished Dissertations, MIT Press, Cambridge, MA, 1992. MR 1149128
- Noam Nisan, Pseudorandom generators for space-bounded computation, Combinatorica 12 (1992), no. 4, 449–461. MR 1194735, DOI 10.1007/BF01305237
- David Ruelle, Chance and chaos, Princeton University Press, Princeton, NJ, 1991. MR 1145490
- A. Shen, V. A. Uspensky, and N. Vereshchagin, Kolmogorov complexity and algorithmic randomness, Mathematical Surveys and Monographs, vol. 220, American Mathematical Society, Providence, RI, 2017. MR 3702040, DOI 10.1090/surv/220
- Salil P. Vadhan, Pseudorandomness, Found. Trends Theor. Comput. Sci. 7 (2011), no. 1-3, front matter, 1–336. MR 3019182, DOI 10.1561/0400000010
- Andrew C. Yao, Theory and applications of trapdoor functions, 23rd annual symposium on foundations of computer science (Chicago, Ill., 1982) IEEE, New York, 1982, pp. 80–91. MR 780384
Reviewer information
- Reviewer: J. Maurice Rojas
- Affiliation: Texas A&M University, College Station, Texas
- Email: rojas@math.tamu.edu
Additional Information
- Journal: Bull. Amer. Math. Soc. 57 (2020), 339-346
- DOI: https://doi.org/10.1090/bull/1676
- Published electronically: September 23, 2019
- Review Copyright: © Copyright 2019 American Mathematical Society