SIGACT News, Volume 35, 2004

Volume 35, Number 1, March 2004

• William I. Gasarch:
  The book review column. 3-4
  
• Dan A. Simovici:
  Review of "The classical decision problem" by Egon Börger, Erich Grädel and Yuri Gurevich. Springer-Verlag 1997. 4-7
  
• Lawrence S. Moss, Hans-Jörg Tiede:
  Review of "Automata theory and its applications" by Bakhadyr Khoussainov and Anil Nerode. Birkhäuser Boston, Inc. 2001.: and "Automata, logics, and infinite games" by E.Grädel, W. Thomas, and T. Wilke. Springer-Verlag. 8-12
  
• Jean Berstel:
  Review of "Automatic sequences: theory, applications, generalizations" by Jean-Paul Allouche and Jeffrey Shallit. Cambridge University Press. 12-16
  

• Lane A. Hemaspaandra:
  SIGACT news complexity theory column 43. 22-35
  
• Marek Chrobak:
  SIGACT news online algorithms column 2. 38-48
  

• Rocky Ross:
  Stability and theory. 49-51
  
• Leona F. Fass:
  Language, mathematics and other dangerous things. 74-79
  
• Christopher Frost, Michael Peck, David Evans:
  Pancakes, puzzles, and polynomials: cracking the Cracker Barrel. 80-84
  

Volume 35, Number 2, June 2004

• William I. Gasarch:
  The book review column. 3-4
  
• Sabina Petride:
  Review of "Concurrent and real-time systems: the CSP approach" by Steve Schneider. Wiley 1999. 4-12
  
• Robert McNaughton:
  Review of "Introduction to languages, machines and logic: computable languages, abstract machines and formal logic" by Alan P. Parkes. Springer-Verlag 2002. 13-14
  
• Pavol Návrat:
  Review of "Algorithm design: foundations, analysis and internet examples" by Michael T. Goodrich and Roberto Tamassia. John Wiley & Sons, Inc. 2001. 14-16
  
• Lance Fortnow:
  Review of "Theory of semi-feasible algorithms" by Lane Hemaspaandra and Leen Torenvliet. Springer. 16-18
  

• Andris Ambainis:
  Quantum search algorithms. 22-35
  

• Marcos Kawazoe Aguilera:
  A pleasant stroll through the land of infinitely many creatures. 36-59
  

• Jittat Fakcharoenphol, Satish Rao, Kunal Talwar:
  Approximating metrics by tree metrics. 60-70
  

• Joseph O'Rourke:
  Computational geometry column 45. 71-73
  

• Marek Chrobak:
  A princess swimming in the fog looking for a monster cow. 74-78
  

• Rockey Ross:
  Mental models. 79-82
  

• Amir M. Ben-Amram:
  A complexity-theoretic proof of a Recursion-Theoretic Theorem. 111-112
  

Volume 35, Number 3, September 2004

• William I. Gasarch:
  Review of "Handbook of Graph Theory edited by Gross and Yellen." CRC, 2004. 5-8
  
• Wenzhong Zhao:
  Review of "Reasoning about Uncertainty by Joseph Y. Halpern." The MIT Press, 2003. 8-12
  
• Luc T. Wille:
  Review of "Learning Kernel Classifiers: Theory and Algorithms by Ralf Herbrich." MIT Press, Cambridge, Mass., 2002. ISBN 026208306X, 384 pages; and Review of "Learning with Kernels: Support Vector Machines, Regularization Optimization and Beyond by Bernhard Scholkopf and Alexander J. Smola." IT Press, Cambridge, Mass., 2002, ISBN 0262194759, 644 pages. 13-17
  
• Carlos Oliveira:
  Review of "Essentials of Constraint Programming by T. Fruhwirth and S. Abdennadher." Springer-Verlag. 17-20
  

• Venkatesan Guruswami:
  Guest column: error-correcting codes and expander graphs. 25-41
  

• Joseph O'Rourke:
  Computational geometry column 46. 42-45
  

• Sergio Rajsbaum:
  ACM SIGACT news distributed computing column 15. 46-57
  

• Marek Chrobak:
  SIGACT news online algorithms column 4. 58-66
  

• Rocky Ross:
  Chicago blues. 69-71
  

• Antti Ylikoski:
  Some simple but interesting results concerning the P ?= NP Problem. 94-97
  
• Dafa Li:
  The equality axioms are not independent. 98-101
  
• S. O. Shilova, Nikolay V. Shilov:
  Etude on theme of Dijkstra. 102-108
  

Volume 35, Number 4, December 2004

• William I. Gasarch:
  The book review column. 4-5
  
• R. Gregory Taylor:
  Review of "Boolean Functions and Computation Models by Peter Clote and Evangelos Kranakis", Springer-Verlag, 2002. 5-11
  
• Carlos A. S. Oliveira:
  Review of "Selected Papers in Discrete Mathematics by D. Knuth", CSLI (Center for the Study of Language and Information Publication) paperback, $72.00. 11-14
  
• Carlos A. S. Oliveira:
  Review of "Linear Optimization and Extensions -- Problems and Solutions by Dimitris Alevas and Manfred Padberg", Springer-Verlag, 450 pages, $54.95. 15-18
  
• William Fahle:
  Review of "Introduction to the Design and Analysis of Algorithms by Ananay Levitin", Addison-Wesley. 18-19
  

• Bruno Codenotti, Sriram V. Pemmaraju, Kasturi R. Varadarajan:
  The computation of market equilibria. 23-37
  

• Sergio Rajsbaum:
  ACM SIGACT news distributed computing column 16. 38
  

• Sergio Rajsbaum:
  Larry Stockmeyer: 1948-2004. 39
  
• Michael Elkin:
  Distributed approximation: a survey. 40-57
  

• Marek Chrobak, Elias Koutsoupias:
  Coordination mechanisms for congestion games. 58-71
  

• Riccardo Pucella:
  Specifying confidentiality. 72-83
  
• Pim van den Broek, Joost Noppen:
  Comparison of two approaches to dynamic programming. 111-116
  
• Harry B. Coonce:
  Computer science and the mathematics genealogy project. 117
  
• S. O. Shilova, Nikolay V. Shilov:
  Addendum to Etude on theme of Dijkstra. 118