Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

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

Book Review

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

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

Author: József Beck
Title: Inevitable randomness in discrete mathematics
Additional book information: University Lecture Series, 49, American Mathematical Society, Providence, RI, 2009, xiii+250 pp., ISBN 978-0-8218-4756-5, US $59.00

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

  • [AH92] Leonard M. Adleman and Ming-Deh A. Huang, Primality testing and abelian varieties over finite fields, Lecture Notes in Mathematics, vol. 1512, Springer-Verlag, Berlin, 1992. MR 1176511 (93g:11128)
  • [AKS02] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781-793. MR 2123939 (2006a:11170),
  • [AB09] Sanjeev Arora and Boaz Barak, Computational complexity: A modern approach, Cambridge University Press, Cambridge, 2009. MR 2500087 (2010i:68001)
  • [Bec08] József Beck, Combinatorial games: Tic-Tac-Toe Theory, Encyclopedia of Mathematics and its Applications, vol. 114, Cambridge University Press, Cambridge, 2008. MR 2402857 (2009g:91038)
  • [DF88] Martin E. Dyer and Alan M. Frieze, On the complexity of computing the volume of a polyhedron, SIAM J. Comput., 17 (1988), no. 5, 967-974.
  • [DFK91] Martin Dyer, Alan Frieze, and Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, J. Assoc. Comput. Mach. 38 (1991), no. 1, 1-17. MR 1095916 (91m:68162),
  • [Ede87] Herbert Edelsbrunner, Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, Berlin, 1987. MR 904271 (89a:68205)
  • [For09] Lance Fortnow, The status of the $ \mathbf {P}$ versus $ \mathbf {NP}$ problem, Commun. ACM 52 (2009), no. 9, 78-86.
  • [IK04] 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 (2005i:68025),
  • [IW97] Russell Impagliazzo and Avi Wigderson, $ {\rm P}={\rm BPP}$ if $ {\rm E}$ requires exponential circuits: derandomizing the XOR lemma, STOC '97 (El Paso, TX), ACM, New York, 1999, pp. 220-229 (electronic). MR 1715634
  • [Koi11] Pascal Koiran, Shallow Circuits with High-Powered Inputs, in Proceedings of Innovations in Computer Science (ICS 2011, Jan. 6-9, 2011, Beijing China), Tsinghua University Press, Beijing.
  • [Lip09] Richard Lipton, Gödel's Lost Letter and $ \mathbf {P}\!=\!\mathbf {NP}$, blog entry, http://rjlipton. .
  • [Pap95] Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285 (95f:68082)
  • [Sim03] Miklós Simonovits, How to compute the volume in high dimension?, Math. Program. 97 (2003), no. 1-2, Ser. B, 337-374. ISMP, 2003 (Copenhagen). MR 2004402 (2004j:68194)
  • [Sip92] Michael Sipser, The history and status of the $ \mathbf {P}$ versus $ \mathbf {NP}$ question, in Proceedings STOC '92 (Twenty-Fourth Annual ACM Symposium on Theory of Computing), pp. 603-618, ACM Press, 1992.
  • [SS77] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84-85. MR 0429721 (55 #2732)
  • [Sto00] Arne Storjohann, Algorithms for matrix canonical forms, doctoral dissertation, Swiss Federal Institute of Technology, Zurich, 2000.
  • [Sze75] E. Szemerédi, On sets of integers containing no $ k$ elements in arithmetic progression, Acta Arith. 27 (1975), 199-245. Collection of articles in memory of Juriĭ Vladimirovič Linnik. MR 0369312 (51 #5547)
  • [Tao06] Terence Tao, A quantitative ergodic theory proof of Szemerédi's theorem, Electron. J. Combin. 13 (2006), no. 1, Research Paper 99, 49. MR 2274314 (2007i:37016)

Review Information:

Reviewer: J. Maurice Rojas
Affiliation: TAMU 3368, Texas A&M University, College Station, Texas 77843-3368
Journal: Bull. Amer. Math. Soc. 50 (2013), 481-487
MSC (2010): Primary 60-02, 05-02, 91A46; Secondary 05D40, 11K38
Published electronically: April 5, 2013
Review copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
American Mathematical Society