Book Review
The AMS does not provide abstracts of book reviews.
You may download the entire review from the links below.
MathSciNet review:
3049873
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
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, DOI 10.1007/BFb0090185
Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781–793. MR 2123939, DOI 10.4007/annals.2004.160.781
Sanjeev Arora and Boaz Barak, Computational complexity, Cambridge University Press, Cambridge, 2009. A modern approach. MR 2500087, DOI 10.1017/CBO9780511804090
József Beck, Combinatorial games, Encyclopedia of Mathematics and its Applications, vol. 114, Cambridge University Press, Cambridge, 2008. Tic-tac-toe theory. MR 2402857, DOI 10.1017/CBO9780511735202
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.
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, DOI 10.1145/102782.102783
Herbert Edelsbrunner, Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, Berlin, 1987. MR 904271, DOI 10.1007/978-3-642-61568-9
Lance Fortnow, The status of the $\mathbf {P}$ versus $\mathbf {NP}$ problem, Commun. ACM 52 (2009), no. 9, 78–86.
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
Russell Impagliazzo and Avi Wigderson, $\textrm {P}=\textrm {BPP}$ if $\textrm {E}$ requires exponential circuits: derandomizing the XOR lemma, STOC ’97 (El Paso, TX), ACM, New York, 1999, pp. 220–229. MR 1715634
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.
Richard Lipton, Gödel’s Lost Letter and $\mathbf {P}\!=\!\mathbf {NP}$, blog entry, http://rjlipton. wordpress.com/the-gdel-letter .
Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
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, DOI 10.1007/s10107-003-0447-x
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.
R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 429721, DOI 10.1137/0206006
Arne Storjohann, Algorithms for matrix canonical forms, doctoral dissertation, Swiss Federal Institute of Technology, Zurich, 2000.
E. Szemerédi, On sets of integers containing no $k$ elements in arithmetic progression, Acta Arith. 27 (1975), 199–245. MR 369312, DOI 10.4064/aa-27-1-199-245
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
References
- 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)
- 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), DOI 10.4007/annals.2004.160.781
- Sanjeev Arora and Boaz Barak, Computational complexity: A modern approach, Cambridge University Press, Cambridge, 2009. MR 2500087 (2010i:68001)
- 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), DOI 10.1017/CBO9780511735202
- 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.
- 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), DOI 10.1145/102782.102783
- Herbert Edelsbrunner, Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, Berlin, 1987. MR 904271 (89a:68205)
- Lance Fortnow, The status of the $\mathbf {P}$ versus $\mathbf {NP}$ problem, Commun. ACM 52 (2009), no. 9, 78–86.
- 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), DOI 10.1007/s00037-004-0182-6
- Russell Impagliazzo and Avi Wigderson, $\textrm {P}=\textrm {BPP}$ if $\textrm {E}$ requires exponential circuits: derandomizing the XOR lemma, STOC ’97 (El Paso, TX), ACM, New York, 1999, pp. 220–229 (electronic). MR 1715634
- 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.
- Richard Lipton, Gödel’s Lost Letter and $\mathbf {P}\!=\!\mathbf {NP}$, blog entry, http://rjlipton. wordpress.com/the-gdel-letter .
- Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285 (95f:68082)
- 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)
- 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.
- 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)
- Arne Storjohann, Algorithms for matrix canonical forms, doctoral dissertation, Swiss Federal Institute of Technology, Zurich, 2000.
- 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)
- 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
Journal:
Bull. Amer. Math. Soc.
50 (2013), 481-487
DOI:
https://doi.org/10.1090/S0273-0979-2013-01407-1
Published electronically:
April 5, 2013
Additional Notes:
Partially supported by NSF MCS grant DMS-0915245, DOE ASCR grant DE-SC0002505, and Sandia National Laboratories.
Review copyright:
© Copyright 2013
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
