Skip to Main Content

Bulletin of the American Mathematical Society

Published by the American Mathematical Society, the Bulletin of the American Mathematical Society (BULL) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-9485 (online) ISSN 0273-0979 (print)

The 2020 MCQ for Bulletin of the American Mathematical Society is 0.47.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


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

References [Enhancements On Off] (What's this?)

  • 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

  • Review Information:

    Reviewer: J. Maurice Rojas
    Affiliation: Texas A&M University, College Station, Texas
    Journal: Bull. Amer. Math. Soc. 57 (2020), 339-346
    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