Book Review

The AMS does not provide abstracts of book reviews. You may download the entire review from the links below.

MathSciNet review: 4076538

Full text of review: PDF This review is available free of charge.

Book Information:

Authors: Alexander Shen, Vladimir A. Uspensky and Nikolay K. Vereshchagin

Title: Kolmogorov complexity and algorithmic randomness

Additional book information: Mathematical Surveys and Monographs, Vol. 220, American Mathematical Society, Providence, RI, 2017, xviii+511 pp., ISBN 9781470431822

*Two theorems on random polynomial time*, 19th Annual Symposium on Foundations of Computer Science (Ann Arbor, Mich., 1978) IEEE, Long Beach, Calif., 1978, pp. 75–83. MR

**539832**

*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

*Computational complexity*, Cambridge University Press, Cambridge, 2009. A modern approach. MR

**2500087**, DOI 10.1017/CBO9780511804090

*Algorithmic number theory. Vol. 1*, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. Efficient algorithms. MR

**1406794**

*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

*e-mail communication*, March 23, 2019.

*How to generate cryptographically strong sequences of pseudorandom bits*, SIAM J. Comput.

**13**(1984), no. 4, 850–864. MR

**764183**, DOI 10.1137/0213053

*Dynamical bias in the coin toss*, SIAM Rev.

**49**(2007), no. 2, 211–235. MR

**2327054**, DOI 10.1137/S0036144504446436

*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

*Pseudorandomness via the discrete Fourier transform*, SIAM J. Comput.

**47**(2018), no. 6, 2451–2487. MR

**3892445**, DOI 10.1137/16M1062132

*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

*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

*$\mathbf {P}\!=\!\mathbf {BPP}$ unless $E$ has subexponential circuits: derandomizing the XOR Lemma*, Proceedings of the 29th STOC, pp. 220–229, 1997.

*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.

*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

*Pseudorandom generators for polynomial threshold functions*, SIAM J. Comput.

**42**(2013), no. 3, 1275–1301. MR

**3504629**, DOI 10.1137/100811623

*Using hard problems to create pseudorandom generators*, ACM Distinguished Dissertations, MIT Press, Cambridge, MA, 1992. MR

**1149128**

*Pseudorandom generators for space-bounded computation*, Combinatorica

**12**(1992), no. 4, 449–461. MR

**1194735**, DOI 10.1007/BF01305237

*Chance and chaos*, Princeton University Press, Princeton, NJ, 1991. MR

**1145490**

*Kolmogorov complexity and algorithmic randomness*, Mathematical Surveys and Monographs, vol. 220, American Mathematical Society, Providence, RI, 2017. MR

**3702040**, DOI 10.1090/surv/220

*Pseudorandomness*, Found. Trends Theor. Comput. Sci.

**7**(2011), no. 1-3, front matter, 1–336. MR

**3019182**, DOI 10.1561/0400000010

*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**

Review Information:

Reviewer: J. Maurice Rojas

Affiliation: Texas A&M University, College Station, Texas

Email: rojas@math.tamu.edu

Journal: Bull. Amer. Math. Soc.

**57**(2020), 339-346

DOI: https://doi.org/10.1090/bull/1676

Published electronically: September 23, 2019

Additional Notes: The reviewer is partially supported by NSF grants CCF-1409020 and CCF-1900881, and by NSF REU grant DMS-1757872.

Review copyright: © Copyright 2019 American Mathematical Society