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
Leonard Adleman, 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
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
References
- Leonard Adleman, 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
- 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$, $\mathbf {P}^{A}\not =\mathbf {NP}^{A}\not =\mathrm {co}-\mathbf {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 $\mathbf {P}=\mathbf {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_20
- 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
- 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
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
