SIGACT News, Volume 37, 2006

Volume 37, Number 1, March 2006

• William I. Gasarch:
  The book review column. 9-11
  
• Jonathan Katz:
  Review of "A Computational Introduction to Number Theory and Algebra by Victor Shoup", Cambridge University Press, 2005. 12-13
  
• Jonathan Katz:
  Review of "Primality Testing in Polynomial Time by Martin Dietzfelbinger", Springer-Verlag, 2004. 14-15
  
• William M. Springer II:
  Review of "Introduction to Coding Theory by Juergen Bierbrauer", Chapman and Hall/CRC, 2005, ISBN 1584884215. 16-18
  
• Adam Bender:
  Review of "Codes: The Guide to Secrecy from Ancient to Modern Times by Richard A. Mollin", Chapman & Hall/CRC, 2005. 18-21
  
• Carlos A. S. Oliveira:
  Review of "Computational Complexity: a Quantitative Perspective by Marius Zimand", Elsevier, ISBN 0444828419. 21-25
  
• Maulik A. Dave:
  Review of "Secure Communicating Systems: Design, analysis, and implementation by Michael R A Huth", Cambridge University Press, 2001. 26-27
  
• Pierre Lescanne:
  Review of "Alfred Tarski: Life and Logic by Anita Burdman Feferman and Solomon Feferman", Cambridge University Press 2004. 27-28
  

• Dean Kelley:
  Technical report column. 29-32
  

• Chaitanya Swamy, David B. Shmoys:
  Approximation algorithms for 2-stage stochastic optimization problems. 33-46
  

• Piotr Faliszewski, Lane A. Hemaspaandra:
  Open questions in the theory of semifeasible computation. 47-65
  

• Paulo Veríssimo:
  Travelling through wormholes: a new look at distributed systems models. 66-81
  

• Marek Chrobak:
  2005: an offline persepctive. 82-98
  

Volume 37, Number 2, June 2006

• William I. Gasarch:
  The book review column. 10-12
  
• Varsha Dani:
  Review of "Fair Division and Collective Welfare by Hervé Moulin", MIT Press, 2003. 12-17
  
• William Schmeister:
  Review of "Algorithms: Sequential, Parallel, and Distributed by Kenneth A. Berman and Jerome L. Paul", Thomson Course Technology, 2005. 17-22
  
• Anthony Widjaja To:
  Review of "Algebraic Complexity Theory by Peter Bürgisser, Michael Clausen and Amin Shokrollahi", Springer 1997. 22-27
  

• Dean Kelley:
  Technical report column. 28-30
  

• Lane A. Hemaspaandra:
  SIGACT news complexity theory column 51. 31-46
  

• Joseph O'Rourke:
  Computational geometry column 47. 47-49
  

• Sergio Rajsbaum:
  ACM SIGACT news distributed computing column 22. 50-56
  

• Alexander Kurz:
  Coalgebras and their logics. 57-77
  
• Riccardo Pucella:
  SIGACT news logic column 15. 57
  

Volume 37, Number 3, September 2006

• William I. Gasarch:
  The book review column. 14-17
  
• William I. Gasarch:
  A joint review of "Reality Conditions: Short Mathematical Fiction, by Alex Kasman", MAA 2005;"Numb3rs, TV show. CBS", Free. Currently running Fridays at 10: 00PM; "Mathematical Apocryphia: Stories and Annecdotes of Mathematicians and the Mathematical by Steven Kranz", MAA, 2002; "Mathematical Apocryphia Redux: More Stories and Annecdotes of Mathematicians and the Mathematical by Steven Kranz", MAA, 1999. 17-19
  
• Brian Blank:
  A Joint Review of "A History of Pi, by Petr Beckmann", St. Martins's Press, 1976, Barnes and Noble Books, 1989; "The Joy of Pi, by David Blatner", Walker & Co., 1997; "The Nothing That Is, by Robert Kaplan", Oxford University Press, 1999; "e: The Story of a Number, by Eli Maor", Princeton University Press, 1998; "An Imaginary Tale, by Paul Nahin", Princeton University Press, 1998; "Zero: The Biography of a Dangerous Idea, by Charles Seife", Viking Press, 2000. 19-26
  
• William I. Gasarch, Alexander Kruskal, Justin Kruskal, Rebecca Kruskal:
  Review of "The Square Root of 2: A Dialogue Concerning a Number and a Sequence by David Flannery", Copernicus Books, 2006. 27-32
  

• Dean Kelley:
  Technical report column. 33-35
  

• Lane A. Hemaspaandra:
  SIGACT news complexity theory column 52. 36-54
  

• Joseph O'Rourke:
  Computational geometry column 48. 55-57
  

• Idit Keidar, Assaf Schuster:
  Want scalable computing?: speculate! 59-66
  

• Ran Canetti:
  Security and composition of cryptographic protocols: a tutorial (part I). 67-92
  

• Karl Crary, Robert Harper:
  Higher-order abstract syntax: setting the record straight. 93-96
  

• Vladik Kreinovich, Max Shpak:
  Aggregability is NP-hard. 97-104
  

Volume 37, Number 4, December 2006

• Pavel Pudlák:
  Gödel and computations: a 100th anniversary retrospective. 13-21
  
• Joan Feigenbaum, Michael Mitzenmacher:
  Towards a theory of networked computation. 22-26
  

• William I. Gasarch:
  The book review column. 27-29
  
• Mats Kindahl:
  Review of "Types and Programming Languages by Benjamin C. Pierce", MIT Press, 2002. 29-34
  
• Maulik A. Dave:
  Review of "Information Theory, Inference, and Learning Algorithms by David J. C. MacKay", Cambridge University Press, 2003. 34-36
  
• Maulik A. Dave:
  Review of "Verification of Reactive Systems: Formal Methods and Algorithms by Klaus Schneider", Springer-Verlag Berlin Heidelberg, 2004. 36-37
  
• James Law:
  Review of "Algorithmic Learning in a Random World by Vovk, Gammerman and Shafer", Springer, 2005, ISBN: 0-387-00152-2. 38-40
  
• Aravind Srinivasan:
  Review of "The Random Projection Method by Santosh Vempala". 41-43
  

• Dean Kelley:
  Technical report column. 44-46
  

• Lane A. Hemaspaandra:
  SIGACT news complexity theory column 53. 47-55
  

• Jan Van den Bussche:
  Database theory column: report on PODS 2006. 56-57
  

• Sergio Rajsbaum:
  ACM SIGACT news distributed computing column 24. 58-84
  

• Hubie Chen:
  A rendezvous of logic, complexity, and algebra. 85-114
  

• Marek Chrobak, Claire Kenyon-Mathieu:
  SIGACT news online algorithms column 10: competitiveness via doubling. 115-126