SIGACT News, Volume 37, 2006

Volume 37, Number 1, March 2006

Book review

• 
  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

Technical report column

• 
  Dean F. Kelley:
  Technical report column. 29-32

Algorithms

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

SIGACT news complexity theory column 50

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

ACM SIGACT news distributed computing column 21

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

SIGACT news online algorithms column 9

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

Volume 37, Number 2, June 2006

Book reviews

• 
  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

Technical report column

• 
  Dean F. Kelley:
  Technical report column. 28-30

Complexity theory

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

Computational geometry

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

Distributed computing

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

Logic

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

Volume 37, Number 3, September 2006

Book reviews

• 
  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

Technical report column

• 
  Dean F. Kelley:
  Technical report column. 33-35

Complexity theory

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

Computational geometry

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

ACM SIGACT News distributed computing column 23

• 
  Idit Keidar, Assaf Schuster:
  Want scalable computing?: speculate! 59-66
• 
  Ran Canetti:
  Security and composition of cryptographic protocols: a tutorial (part I). 67-92

Logic: SIGACT news logic column 16

• 
  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

Special feature

• 
  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

Book reviews

• 
  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

Technical report column

• 
  Dean F. Kelley:
  Technical report column. 44-46

Complexity theory

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

Database

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

Distributed computing

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

Logic

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

Online algorithms

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