Table of contents for issues of ACM SIGACT News

Last update: Thu Nov 3 12:52:21 MDT 2022                Valid HTML 3.2!

Volume 1, Number 1, 1969
Volume 1, Number 3, 1969
Volume 2, Number 4, 1970
Volume 2, Number 6, 1970
Volume 2, Number 7, 1970
Volume 3, Number 8, January, 1971
Volume 3, Number 9, April, 1971
Volume 3, Number 12, 1971
Volume 3, Number 13, December, 1971
Volume 4, Number 14, January, 1972
Volume 5, Number ??, 1973
Volume 5, Number 1, January, 1973
Volume 5, Number 2, April, 1973
Volume 5, Number 3, July, 1973
Volume 5, Number 4, October, 1973
Volume 6, Number 1, January, 1974
Volume 6, Number 2, April, 1974
Volume 6, Number 3, July, 1974
Volume 6, Number 4, October, 1974
Volume 7, Number 1, January, 1975
Volume 7, Number 2, April, 1975
Volume 7, Number 3, Summer, 1975
Volume 7, Number 4, November, 1975
Volume 8, Number 1, January, 1976
Volume 8, Number 2, April / June, 1976
Volume 8, Number 3, July, 1976
Volume 8, Number 4, October, 1976
Volume 9, Number ??, 1977
Volume 9, Number 1, January, 1977
Volume 9, Number 2, Summer, 1977
Volume 9, Number 3, Fall, 1977
Volume 9, Number 4, Winter, 1978
Volume 10, Number 1, Spring, 1978
Volume 10, Number 2, Summer, 1978
Volume 10, Number 3, Winter, 1979
Volume 11, Number 1, Summer, 1979
Volume 11, Number 2, Fall, 1979
Volume 12, Number 1, Winter--Spring, 1980
Volume 12, Number 3, Fall, 1980
Volume 13, Number 1, Winter, 1981
Volume 13, Number 2, Spring--Summer, 1981
Volume 14, Number 1, Winter, 1982
Volume 14, Number 2, Spring, 1982
Volume 14, Number 3, Summer, 1982
Volume 14, Number 4, Fall--Winter, 1982
Volume 15, Number 1, Winter--Spring, 1983
Volume 15, Number 2, Spring--Summer, 1983
Volume 15, Number 3, Summer--Fall, 1983
Volume 15, Number 4, Winter--Spring, 1984
Volume 16, Number 1, Winter--Spring, 1984
Volume 16, Number 2, Summer, 1984
Volume 16, Number 3, Fall, 1984
Volume 16, Number 4, April, 1985
Volume 17, Number 1, June, 1985
Volume 17, Number 2, September, 1985
Volume 17, Number 3, Winter, 1986
Volume 17, Number 4, Spring, 1986
Volume 18, Number 1, Summer, 1986
Volume 18, Number 2, September / March, 1986--1987
Volume 18, Number 3, April, 1987
Volume 18, Number 4, Summer, 1987
Volume 19, Number 1, Fall, 1987
Volume 19, Number 2, 1988
Volume 19, Number 3--4, Fall, 1988
Volume 20, Number ??, 1988
Volume 20:4, Number ??, Fall, 1989
Volume 20, Number ??, 1989
Volume 20, Number 1, Winter, 1989
Volume 20, Number 2, March, 1989
Volume 20, Number 3, July, 1989
Volume 20, Number 4, November, 1989
Volume 21, Number 1, January, 1990
Volume 21, Number 2, Spring, 1990
Volume 21, Number 3, Summer, 1990
Volume 21, Number 4, Fall, 1990
Volume 22, Number 1, Winter, 1991
Volume 22, Number 2, Spring, 1991
Volume 22, Number 3, Summer, 1991
Volume 22, Number 4, Fall, 1991
Volume ??, Number ??, 1991
Volume 23, Number ??, 1992
Volume 23, Number 1, Winter, 1992
Volume 23, Number 2, Spring, 1992
Volume 23, Number 3, Summer, 1992
Volume 23, Number 4, Fall, 1992
Volume 24, Number 1, Winter, 1993
Volume 24, Number 2, Spring, 1993
Volume 24, Number 3, October, 1993
Volume 24, Number 4, December, 1993
Volume 25, Number 1, March, 1994
Volume 25, Number 2, June, 1994
Volume 25, Number 3, September, 1994
Volume 25, Number 4, December, 1994
Volume 26, Number 1, March, 1995
Volume 26, Number 2, June, 1995
Volume 26, Number 3, September, 1995
Volume 26, Number 4, December, 1995
Volume 27, Number 1, March, 1996
Volume 27, Number 2, June, 1996
Volume 27, Number 3, September, 1996
Volume 27, Number 4, December, 1996
Volume 28, Number 1, March, 1997
Volume 28, Number 2, June, 1997
Volume 28, Number 3, September, 1997
Volume 28, Number 4, December, 1997
Volume 29, Number 3, September, 1998
Volume 29, Number 1, March, 1998
Volume 29, Number 3, September, 1998
Volume 29, Number 2, June, 1998
Volume 29, Number 3, September, 1998
Volume 29, Number 4, December, 1998
Volume 29, Number 1, March, 1998
Volume 29, Number 2, June, 1998
Volume 29, Number 3, September, 1998
Volume 29, Number 4, December, 1998
Volume 30, Number 1, March, 1999
Volume 29, Number 4, December, 1998
Volume 29, Number 2, June, 1998
Volume 29, Number 3, September, 1998
Volume 29, Number 4, December, 1998
Volume 29, Number 3, September, 1998
Volume 29, Number 2, June, 1998
Volume 29, Number 1, March, 1998
Volume 29, Number 4, December, 1998
Volume 29, Number 3, September, 1998
Volume 30, Number 1, March, 1999
Volume 29, Number 4, December, 1998
Volume 29, Number 2, June, 1998
Volume 29, Number 3, September, 1998
Volume 29, Number 1, March, 1998
Volume 30, Number 1, March, 1999
Volume 29, Number 1, March, 1998
Volume 29, Number 4, December, 1998
Volume 29, Number 3, September, 1998
Volume 29, Number 2, June, 1998
Volume 29, Number 4, December, 1998
Volume 29, Number 1, March, 1998
Volume 29, Number 2, June, 1998
Volume 29, Number 3, September, 1998
Volume 29, Number 4, December, 1998
Volume 30, Number 1, March, 1999
Volume 29, Number 2, June, 1998
Volume 29, Number 4, December, 1998
Volume 30, Number 1, March, 1999
Volume 29, Number 3, September, 1998
Volume 29, Number 2, June, 1998
Volume 30, Number 1, March, 1999
Volume 30, Number 2, June, 1999
Volume 30, Number 3, September, 1999
Volume 30, Number 4, December, 1999
Volume 31, Number 1, March, 2000
Volume 31, Number 2, June 1, 2000
Volume 31, Number 3, September, 2000
Volume 31, Number 4, December, 2000
Volume 32, Number 1, March, 2001
Volume 32, Number 2, June, 2001
Volume 32, Number 3, September 1, 2001
Volume 32, Number 4, December, 2001
Volume 33, Number 1, March, 2002
Volume 33, Number 2, June, 2002
Volume 33, Number 3, September, 2002
Volume 33, Number 4, December, 2002
Volume 34, Number 1, March, 2003
Volume 34, Number 2, June, 2003
Volume 34, Number 3, September, 2003
Volume 34, Number 4, December, 2003
Volume 35, Number 1, March, 2004
Volume 35, Number 2, June, 2004
Volume 35, Number 3, September, 2004
Volume 35, Number 4, December, 2004
Volume 36, Number 1, March, 2005
Volume 36, Number 2, June, 2005
Volume 36, Number 3, September, 2005
Volume 36, Number 4, December, 2005
Volume 37, Number 1, March, 2006
Volume 37, Number 2, June, 2006
Volume 37, Number 3, September, 2006
Volume 37, Number 4, December, 2006
Volume 38, Number 1, March, 2007
Volume 38, Number 2, June, 2007
Volume 38, Number 3, September, 2007
Volume 38, Number 4, December, 2007
Volume 39, Number 1, March, 2008
Volume 39, Number 2, June, 2008
Volume 39, Number 3, September, 2008
Volume 39, Number 4, December, 2008
Volume 40, Number 1, March, 2009
Volume 40, Number 2, June, 2009
Volume 40, Number 3, September, 2009
Volume 40, Number 4, December, 2009
Volume 41, Number 1, March, 2010
Volume 41, Number 2, June, 2010
Volume 41, Number 3, September, 2010
Volume 41, Number 4, December, 2010
Volume 42, Number 1, March, 2011
Volume 42, Number 2, June, 2011
Volume 42, Number 3, September, 2011
Volume 42, Number 4, December, 2011
Volume 43, Number 1, March, 2012
Volume 43, Number 2, June, 2012
Volume 43, Number 3, September, 2012
Volume 43, Number 4, December, 2012
Volume 44, Number 1, March, 2013
Volume 44, Number 2, June, 2013
Volume 44, Number 3, September, 2013
Volume 44, Number 4, December, 2013
Volume 45, Number 1, March, 2014
Volume 45, Number 2, June, 2014
Volume 45, Number 3, September, 2014
Volume 45, Number 4, December, 2014
Volume 46, Number 1, March, 2015
Volume 46, Number 2, June, 2015
Volume 46, Number 3, September, 2015
Volume 46, Number 4, December, 2015
Volume 47, Number 1, March, 2016
Volume 47, Number 2, June, 2016
Volume 47, Number 3, September, 2016
Volume 47, Number 4, December, 2016
Volume 48, Number 1, March, 2017
Volume 48, Number 2, June, 2017
Volume 48, Number 3, September, 2017
Volume 48, Number 4, December, 2017
Volume 49, Number 1, March, 2018
Volume 49, Number 2, June, 2018
Volume 49, Number 3, September, 2018
Volume 49, Number 4, December, 2018
Volume 50, Number 1, March, 2019
Volume 50, Number 2, June, 2019
Volume 50, Number 3, September, 2019
Volume 50, Number 4, December, 2019
Volume 51, Number 1, March, 2020
Volume 51, Number 2, June, 2020
Volume 51, Number 3, September, 2020
Volume 51, Number 4, December, 2020
Volume 52, Number 1, March, 2021
Volume 52, Number 2, June, 2021
Volume 52, Number 3, September, 2021
Volume 52, Number 4, December, 2021
Volume 53, Number 1, March, 2022
Volume 27, Number 6, June, 1984
Volume 27, Number 4, April, 1984
Volume 20, Number 1, February, 1991
Volume 3, Number 2, 1974
Volume 163, Number 1, October 15, 2004


ACM SIGACT News
Volume 1, Number 1, 1969

                   D. E. Muller   Universal Boolean functions  . . . . . . 8--11

ACM SIGACT News
Volume 1, Number 3, 1969

                Dennis F. Cudia   The degree diagram of undecidable
                                  problems of formal grammars  . . . . . . 7--8


ACM SIGACT News
Volume 2, Number 4, 1970

                 M. Fischer and   
                   A. Meyer and   
                  P. O'Neil and   
                    M. Paterson   A note on independence of a
                                  regularity-preserving operator . . . . . 3--7
                         A. Paz   Events which are not representable by a
                                  probabilistic automaton  . . . . . . . . 8--11
                  G. J. Chaitin   To a Mathematical Definition of ``Life'' 12--18
             Sandra E. Hutchins   Stochastic sources for context-free
                                  languages  . . . . . . . . . . . . . . . 19--19

ACM SIGACT News
Volume 2, Number 6, 1970

              Clarence A. Ellis   Non-context-free probabilistic languages 9--14
            Edward L. Robertson   A corrected definition of ``local
                                  speed-up'' . . . . . . . . . . . . . . . 15--16

ACM SIGACT News
Volume 2, Number 7, 1970

                    David Pager   A solution to an open problem by Knuth   9--10
           Stephen D. Isard and   
               Arnold M. Zwicky   Three open questions in the theory of
                                  one-symbol Smullyan systems  . . . . . . 11--19


ACM SIGACT News
Volume 3, Number 8, January, 1971

                  Ivan M. Havel   Weak complexity measures . . . . . . . . 21--30

ACM SIGACT News
Volume 3, Number 9, April, 1971

               H. W. Buttelmann   Syntax-semantics systems as structure
                                  manipulation systems: phrase structure
                                  grammars and generalized finite automata 10--10
                  G. J. Chaitin   Computational complexity and Gödel's
                                  incompleteness theorem . . . . . . . . . 11--12

ACM SIGACT News
Volume 3, Number 12, 1971

                 Giuseppe Longo   Axioms for time dependence of resource
                                  consumption in computing recursive
                                  functions  . . . . . . . . . . . . . . . 14--24

ACM SIGACT News
Volume 3, Number 13, December, 1971

                      L. Reeker   A note on a Badly Nondeterministic
                                  automaton  . . . . . . . . . . . . . . . 22--24


ACM SIGACT News
Volume 4, Number 14, January, 1972

                   Robin Milner   Implementation and applications of
                                  Scott's logic for computable functions   1--6
                Rod M. Burstall   An algebraic description of programs
                                  with assertions, verification and
                                  simulation . . . . . . . . . . . . . . . 7--14
                 C. David Allen   Derivation of axiomatic definitions of
                                  programming languages from algorithmic
                                  definitions  . . . . . . . . . . . . . . 15--26
                Zohar Manna and   
               Stephen Ness and   
                 Jean Vuillemin   Inductive methods for proving properties
                                  of programs  . . . . . . . . . . . . . . 27--50
                 E. A. Ashcroft   Program correctness methods and language
                                  definition . . . . . . . . . . . . . . . 51--57
               J. M. Cadiou and   
                    Zohar Manna   Recursive definitions of partial
                                  functions and their computations . . . . 58--65
                 T. E. Hull and   
              W. H. Enright and   
                 A. E. Sedgwick   The correctness of numerical algorithms  66--73
            Michael S. Paterson   Decision problems in computational
                                  models . . . . . . . . . . . . . . . . . 74--82
         Stephen J. Garland and   
               David C. Luckham   Translating recursion schemes into
                                  program schemes  . . . . . . . . . . . . 83--96
               H. R. Strong and   
                   S. A. Walker   Properties preserved under recursion
                                  removal  . . . . . . . . . . . . . . . . 97--103
             Michael J. Fischer   Lambda calculus schemata . . . . . . . . 104--109
                Clement McGowan   The Contour Model Lambda Calculus
                                  Machine  . . . . . . . . . . . . . . . . 110--115
              Raymond E. Miller   A boundary between decidability and
                                  undecidability for parallel program
                                  schemata (extended abstract) . . . . . . 116--120
                Ralph L. London   Correctness of a compiler for a Lisp
                                  subset . . . . . . . . . . . . . . . . . 121--127
                   Peter Wegner   Operational semantics of programming
                                  languages  . . . . . . . . . . . . . . . 128--141
                 John A. N. Lee   The definition and validation of the
                                  radix sorting technique  . . . . . . . . 142--149
                    C. B. Jones   Formal development of correct
                                  algorithms: an example based on Earley's
                                  recogniser . . . . . . . . . . . . . . . 150--169
                Daniel M. Berry   The equivalence of models of tasking . . 170--190
             Clement L. McGowan   The ``most recent'' error: Its causes
                                  and correction . . . . . . . . . . . . . 191--202
                Michel Sintzoff   Calculating properties of programs by
                                  valuations on specific models  . . . . . 203--207
        T. E. Cheatham, Jr. and   
                   Ben Wegbreit   On a laboratory for the study of
                                  automating programming . . . . . . . . . 208--211


ACM SIGACT News
Volume 5, Number ??, 1973

                A. L. Rosenburg   On the Time Required to Recognize
                                  Properties of Graphs: a Problem  . . . . 15--16

ACM SIGACT News
Volume 5, Number 1, January, 1973

                David B. Benson   Another comment on the null word
                                  definition problem . . . . . . . . . . . 14--17
              SIGACT News Staff   Recent technical reports . . . . . . . . 21--24

ACM SIGACT News
Volume 5, Number 2, April, 1973

                   M. Bauer and   
                   D. Brand and   
                 M. Fischer and   
                   A. Meyer and   
                    M. Paterson   A note on disjunctive form tautologies   17--20
                  G. J. Chaitin   Some philosophical implications of
                                  information-theoretic computational
                                  complexity . . . . . . . . . . . . . . . 21--23
                  G. J. Chaitin   Some abstracts from The Computer Science
                                  Conference . . . . . . . . . . . . . . . 24--25
              SIGACT News Staff   Recent technical reports . . . . . . . . 26--27

ACM SIGACT News
Volume 5, Number 3, July, 1973

                  L. Stockmeyer   Planar $3$-colorability is NP-complete   19--25
               Larry Stockmeyer   Planar $3$-colorability is polynomial
                                  complete . . . . . . . . . . . . . . . . 19--25
                  John Lind and   
                Albert R. Meyer   A characterization of log-space
                                  computable functions . . . . . . . . . . 26--29
                       G. Ricci   Some further comments about nothing  . . 29--30
              SIGACT News Staff   Recent technical reports . . . . . . . . 31--32

ACM SIGACT News
Volume 5, Number 4, October, 1973

                Louise H. Jones   Microprogramming: an opportunity for
                                  SIGACT . . . . . . . . . . . . . . . . . 9--11
                David B. Benson   An alternate proof of Aho & Ullman's
                                  LR(k) viable prefix theorem  . . . . . . 11--14
            Arnold L. Rosenberg   On the Time Required to Recognize
                                  Properties of Graphs: a Problem  . . . . 15--16


ACM SIGACT News
Volume 6, Number 1, January, 1974

                Donald E. Knuth   A terminological proposal  . . . . . . . 12--18
                      Zvi Galil   On some direct encodings of
                                  nondeterministic Turing machines
                                  operating in polynomial time into
                                  $p$-complete problems  . . . . . . . . . 19--24
               Joel I. Seiferas   A note on prefixes of regular languages  25--29
          Richard J. Lipton and   
                Lawrence Snyder   On the Aanderaa--Rosenberg Conjecture    30--31
                   Peter Wegner   Modification of Aho and Ullman's
                                  correctness proof of Warshall's
                                  algorithm  . . . . . . . . . . . . . . . 32--35
              SIGACT News Staff   Technical reports  . . . . . . . . . . . 35--35

ACM SIGACT News
Volume 6, Number 2, April, 1974

                Donald E. Knuth   Postscript about NP-hard problems  . . . 15--16
                S. Rao Kosaraju   Regularity preserving functions  . . . . 16--17
                  Ivan M. Havel   Automata theory motivated by problem
                                  solving  . . . . . . . . . . . . . . . . 18--23
             Victor L. Bennison   Saving tapes in the simulation of
                                  multihead Turing machines  . . . . . . . 23--26
              SIGACT News Staff   Recent technical reports . . . . . . . . 57--60

ACM SIGACT News
Volume 6, Number 3, July, 1974

              SIGACT News Staff   A recent technical report  . . . . . . . 5--5
               Stephen Cook and   
                 Robert Reckhow   Corrections for ``On the lengths of
                                  proofs in the propositional calculus
                                  preliminary version''  . . . . . . . . . 15--22
                S. Rao Kosaraju   Correction to ``Regularity preserving
                                  functions'' (ACM SIGACT News \bf 6
                                  (1974), no. 2, 16--17) . . . . . . . . . 22--22
              Carl H. Smith and   
                 J. van Leeuwen   Microprogrammed random access stored
                                  program machines . . . . . . . . . . . . 23--32
              SIGACT News Staff   Recent technical reports . . . . . . . . 33--34

ACM SIGACT News
Volume 6, Number 4, October, 1974

                Jan van Leeuwen   A forgotten connection between
                                  tag-systems and parallel-rewriting . . . 19--20
                 G. Germano and   
          A. Maggiolo-Schettini   Loops in Algol 60 and in category theory 21--23
              David R. Cheriton   An extension to on-line multiplication
                                  lower bound results  . . . . . . . . . . 24--31
           Robert Constable and   
                     David Park   Special issue on semantics and program
                                  schemas: SIAM Journal on Computing . . . 32--32


ACM SIGACT News
Volume 7, Number 1, January, 1975

              Richard E. Ladner   The circuit value problem is log space
                                  complete for P . . . . . . . . . . . . . 18--20
                 Y. Edmund Lien   Periodic properties of strings . . . . . 21--25
           M. S. Krishnamoorthy   An NP-hard problem in bipartite graphs   26--26

ACM SIGACT News
Volume 7, Number 2, April, 1975

                    Peter Kugel   Trees  . . . . . . . . . . . . . . . . . 19--19
              SIGACT News Staff   Technical reports  . . . . . . . . . . . 20--24

ACM SIGACT News
Volume 7, Number 3, Summer, 1975

                 Barry K. Rosen   A Church--Rosser Theorem for Graph
                                  Grammars . . . . . . . . . . . . . . . . 26--31
             Lieuwe de Jong and   
                Jan van Leeuwen   An improved bound on the number of
                                  multiplications and divisions necessary
                                  to evaluate a polynomial and all its
                                  derivatives  . . . . . . . . . . . . . . 32--34
              SIGACT News Staff   Recent technical reports . . . . . . . . 35--39

ACM SIGACT News
Volume 7, Number 4, November, 1975

           Richard E. Schneider   Automata theory: what is it used for?    8--11
          Richard J. Lipton and   
                    Nancy Lynch   A quantifier characterization for
                                  nondeterministic log space . . . . . . . 24--25
                      Zvi Galil   On converting on-line algorithms into
                                  real-time and on real-time algorithms
                                  for string-matching and palindrome
                                  recognition  . . . . . . . . . . . . . . 26--30
                 Helmut Alt and   
                  Kurt Mehlhorn   A language over a one symbol alphabet
                                  requiring only $ O(\log \log n) $ space  31--33
                Harold N. Gabow   How to gracefully number certain
                                  symmetric trees  . . . . . . . . . . . . 33--36


ACM SIGACT News
Volume 8, Number 1, January, 1976

                    Peter Kugel   On uninteresting theorems  . . . . . . . 27--29
                   Dana Angluin   The Four Russians' Algorithm for Boolean
                                  matrix multiplication is optimal in its
                                  class  . . . . . . . . . . . . . . . . . 29--33
                   Istvan Simon   Two results on polynomial-time
                                  reducibilities . . . . . . . . . . . . . 33--37
                  Arthur Pyster   A language construct for ``Dovetailing'' 38--40
              SIGACT News Staff   Recent technical reports . . . . . . . . 41--49

ACM SIGACT News
Volume 8, Number 2, April / June, 1976

                Donald E. Knuth   Big Omicron and big Omega and big Theta  18--24
                 Richard Hamlet   Application of ``DOVETAILING'' to
                                  program testing  . . . . . . . . . . . . 25--26
                    Peter Kugel   Digital to analog conversion: a
                                  speculation  . . . . . . . . . . . . . . 27--33
              SIGACT News Staff   Abstracts from the computer science
                                  conference . . . . . . . . . . . . . . . 34--37
              SIGACT News Staff   Recent technical reports . . . . . . . . 38--52

ACM SIGACT News
Volume 8, Number 3, July, 1976

                 Carroll Morgan   A prime decomposition result for
                                  parallel systems . . . . . . . . . . . . 14--20
     Mary-Claire van Leunen and   
                 Richard Lipton   How to have your abstract rejected . . . 21--24
                       G. Yuval   The geometric mean distance  . . . . . . 24--25
                    SIGACT News   Recent technical reports . . . . . . . . 26--36

ACM SIGACT News
Volume 8, Number 4, October, 1976

               Samuel Eilenberg   Book Review: \booktitleAlgebraic and
                                  Automata-Theoretic Properties of Formal
                                  Languages, by Seymour Ginsburg. North
                                  Holland, 1975  . . . . . . . . . . . . . 11--12
               J. Hartmanis and   
                 J. E. Hopcroft   Independence Results in Computer Science 13--24
                Jan van Leeuwen   A regularity condition for parallel
                                  rewriting systems  . . . . . . . . . . . 24--27
                Stephen A. Cook   A short proof of the pigeon hole
                                  principle using extended resolution  . . 28--32
              SIGACT News Staff   Recent technical reports . . . . . . . . 33--40


ACM SIGACT News
Volume 9, Number ??, 1977

                Donald E. Knuth   The Samson--Mueller Algorithm  . . . . . ??

ACM SIGACT News
Volume 9, Number 1, January, 1977

            John C. Cherniavsky   Book review department . . . . . . . . . 15--15
                   Gabor Herman   Book Review: \booktitleAutomata,
                                  Languages, Development, by A.
                                  Lindenmayer and G. Rozenberg. North
                                  Holland Publishing Co. 1976  . . . . . . 16--18
              SIGACT News Staff   Recent technical reports . . . . . . . . 19--34

ACM SIGACT News
Volume 9, Number 2, Summer, 1977

                Donald E. Knuth   The complexity of songs  . . . . . . . . 17--24
         Leslie M. Goldschlager   The monotone and planar circuit value
                                  problems are log space complete for P    25--29
          Dianne E. Britton and   
        Ralph B. McLaughlin and   
              Richard J. Orgass   A note concerning intermittent
                                  assertions . . . . . . . . . . . . . . . 30--35
                   Larry Carter   A four-gadget  . . . . . . . . . . . . . 36--36
              SIGACT News Staff   Recent technical reports . . . . . . . . 37--44

ACM SIGACT News
Volume 9, Number 3, Fall, 1977

                Larry H. Reeker   Book Review: \booktitlePrograms,
                                  Machines, and Computation: an
                                  Introduction to the Theory of Computing,
                                  by K. L. Clark and D. F. Cowell  . . . . 20--22
               Kellogg S. Booth   Boolean matrix multiplication using only
                                  $ O(n^{\log_2 7} \log n) $ bit
                                  operations . . . . . . . . . . . . . . . 23--23
           M. S. Krishnamoorthy   A note on ``Some simplified NP-complete
                                  graph problems'' . . . . . . . . . . . . 24--24
                 Barry K. Rosen   Arcs in graphs are NOT pairs of nodes    25--27
              SIGACT News Staff   Recent technical reports . . . . . . . . 28--32

ACM SIGACT News
Volume 9, Number 4, Winter, 1978

                 Harry R. Lewis   Book Review: \booktitleMariages stables
                                  et leurs relations avec d'autre
                                  probl\`emes combinatoires: introduction
                                  \`a l'analyze mathématique des
                                  algorithmes, by Donald E. Knuth. Les
                                  Presses de l'Université de Montréal  . . . 13--14
                  Y. Nisselbaum   On merging $N$ ordered elements with
                                  three elements . . . . . . . . . . . . . 14--16
                M. R. Garey and   
                  D. S. Johnson   A note on ``A note on 'Some simplified
                                  NP-complete graph problems'''  . . . . . 17--17
             R. K. Shyamasundar   A note on the transitive closure of a
                                  Boolean matrix . . . . . . . . . . . . . 18--21
              Howard P. Katseff   From the recursive function theory
                                  newsletter . . . . . . . . . . . . . . . 22--23
              SIGACT News Staff   Recent technical reports . . . . . . . . 24--28


ACM SIGACT News
Volume 10, Number 1, Spring, 1978

                Jan van Leeuwen   Evaluating a polynomial and its reverse  18--21
                      Zvi Galil   Killing two birds with one stone . . . . 22--24
     Marlene Jones Colbourn and   
            Charles J. Colbourn   Graph isomorphism and self-complementary
                                  graphs . . . . . . . . . . . . . . . . . 25--29
              Lawrence Yelowitz   Notes on ``A note on the transitive
                                  closure of a Boolean matrix''  . . . . . 30--30
             R. K. Shyamasundar   A note on the multiplication of $ 4
                                  \times 4 $ matrices  . . . . . . . . . . 31--32
              SIGACT News Staff   International Business Machines  . . . . 38--41

ACM SIGACT News
Volume 10, Number 2, Summer, 1978

             P. A. Subrahmanyam   Book Review: \booktitleLinguistic
                                  Structures Processing, by A. Zampolli.
                                  North Holland Publishing Company 1977    39--41
                 James E. Burns   Mutual exclusion with linear waiting
                                  using binary shared variables  . . . . . 42--47
                  Jeffrey Jaffe   A necessary and sufficient pumping lemma
                                  for regular languages  . . . . . . . . . 48--49
                   Dexter Kozen   A clique problem equivalent to graph
                                  isomorphism  . . . . . . . . . . . . . . 50--52
                   B. Litow and   
               I. H. Sudborough   On non-erasing oracle tapes in space
                                  bounded reducibility . . . . . . . . . . 53--57
            Jacques Vélu   Tests for primality under the Riemann
                                  hypothesis . . . . . . . . . . . . . . . 58--59
                    Derick Wood   One-sided height-balanced search trees   60--62

ACM SIGACT News
Volume 10, Number 3, Winter, 1979

                  A. K. Dewdney   Logic circuits in the plane: minimal
                                  crossovers . . . . . . . . . . . . . . . 38--48
       M. S. Krishnamoorthy and   
                Somenath Biswas   The Generalized Towers of Hanoi  . . . . 49--49
       M. S. Krishnamoorthy and   
                Somenath Biswas   Recent technical reports . . . . . . . . 50--94


ACM SIGACT News
Volume 11, Number 1, Summer, 1979

            John C. Cherniavsky   Book Review: \booktitleThe Theory of
                                  Computer Science: a Programming
                                  Approach, by J. M. Brady. Chapman and
                                  Hall . . . . . . . . . . . . . . . . . . 17--17
            John C. Cherniavsky   Book Review: \booktitleAutomated Theorem
                                  Proving: a Logical Basis, by D. W.
                                  Loveland. North-Holland Publishing Co.
                                  1977 . . . . . . . . . . . . . . . . . . 18--18
           Kenneth H. Derus and   
                 John C. Hansen   Logics of truth and disposition  . . . . 36--43
              SIGACT News Staff   Recent technical reports . . . . . . . . 44--80

ACM SIGACT News
Volume 11, Number 2, Fall, 1979

            John C. Cherniavsky   Book Review: \booktitleTORIX: a
                                  Programming System for Operations on
                                  Vectors and Matrices over Arbitrary
                                  Fields and of Variable Size, vol 1, by
                                  S. G. Van Der Meulen and M. Veldhorst.
                                  Mathematisch Centrum 1978  . . . . . . . 6--6
         Richard A. DeMillo and   
              Richard J. Lipton   Book Review: \booktitleProofs and
                                  Refutations: the Logic of Mathematical
                                  Discovery, by Imre Lakatos. Cambridge
                                  University Press 1976  . . . . . . . . . 7--9
              Allan Borodin and   
         Michael J. Fischer and   
       David G. Kirkpatrick and   
             Nancy A. Lynch and   
                   Martin Tompa   A time-space tradeoff for sorting and
                                  related non-oblivious computations . . . 24--24
                   H. Ehrig and   
             H. J. Kreowski and   
                    P. Padawitz   Algebraic implementation of abstract
                                  data types: an announcement  . . . . . . 25--29
           Kenneth H. Derus and   
                 John C. Hansen   Propositions with multiple dispositions
                                  and multiple truth values  . . . . . . . 30--35
          Jon Louis Bentley and   
                  James B. Saxe   Algorithms on Vector Sets  . . . . . . . 36--39
              SIGACT News Staff   Recent technical reports . . . . . . . . 40--57


ACM SIGACT News
Volume 12, Number 1, Winter--Spring, 1980

              SIGACT News Staff   Technical reports  . . . . . . . . . . . 2--135

ACM SIGACT News
Volume 12, Number 3, Fall, 1980

                    David Maier   Book Review: \booktitleIntroduction to
                                  Automata Theory, Languages and
                                  Computation, by John E. Hopcroft and
                                  Jeffrey D. Ullman. Addison-Wesley 1979   13--14
               John Cherniavsky   Book Reviews: \booktitleChecking
                                  Landau's ``Grundlagen'' in the Automath
                                  system, by L. S. Van Benthem Jutting.
                                  Mathematical Centre 1979:
                                  \booktitleFirst Order Dynamic Logic, by
                                  David Harel. Springer-Verlag 1979. And
                                  \booktitleA Programming Logic, by Robert
                                  L. Constable and Michael J. O'Donnell.
                                  Winthrop Publishers 1978 . . . . . . . . 14--16
          Jon Louis Bentley and   
             Dorothea Haken and   
                  James B. Saxe   A General Method For Solving
                                  Divide-and-conquer Recurrences . . . . . 36--44
                 H. Gaifman and   
                      E. Shamir   Roots of the hardest context free
                                  language and other constructs  . . . . . 45--51
               Georgii Gens and   
                 Evgenii Levner   Complexity of approximation algorithms
                                  for combinatorial problems: a survey . . 52--65
             Allan Gottlieb and   
               Clyde P. Kruskal   A note on sorting integers from a
                                  bounded range  . . . . . . . . . . . . . 66--67
                    David Harel   On folk theorems . . . . . . . . . . . . 68--80
                    Ernst Leiss   Constructing a finite automaton for a
                                  given regular expression . . . . . . . . 81--87
                Farshid Nourani   A note on the constructors of the
                                  computable universe  . . . . . . . . . . 88--89
    António G. Porto and   
               Armando B. Matos   Ackermann and the superpowers  . . . . . 90--95


ACM SIGACT News
Volume 13, Number 1, Winter, 1981

                 S. A. Greibach   Comments on the roots of theorems and
                                  languages both easy and hard . . . . . . 26--29
              Uwe Schöning   A note on complete sets for the
                                  polynomial-time hierarchy  . . . . . . . 30--34
           Clyde P. Kruskal and   
                Elia Weixelbaum   A note on the worst case of heapsort . . 35--38
              SIGACT News Staff   Technical reports  . . . . . . . . . . . 39--87

ACM SIGACT News
Volume 13, Number 2, Spring--Summer, 1981

              SIGACT News Staff   Technical reports  . . . . . . . . . . . 16--65


ACM SIGACT News
Volume 14, Number 1, Winter, 1982

              Uwe Schöning   On NP-decomposable sets  . . . . . . . . 18--20
                    Karel Culik   Theory of computation on
                                  abstract/concrete computer automata  . . 21--35
           Donald F. Stanat and   
               Stephen F. Weiss   A pumping theorem for regular languages  36--37
                 T. R. S. Walsh   The busy beaver on a one-way infinite
                                  tape . . . . . . . . . . . . . . . . . . 38--43
              SIGACT News Staff   Recent technical reports . . . . . . . . 44--65

ACM SIGACT News
Volume 14, Number 2, Spring, 1982

              SIGACT News Staff   Technical reports  . . . . . . . . . . . 20--41

ACM SIGACT News
Volume 14, Number 3, Summer, 1982

                L. H. Landweber   CSNET: a tool for researchers in
                                  theoretical computer science . . . . . . 21--22
               Don-Min Tsou and   
             Patrick C. Fischer   Decomposition of a relation scheme into
                                  Boyce--Codd Normal Form  . . . . . . . . 23--29
              Etienne Grandjean   Number of universal quantifiers and
                                  computational complexity: preliminary
                                  report . . . . . . . . . . . . . . . . . 30--30
               Siroos K. Afshar   On the complexity of permutation network
                                  design . . . . . . . . . . . . . . . . . 31--35
                 Dino Mandrioli   On teaching theoretical foundations of
                                  computer science . . . . . . . . . . . . 36--53

ACM SIGACT News
Volume 14, Number 4, Fall--Winter, 1982

               Whitfield Diffie   Cryptographic technology: fifteen year
                                  forecast . . . . . . . . . . . . . . . . 38--57
                 Dino Mandrioli   On teaching theoretical foundations of
                                  Computer Science . . . . . . . . . . . . 58--69
            John C. Cherniavsky   Book Review: \booktitleUnsolvable
                                  Classes of Quantificational Formulas, by
                                  Harry R. Lewis. Addison-Wesley 1979. and
                                  \booktitleThe Decision Problem: Solvable
                                  Classes of Quantificational Formulas, by
                                  Burton Dreben and Warren D. Goldfarb.
                                  Addison-Wesley 1979  . . . . . . . . . . 70--71
              SIGACT News Staff   Research advance abstracts . . . . . . . 72--83


ACM SIGACT News
Volume 15, Number 1, Winter--Spring, 1983

         Hamid R. Amirazizi and   
              Martin E. Hellman   Time-memory-processor tradeoffs  . . . . 18--19
         Hamid R. Amirazizi and   
             Ehud D. Karnin and   
              Justin M. Reyneri   Compact knapsacks are polynomially
                                  solvable . . . . . . . . . . . . . . . . 20--22
                    Manuel Blum   Coin Flipping by Telephone --- a
                                  Protocol for Solving Impossible Problems 23--27
                 Giles Brassard   An optimally secure relativized
                                  cryptosystem . . . . . . . . . . . . . . 28--33
                    Shimon Even   A protocol for signing contracts . . . . 34--39
          Martin E. Hellman and   
             Ehud D. Karnin and   
                 Justin Reyneri   On the necessity of cryptanalytic
                                  exhaustive search  . . . . . . . . . . . 40--44
                    Ernst Henze   The solution of a general equation for
                                  the public key system  . . . . . . . . . 45--49
                 Tore Herlestam   On the feasibility of computing discrete
                                  logarithms using Adleman's
                                  subexponential algorithm . . . . . . . . 50--55
            Ingemar Ingemarsson   Are all injective knapsacks partly
                                  solvable after multiplication modulo q?  56--60
                 John P. Jordan   A variant of a public key cryptosystem
                                  based on Goppa Codes . . . . . . . . . . 61--66
                 D. R. Morrison   Subtractive encryptors: alternatives to
                                  the DES  . . . . . . . . . . . . . . . . 67--77
                Stephen Wiesner   Conjugate coding . . . . . . . . . . . . 78--88
              SIGACT News Staff   Abstracts computing research laboratory  93--104

ACM SIGACT News
Volume 15, Number 2, Spring--Summer, 1983

         Ir\`ene Guessarian and   
      Francesco Parisi-Presicce   Iterative vs. regular factor algebras    32--44
                Alistair Moffat   The effect of paged memory upon
                                  algorithm performance: short note  . . . 45--52
                Cristian Calude   On a class of independent problems
                                  related to Rice theorem  . . . . . . . . 53--57
                  Stanley Coren   The game of academe  . . . . . . . . . . 58--62
              SIGACT News Staff   Abstracts  . . . . . . . . . . . . . . . 63--74
               Dan R. Olsen and   
                  Norman Badler   An expression model for graphical
                                  command languages  . . . . . . . . . . . 76--76
        Nicholas V. Findler and   
                Robert F. Cromp   An artificial intelligence technique to
                                  generate self-optimizing experimental
                                  designs  . . . . . . . . . . . . . . . . 77--77
        Nicholas V. Findler and   
                         Ron Lo   A note on the functional estimation of
                                  values of hidden variables: an extended
                                  module for expert systems  . . . . . . . 78--78

ACM SIGACT News
Volume 15, Number 3, Summer--Fall, 1983

                  Leona F. Fass   Learning Context-Free Languages from
                                  their Structured Sentences . . . . . . . 24--35
                    D. J. Cooke   On non-hierarchical systems of binary
                                  operators  . . . . . . . . . . . . . . . 36--44
             Ir\`ene Guessarian   Survey on classes of interpretations and
                                  some of their applications . . . . . . . 45--71
              SIGACT News Staff   Abstracts and available technical
                                  reports  . . . . . . . . . . . . . . . . 72--95

ACM SIGACT News
Volume 15, Number 4, Winter--Spring, 1984

                   Babra Simons   The reentry Computer Science Program at
                                  U.C. Berkeley  . . . . . . . . . . . . . 36--36
                  Richard Stark   Combinatory automaton  . . . . . . . . . 37--37
              SIGACT News Staff   Abstracts  . . . . . . . . . . . . . . . 48--56
             Jonathan S. Turner   On the general graph embedding problem
                                  with applications to circuit layout  . . 59--59
            S. Louis Hakimi and   
                     Oded Kariv   Midwest theory of computation symposium:
                                  on a generalization of edge-coloring in
                                  graphs . . . . . . . . . . . . . . . . . 60--60
                 Ronald V. Book   Relativizations of complexity classes    61--61
                    John Franco   Duality, finite improvement and
                                  efficiently solved optimization problems 62--62
            Eitan M. Gurari and   
                  Ten Hwang Lai   Deadlock detection in communicating
                                  finite state machines  . . . . . . . . . 63--64


ACM SIGACT News
Volume 16, Number 1, Winter--Spring, 1984

                   Babra Simons   The reentry Computer Science Program at
                                  U.C. Berkeley  . . . . . . . . . . . . . 36--36
                  Richard Stark   Combinatory automaton  . . . . . . . . . 37--37
              SIGACT News Staff   Abstracts  . . . . . . . . . . . . . . . 48--56
             Jonathan S. Turner   On the general graph embedding problem
                                  with applications to circuit layout  . . 59--59
            S. Louis Hakimi and   
                     Oded Kariv   Midwest theory of computation symposium:
                                  on a generalization of edge-coloring in
                                  graphs . . . . . . . . . . . . . . . . . 60--60
                 Ronald V. Book   Relativizations of complexity classes    61--61
                    John Franco   Duality, finite improvement and
                                  efficiently solved optimization problems 62--62
            Eitan M. Gurari and   
                  Ten Hwang Lai   Deadlock detection in communicating
                                  finite state machines  . . . . . . . . . 63--64

ACM SIGACT News
Volume 16, Number 2, Summer, 1984

               David S. Johnson   The genealogy of theoretical computer
                                  science: a preliminary report  . . . . . 36--49
                 Nicola Santoro   Sense of direction, topological
                                  awareness and communication complexity   50--56
              SIGACT News Staff   Abstracts  . . . . . . . . . . . . . . . 57--62

ACM SIGACT News
Volume 16, Number 3, Fall, 1984

              Charles B. Dunham   A sequence of uncomputable functions . . 48--48
              Andrei Broder and   
                   Jorge Stolfi   Pessimal algorithms and simplexity
                                  analysis . . . . . . . . . . . . . . . . 49--53

ACM SIGACT News
Volume 16, Number 4, April, 1985

            John C. Cherniavsky   NSF news . . . . . . . . . . . . . . . . 46--47
                 Barbara Simons   Some thoughts on running a conference    48--52
         Severo M. Ornstein and   
                Lucy A. Suchman   Reliability and responsibility . . . . . 53--55
  Paul M. B. Vitányi and   
               Lambert Meertens   Big omega versus the wild functions  . . 56--59
            Jacques Morgenstern   How to Compute Fast a Function and All
                                  Its Derivatives, A Variation on the
                                  Theorem of Baur-Strassen . . . . . . . . 60--62


ACM SIGACT News
Volume 17, Number 1, June, 1985

                 Nicola Santoro   The un-merging problem . . . . . . . . . 5--6
                      J. Franco   Sensitivity of probabilistic results on
                                  algorithms for NP-complete problems to
                                  input distributions  . . . . . . . . . . 40--59
                Gillea Brassard   Crusade for a better notation  . . . . . 60--64
                     Rod McBeth   The tree structure of exponential
                                  calculations . . . . . . . . . . . . . . 65--77
              C. J. Eqvhazy and   
                   T. B. Ramsay   Generating a set of fundamental cycles
                                  in a graph . . . . . . . . . . . . . . . 78--82

ACM SIGACT News
Volume 17, Number 2, September, 1985

             Harold M. Hastings   Maps of the interval, polynomial time,
                                  and polynomial space . . . . . . . . . . 44--51
             Harold M. Hastings   Convergence of simulated annealing . . . 52--63

ACM SIGACT News
Volume 17, Number 3, Winter, 1986

              Charles B. Dunham   A Simpler Approach to the Busy Beaver
                                  Problem  . . . . . . . . . . . . . . . . 29--29
                   Mara Chibnik   Algorithmic elimination of spurious
                                  nondeterminism from Mealy machines . . . 30--34
            Robert M. Nirenberg   A practical Turing machine
                                  representation . . . . . . . . . . . . . 35--44

ACM SIGACT News
Volume 17, Number 4, Spring, 1986

                   M. N. Wegman   What it's like to be a POPL referee  . . 50--51
                   Z. Galil and   
                   R. Giancarlo   Improved string matching with $k$
                                  mismatches . . . . . . . . . . . . . . . 52--54
                     L. F. Fass   On the inference of canonical
                                  context-free grammars  . . . . . . . . . 55--60
                    Y. Gurevich   What does O(n) mean  . . . . . . . . . . 61--63


ACM SIGACT News
Volume 18, Number 1, Summer, 1986

                   R. Bernstein   Testing for semilattices . . . . . . . . 49--50
                   C. B. Dunham   The cycle burning problem  . . . . . . . 51--51
                   D. M. Wilson   The halting problem for Turning machines 52--52
             D. M. Atkinson and   
                 N. Santoro and   
                     J. Urrutia   On the integer complexity of Boolean
                                  matrix multiplication  . . . . . . . . . 53--53
                    I. Parberry   Parallel speedup of sequential machines:
                                  a defense of parallel computation thesis 54--67
                       D. Harel   Logic and databases: a critique  . . . . 68--74
                  A. K. Dewdney   Experiments with a generic reduction
                                  computer . . . . . . . . . . . . . . . . 75--79
                  C. Gerety and   
                        P. Cull   Time complexity of the Towers of Hanoi
                                  problem  . . . . . . . . . . . . . . . . 80--87

ACM SIGACT News
Volume 18, Number 2, September / March, 1986--1987

                       D. Kozen   Fast parallel orthogonalization  . . . . 47--47
                   D. Wiedemann   Quantum cryptography . . . . . . . . . . 48--51
                H. Gallaire and   
                  J. Minker and   
                  J. M. Nicolas   Logic and databases: a response  . . . . 52--56
                       Z. Qiang   An $ O(\ln n) $ parallel algorithm for
                                  the subset sum problem . . . . . . . . . 57--63
                      R. McBeth   The tree structure of exponential
                                  calculations --- Addendum  . . . . . . . 64--64

ACM SIGACT News
Volume 18, Number 3, April, 1987

             K. L. Williams and   
                  M. R. Meybodi   Representing problems as string
                                  transformations  . . . . . . . . . . . . 29--30
                      R. McBeth   A proof of generalized induction . . . . 31--36
                   C. B. Dunham   Pessimization is unsolvable  . . . . . . 37--37
                     D. Epstein   On the NP-completeness of cryptarithms   38--40
                 A. J. Dos Reis   Regular languages under F-gsm mappings   41--45
                 A. J. Dos Reis   Regular languages do not form a lattice
                                  under GSM mappings . . . . . . . . . . . 46--47
                  L. Burkholder   The halting problem  . . . . . . . . . . 48--60
                     E. Staples   The tower of Hanoi problem with
                                  arbitrary start and end positions  . . . 61--64

ACM SIGACT News
Volume 18, Number 4, Summer, 1987

               James M. Swenson   A constructive proof of the countability
                                  of $ \Sigma * $  . . . . . . . . . . . . 48--50
         Charles H. Bennett and   
                Gilles Brassard   Quantum public key distribution
                                  reinvented . . . . . . . . . . . . . . . 51--53
                 Shang-Hua Teng   The construction of Huffman-equivalent
                                  prefix code in NC  . . . . . . . . . . . 54--61


ACM SIGACT News
Volume 19, Number 1, Fall, 1987

                 B. Simmons and   
                      J. Yudken   Federal funding in computer science: a
                                  preliminary report . . . . . . . . . . . 54--63

ACM SIGACT News
Volume 19, Number 2, 1988

                   Ian Parberry   How to Present a Paper in Theoretical
                                  Computer Science: a Speaker's Guide for
                                  Students . . . . . . . . . . . . . . . . 42--47
                  V. Kantabutra   A lower bound on the path length of
                                  binary trees . . . . . . . . . . . . . . 48--50
                 B. M. E. Moret   Planar NAE3SAT is in P . . . . . . . . . 51--54
                 Howard Trickey   Using \LaTeX . . . . . . . . . . . . . . 55--57

ACM SIGACT News
Volume 19, Number 3--4, Fall, 1988

                    Maria Klawe   SIGACT salary survey . . . . . . . . . . 11--17
                Joseph O'Rourke   Computational geometry column  . . . . . 21--26
              Joachim Ciesinger   Neural nets  . . . . . . . . . . . . . . 46--47


ACM SIGACT News
Volume 20, Number ??, 1988

           Ronald L. Graham and   
            Donald E. Knuth and   
                 Oren Patashnik   Textbook Announcement:
                                  \booktitleConcrete Mathematics: a
                                  Foundation for Computer Science  . . . . ??


ACM SIGACT News
Volume 20:4, Number ??, Fall, 1989

              P. Kanellakis and   
                   S. Abiteboul   Deciding bounded recursion in database
                                  logic programs . . . . . . . . . . . . . 


ACM SIGACT News
Volume 20, Number ??, 1989

                    T. Zeugmann   Book Review: Baase, \booktitleComputer
                                  Algorithms: Introduction to Design and
                                  Analysis (2nd ed.) (1988)  . . . . . . . 

ACM SIGACT News
Volume 20, Number 1, Winter, 1989

                     L. Ramshaw   Suitening our nomenclature . . . . . . . 60--61
                       M. Tompa   Figures of merit . . . . . . . . . . . . 62--71

ACM SIGACT News
Volume 20, Number 2, March, 1989

                Joseph O'Rourke   Computational geometry column  . . . . . 10--11

ACM SIGACT News
Volume 20, Number 3, July, 1989

                Gilles Brassard   Cryptology column  . . . . . . . . . . . 15--19
                Joseph O'Rourke   Computational geometry column  . . . . . 25--26
               Joost Engelfriet   The complexity of the circularity
                                  problem for attribute grammars: a note
                                  on a counterexample for a simpler
                                  construction . . . . . . . . . . . . . . 57--59
            Peter Salenieks and   
          Michael G. Farringdon   How To Answer It . . . . . . . . . . . . 60--63

ACM SIGACT News
Volume 20, Number 4, November, 1989

                    G. Brassard   Cryptology --- column 2  . . . . . . . . 13--13
                       C. Dwork   Distributed computing column . . . . . . 14--16
        Paris C. Kanellakis and   
                Serge Abiteboul   Database Theory Column: Deciding Bounded
                                  Recursion in Database Logic Programs . . 17--23
                     S. Khuller   Open problems: 3 . . . . . . . . . . . . 24--24
                      D. T. Lee   NSF report --- computer and computation
                                  research . . . . . . . . . . . . . . . . 25--25
                     M. C. Loui   Reprint from \booktitleComputing Reviews 26--29
                    J. O'Rourke   Computational geometry column 8  . . . . 30--30
                    I. Parberry   The journal review column  . . . . . . . 31--37
               W. M. Farmer and   
                   A. J. Kfoury   Minutes of the 4th annual LICS business
                                  meeting  . . . . . . . . . . . . . . . . 43--47
                  J. Feigenbaum   Report on DIMACS seminar series  . . . . 48--49
              I. Guessarian and   
                      D. Perrin   LITP: Laboratoire D'Informatique
                                  théorique et programmation Paris:
                                  Presentation of scientific activity  . . 50--53
                    M. Stallman   Course outline: course announcement
                                  (Spring 1989) CSE/OR 691 I: Surviving
                                  Intractability . . . . . . . . . . . . . 74--77
              C. H. Bennett and   
                    G. Brassard   Experimental quantum cryptography: the
                                  dawn of a new era for quantum
                                  cryptography: the experimental prototype
                                  is working . . . . . . . . . . . . . . . 78--80
                 M. Chrobak and   
                     H. Karloff   A lower bound on the size of universal
                                  sets for planar graphs . . . . . . . . . 83--86
              M. J. Fischer and   
              R. P. Fischer and   
                      R. Beigel   Primitive recursion without implicit
                                  predecessor  . . . . . . . . . . . . . . 87--91
                    I. Parberry   A guide for new referees in theoretical
                                  computer science . . . . . . . . . . . . 92--99


ACM SIGACT News
Volume 21, Number 1, January, 1990

                 Gilles Brasard   Cryptology --- column 3 hot news on
                                  interactive protocols  . . . . . . . . . 7
                  Samir Khuller   Open problems  . . . . . . . . . . . . . 12
                      D. T. Lee   NSF report --- computer and computation
                                  research . . . . . . . . . . . . . . . . 13
                Michael C. Loui   Reprint from \booktitleComputing Reviews 14
                Joseph O'Rourke   Computational geometry column 9  . . . . 18
                   Ian Parberry   The journal review column  . . . . . . . 21
                     S. S. Ravi   Journal backlog report . . . . . . . . . 26

ACM SIGACT News
Volume 21, Number 2, Spring, 1990

               David S. Johnson   A STOC/FOCS bibliography: the last
                                  progress report  . . . . . . . . . . . . 4
                Gilles Brassard   Cryptology --- column 4: hiding
                                  information from oracles . . . . . . . . 5
                  Cynthia Dwork   Distributed computing column . . . . . . 12
                      D. T. Lee   NSF report --- computer and computation
                                  research . . . . . . . . . . . . . . . . 16
                   Ian Parberry   The journal review column  . . . . . . . 21
                Joan Feigenbaum   Report on DIMACS seminar series  . . . . 25
           Susanne E. Hambrusch   Report of the 21st Midwest Theory
                                  Consortium . . . . . . . . . . . . . . . 30
             Arthur L. Liestman   Report on WOBCATS meeting  . . . . . . . 32
           Andrzej Proskurowski   Report on GRA-GRA: 4th International
                                  Workshop on Graph Grammars and Their
                                  Applications to Computer Science . . . . 39
                   Rex A. Dwyer   Kinder, gentler average-case analysis
                                  for convex hulls and maximal vectors . . 64

ACM SIGACT News
Volume 21, Number 3, Summer, 1990

            Serge Abiteboul and   
            Paris C. Kanellakis   Database Theory Column: Query Languages
                                  for Complex Object Databases . . . . . . 9--18
               Ramki Thurimella   Report on WOPA: Workshop on Parallel
                                  Algorithms . . . . . . . . . . . . . . . ??

ACM SIGACT News
Volume 21, Number 4, Fall, 1990

                 Luigi Palopoli   A new proof of undecidability of safety
                                  of logic queries . . . . . . . . . . . . 69--72
                   B. Ravikumar   Some applications of a technique of
                                  Sakoda and Sipser  . . . . . . . . . . . 73--77
                   Martin Tompa   Figures of merit: the sequel . . . . . . 78--81


ACM SIGACT News
Volume 22, Number 1, Winter, 1991

                Gilles Brassard   How convincing is your protocol? . . . . 5--12
                   Leonid Levin   Theory of computation: how to start  . . 47--56
                  Zvi Galil and   
           Giuseppe F. Italiano   Reducing edge connectivity to vertex
                                  connectivity . . . . . . . . . . . . . . 57--61
                Oscar H. Ibarra   On resetting DLBA's  . . . . . . . . . . 62--63
                 Ernst L. Leiss   Some comments on a recent note by
                                  Ravikumar  . . . . . . . . . . . . . . . 64--64
                Alan T. Sherman   On Superpolylogarithmic Subexponential
                                  Functions (Part I) . . . . . . . . . . . 65

ACM SIGACT News
Volume 22, Number 2, Spring, 1991

            Jean-Camille Birget   Intersection of Regular Languages and
                                  State Complexity . . . . . . . . . . . . 49
                Prabhakar Ragde   Extracting Poetry from Technical Papers  50
                 Man T. Sherman   On Superpolylogarithmic Subexponential
                                  Functions (Part II)  . . . . . . . . . . 51--56

ACM SIGACT News
Volume 22, Number 3, Summer, 1991

               Richard Cole and   
                    Alan Siegel   Report on the Second Workshop on
                                  Parallel Algorithms (WOPA) . . . . . . . 20--23
   Hél\`ene Kirchner and   
                Pierre Lescanne   Rewriting techniques and applications,
                                  RTA'91 . . . . . . . . . . . . . . . . . 24--30
                 Natalie Angier   The glass ceiling: in theory women swell
                                  ranks of science, but remain invisible
                                  at the top . . . . . . . . . . . . . . . 38--40
                Michael C. Loui   Theory of computing: achievements,
                                  challenges, and opportunities  . . . . . 41--48
                   Rohit Parikh   A test for fuzzy logic . . . . . . . . . 49--50
                   Sheng Yu and   
                  Qingyu Zhuang   On the state complexity of intersection
                                  of regular languages . . . . . . . . . . 52--54
                   M. A. McBeth   Finite types, exponential forms and
                                  complete trees . . . . . . . . . . . . . 55--62
                 P. A. Laplante   The Heisenberg uncertainty principle and
                                  the halting problem  . . . . . . . . . . 63--65

ACM SIGACT News
Volume 22, Number 4, Fall, 1991

                   C. P. Rupert   Commutative regular languages  . . . . . 48--49
             F. Aurenhammer and   
                 G. Stöckl   On the Peeper's Voronoi diagram  . . . . 50--59
              Amir M. Ben-Amram   Some notions on notations  . . . . . . . 60--62
                    Uzi Vishkin   Can parallel algorithms enhance serial
                                  implementation . . . . . . . . . . . . . 63--63


ACM SIGACT News
Volume ??, Number ??, 1991

                Rajeev Alur and   
            Thomas A. Henzinger   Sigact News Logic Column 1: Time for
                                  Logic  . . . . . . . . . . . . . . . . . ??


ACM SIGACT News
Volume 23, Number ??, 1992

                    T. Zeugmann   Book Review: Reingold and Shen,
                                  \booktitleMore Nearly Optimal Algorithms
                                  for Unbounded Searching (1991) . . . . . ??

ACM SIGACT News
Volume 23, Number 1, Winter, 1992

                Francine Berman   CRA status of women column . . . . . . . 14--17
                     Rocky Ross   Education Forum  . . . . . . . . . . . . 18--19
                Joseph O'Rourke   Book Review: \booktitleIntersection and
                                  Decomposition Algorithms for Planar
                                  Arrangements, by Pankaj K. Agarwal.
                                  (Cambridge University Press, Cambridge,
                                  1991. xvii + 277 pp. \$39.50 cloth. ISBN
                                  0-521-40446-0)}  . . . . . . . . . . . . 35--36
                   M. A. McBeth   The Turing machine of Ackermann's
                                  function . . . . . . . . . . . . . . . . 37--43
                 Oded Goldreich   Critique of some trends in the TCS
                                  community in light of two controversies  44--46
                    Varol Akman   Undaunted sets (extended abstract) . . . 47--48

ACM SIGACT News
Volume 23, Number 2, Spring, 1992

                Joseph O'Rourke   Computational geometry . . . . . . . . . 26--28
                Patrick Lincoln   Linear logic . . . . . . . . . . . . . . 29--37
                Patrick Lincoln   Linear Logic: Guest Logic Column . . . . 29--37
                     Rocky Ross   Education Forum  . . . . . . . . . . . . 50--53
                 John T. Stasko   Animating Algorithms with XTANGO . . . . 67--71
            Fabrizio Luccio and   
                    Linda Pagli   The $p$-shovelers problem: (computing
                                  with time-varying data)  . . . . . . . . 72--75
                      Zvi Galil   Renato Capocelli . . . . . . . . . . . . 104

ACM SIGACT News
Volume 23, Number 3, Summer, 1992

                  Tom Jacob and   
                    Bill Kaizer   Book review: \booktitleA Unifying
                                  Framework for Structured Analysis and
                                  Design Models. By T. H. Tse. (Cambridge
                                  University Press, 1991. xi + 179pp. ISBN
                                  0-521-39196-2) . . . . . . . . . . . . . 30
                   Sajal K. Das   Book Review: \booktitleIntroduction to
                                  Parallel Algorithms and Architectures:
                                  Arrays, Trees, Hypercubes, by F. T.
                                  Leighton (Morgan Kauffman Pub, 1992) . . 31--32
                     Rocky Ross   Education forum  . . . . . . . . . . . . 33
                       B. Litow   On Rat$_\infty $ . . . . . . . . . . . . 98--99
             Bryant A. Julstrom   A bound on the shift function in terms
                                  of the Busy Beaver function  . . . . . . 100--106
                     Paul Young   How reductions to sparse sets collapse
                                  the polynomial-time hierarchy: a primer;
                                  part I: polynomial-time Turing
                                  reductions . . . . . . . . . . . . . . . 107--117

ACM SIGACT News
Volume 23, Number 4, Fall, 1992

                     J. Shallit   Randomized Algorithms in ``Primitive
                                  Cultures'' . . . . . . . . . . . . . . . 77--80


ACM SIGACT News
Volume 24, Number 1, Winter, 1993

                  Mark A. Weiss   Technical report column  . . . . . . . . 10--16
                Joseph O'Rourke   Computational geometry column 18 . . . . 20--25
               S. Purushothaman   Book Review: \booktitleNets, Terms and
                                  Formulas. By E.-R. Olderog. (Cambridge
                                  University Press, 1991. x + 267pp. ISBN
                                  0-521-40044-9. \$49.95)} . . . . . . . . 26--27
            Thomas A. Henzinger   Book Review: \booktitleVerifying
                                  Temporal Properties of Systems, by
                                  Julian Charles Bradfield. (Birkhäuser,
                                  1992 viii + 113pp. ISBN 0-8176-3625-0.
                                  \$49.50)}  . . . . . . . . . . . . . . . 27--28
                 Ryan Stansifer   Book Review: \booktitleSemantics of
                                  Programming Languages: Structures and
                                  Techniques. By Carl A. Gunter. (MIT
                                  Press, 1992. xviii + 419pp. ISBN
                                  0-262-07143-6 \$37.50)}  . . . . . . . . 28--29
                     Rocky Ross   Education Forum: New Courses on the
                                  Horizon  . . . . . . . . . . . . . . . . 30
                   Carlo Batini   Applications of graph drawing to
                                  software engineering (abstract)  . . . . 57
                    Peter Eades   Algorithms for drawing trees (abstract)  57
                     Janos Pach   Extremal problems in graph drawings
                                  (abstract) . . . . . . . . . . . . . . . 57
              Ioannis G. Tollis   Visibility representations of planar
                                  graphs (abstract)  . . . . . . . . . . . 57--58
        Hubert de Fraysseix and   
             Pierre Rosenstiehl   Partial orders for planarity and
                                  drawings (abstract)  . . . . . . . . . . 58
                  Kozo Sugiyama   Drawing compound digraphs and its
                                  application to an idea organizer
                                  (abstract) . . . . . . . . . . . . . . . 58
           Giuseppe Di Battista   Area requirements (abstract) . . . . . . 58--59
               Michael Kaufmann   Angular resolution of straight-line
                                  drawings (abstract)  . . . . . . . . . . 59
                    Bojan Mohar   Circle packing representation in the
                                  plane and other surfaces . . . . . . . . 59
               Roberto Tamassia   Algorithms for orthogonal drawings
                                  (abstract) . . . . . . . . . . . . . . . 59
                Robert F. Cohen   Dynamic graph drawing (abstract) . . . . 60
                      Goos Kant   A new method for planar graph drawings
                                  on a grid (abstract) . . . . . . . . . . 60
                Giuseppe Liotta   An automatic layout facility (abstract)  60
Martín Hötzel Escardó   On lazy natural numbers with
                                  applications to computability theory and
                                  functional programming . . . . . . . . . 61--67
                 Andrew Davison   Vague text compression . . . . . . . . . 68--74

ACM SIGACT News
Volume 24, Number 2, Spring, 1993

           Lane A. Hemaspaandra   Lowness: a yardstick for NP-P  . . . . . 10--14
                 Claire Toynbee   On the outer: women in computer science
                                  courses  . . . . . . . . . . . . . . . . 18--21
                  Jon G. Riecke   Book Review: \booktitleAction Semantics.
                                  By Peter D. Mosses. (Cambridge
                                  University Press, 1992. xx + 372pp. ISBN
                                  0-521-40347-2. \$49.95)} . . . . . . . . 24--25
                    Amy Zwarico   Book Review: \booktitleAction Refinement
                                  in Process Algebras. By Luca Aceto.
                                  (Cambridge University Press, 1992. ix +
                                  273pp. ISBN 0-521-43111-5. \$49.95)} . . 25--26
                     Rocky Ross   Education Forum: An Introductory
                                  Computer Science Curriculum
                                  Incorporating Theory . . . . . . . . . . 27--29
                     Don Colton   A restated pumping lemma for
                                  context-free languages . . . . . . . . . 87
               R. Chaudhuri and   
                   H. Höft   Splaying a search tree in preorder takes
                                  linear time  . . . . . . . . . . . . . . 88--93

ACM SIGACT News
Volume 24, Number 3, October, 1993

               Kenneth W. Regan   Machine models and linear time
                                  complexity . . . . . . . . . . . . . . . 5--15
            Boleslaw Mikolajzak   Book Review: \booktitleColoured Petri
                                  Nets: Basic Concepts, Analysis Methods
                                  and Practical Use, Volume One. By Kurt
                                  Jensen. (Springer-Verlag, 1992. vii +
                                  234 pages. ISBN 0-387-55597-8. \$69.00)} 31--33
             Prakesh Panangaden   Book Review: \booktitlePrograms,
                                  Recursion and Unbounded Choice. By Wim
                                  H. Hesselink. (Cambridge University
                                  Press, 1992. xii + 223 pages. ISBN
                                  0-521-40436-3. \$39.95)} . . . . . . . . 34--37
                     Rocky Ross   Education Forum: Lecture and Lab
                                  Syllabus for a Breadth-First
                                  Introductory Computer Science Course
                                  Sequence following the Data Structures
                                  and Algorithms Paradigm  . . . . . . . . 38--43
               Clark Thomborson   Why are fewer females obtaining
                                  bachelor's degrees in computer science?  114--116
                   Hu Xiao-Long   The representation of a program in the
                                  Blum--Shub--Smale theory of computation
                                  over an arbitrary ring . . . . . . . . . 117--119

ACM SIGACT News
Volume 24, Number 4, December, 1993

                 Oded Goldreich   A Taxonomy of Proof Systems (part 1) . . 2--13
            Michael T. Goodrich   Parallel algorithms column 1: models of
                                  computation  . . . . . . . . . . . . . . 16--21
                   A. P. Sistla   Book Review: \booktitleThe Temporal
                                  Logic of Reactive and Concurrent Systems
                                  --- Specification. By Zohar Manna and
                                  Amir Pnueli. (Springer-Verlag, 1991. xiv
                                  + 427pp. ISBN 0-387-97664-7. \$49.95)}   34--36
                 J. A. Makowsky   Book Review: \booktitlePredicate
                                  Transformer Semantics. By Ernest G.
                                  Manes. (Cambridge University Press,
                                  1992. 233pp. ISBN 0-521-42036-9.
                                  \$39.95)}  . . . . . . . . . . . . . . . 36--38
                        R. Ross   Computer science laboratories  . . . . . 45--48
             Claude G. Diderich   A Bibliography on Minimax Trees  . . . . 82--89
              Thomas H. Spencer   Context-free languages . . . . . . . . . 90--91


ACM SIGACT News
Volume 25, Number 1, March, 1994

                 Oded Goldreich   A Taxonomy of Proof Systems (part 2) . . 22--30
                Joseph O'Rourke   Computational geometry . . . . . . . . . 31--33
              Lance Fortnow and   
               Stuart Kurtz and   
                     Duke Whang   The infinite version of an open
                                  communication complexity problem is
                                  independent of the axioms of set theory  87--89
               Armando B. Matos   An introduction to ultimately periodic
                                  sets of integers . . . . . . . . . . . . 90--96

ACM SIGACT News
Volume 25, Number 2, June, 1994

           Lane A. Hemaspaandra   Complexity theory column 5: the
                                  not-ready-for-prime-time conjectures . . 5--10
                  Yuri Gurevich   Logic Activities in Europe . . . . . . . 11--24
          Jean-Pierre Jouannaud   Book Review: \booktitleA Proof Theory
                                  for General Unification. By Wayne
                                  Snyder. (Birkhäuser, 1991. vi + 175
                                  pages. ISBN 0-8176-3593-9. \$28.00)} . . 25
                    Frank Vlach   Book Review: \booktitleThe Deductive
                                  Foundations of Computer Programming. By
                                  Zohar Manna and Richard Waldinger.
                                  (Addison-Wesley, 1993. xiv + 717pp. ISBN
                                  0-201-54886-0. \$46.25)} . . . . . . . . 26--27
           Stephen A. Bloch and   
           Jonathan F. Buss and   
                 Judy Goldsmith   How hard are $ n^2$-hard problems? . . . 83--85
                   Rajeev Raman   A simpler analysis of algorithm 65
                                  (find) . . . . . . . . . . . . . . . . . 86--89
Antônio Carlos da Rocha Costa and   
     Vanderlei Moraes Rodrigues   Inspecting continuations . . . . . . . . 90--91

ACM SIGACT News
Volume 25, Number 3, September, 1994

          Derek Denny-Brown and   
                  Yenjo Han and   
       Lane A. Hemaspaandra and   
                Leen Torenvliet   Semi-membership algorithms: some recent
                                  advances . . . . . . . . . . . . . . . . 12--23
                Joseph O'Rourke   Computational geometry column 23 . . . . 24--27
                William Gasarch   Book Review: \booktitleFinite Automata,
                                  Formal Logic, and Circuit Complexity. By
                                  Howard Straubing. (Birkhäuser. 1994. xii
                                  + 226pp. ISBN 0-8176-3719-2. \$39.50)}   28--32
                     Rocky Ross   Education Forum: Project Impact:
                                  NSF-Funded Science Education Projects    49--52
                    H. Petersen   Two-way one-counter automata accepting
                                  bounded languages  . . . . . . . . . . . 102--105
           Kenneth W. Regan and   
                       Jie Wang   The quasilinear isomorphism challenge    106--113
   Alejandro López-Ortiz   Linear pattern matching of repeated
                                  substrings . . . . . . . . . . . . . . . 114--121
         Michael T. Hallett and   
                H. Todd Wareham   A compendium of parameterized complexity
                                  results  . . . . . . . . . . . . . . . . 122--123
                 Jim French and   
                 Edward Fox and   
                  Kurt Maly and   
                 Alan L. Selman   Wide area technical report
                                  service-technical reports online . . . . 124--127

ACM SIGACT News
Volume 25, Number 4, December, 1994

           Lane A. Hemaspaandra   Teaching Computational Complexity:
                                  Resources to Treasure  . . . . . . . . . 2--11
                Joseph O'Rourke   Computational Geometry Column 24 . . . . 12--14
                Gilles Brassard   Cryptology Column -- Quantum Computing:
                                  The End of Classical Cryptography? . . . 15--21
                Gilles Brassard   Quantum computing: the end of classical
                                  cryptography?  . . . . . . . . . . . . . 15--21
               Paris Kanellakis   Database querying and constraint
                                  programming  . . . . . . . . . . . . . . 22--87
                     Rocky Ross   Education Forum: The Dynalab Animation
                                  System . . . . . . . . . . . . . . . . . 49--54
                Thomas Zeugmann   Report on COLT 1994  . . . . . . . . . . 88--95
                   Ian Parberry   A form for referees in theoretical
                                  computer science . . . . . . . . . . . . 96--102
                Rice University   In memoriam Eugene L. Lawler . . . . . . 108--109


ACM SIGACT News
Volume 26, Number 1, March, 1995

       Lane A. Hemaspaandra and   
               Heribert Vollmer   The satanic notations: counting classes
                                  beyond #P and other definitional
                                  adventures . . . . . . . . . . . . . . . 2--13
                Joseph O'Rourke   Computational geometry . . . . . . . . . 14--16
                  Cynthia Dwork   Distributed Computing Column: Lotus
                                  Notes Security and Authentication  . . . 17--19
                  Erkan Tan and   
                    Varol Akman   Book Reviews: \booktitleLogic for
                                  Applications, by Anil Nerode and Richard
                                  A. Shore . . . . . . . . . . . . . . . . 20--22
                Michael C. Loui   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 24--26
          Sandra Johnson Baylor   Graduate Information for Women in CS&E    27--30
                 Dana May Latch   NSF Announcements: Theory of Computing
                                  Program  . . . . . . . . . . . . . . . . 31--32
                  Samir Khuller   Open Problems: 11  . . . . . . . . . . . 33
                  Mark A. Weiss   Technical Report Column  . . . . . . . . 34--39
                     Rocky Ross   Education Forum: Animated Textbooks: A
                                  Current Example  . . . . . . . . . . . . 40--43
          Michael J. Kearns and   
              Umesh V. Vazirani   Computational Learning Theory  . . . . . 43--45
           Roberto Tamassia and   
              Ioannis G. Tollis   Report on Graph Drawing '94  . . . . . . 87--91
                 Manfred Kudlek   Report on IFIP'94  . . . . . . . . . . . 92--98
                   Ian Parberry   Surfing the Web  . . . . . . . . . . . . 99--101

ACM SIGACT News
Volume 26, Number 2, June, 1995

                    Anne Condon   Approximate solutions to problems in
                                  PSPACE . . . . . . . . . . . . . . . . . 4--13
                Joseph O'Rourke   Computational geometry column 26 . . . . 15--17
                Gilles Brassard   Cryptology Column: The Book I've Always
                                  Wanted To Write (Almost) . . . . . . . . 18--20
                    David Harel   Will I be pretty, will I be rich?: some
                                  thoughts on theory vs. practice in
                                  systems engineering  . . . . . . . . . . 21--25
            Stephen R. Tate and   
            David B. Benson and   
             Jonathan Goldstine   Book Reviews . . . . . . . . . . . . . . 26--32
                Michael C. Loui   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 33--36
                 Dana May Latch   NSF Announcements: Theory of Computing
                                  Program  . . . . . . . . . . . . . . . . 37--38
                  Mark A. Weiss   Journal Backlog Report . . . . . . . . . 39--44
                  Mark A. Weiss   Technical Report Column  . . . . . . . . 45--46
                     Rocky Ross   Education Forum: Animation Activities at
                                  SRC  . . . . . . . . . . . . . . . . . . 47--50
                   Ian Parberry   Problems on Algorithms . . . . . . . . . 50--56
                Leonid A. Levin   STOC Criteria  . . . . . . . . . . . . . 77
              Ashok Subramanian   Two recent algorithms for the global
                                  minimum cut problem  . . . . . . . . . . 78--87
              Amir M. Ben-Amram   What is a ``Pointer Machine''? . . . . . 88--95
             Michael Goldwasser   A survey of linear programming in
                                  randomized subexponential time . . . . . 96--104

ACM SIGACT News
Volume 26, Number 3, September, 1995

                Ioan I. Macarie   Space-bounded probabilistic computation:
                                  old and new stories  . . . . . . . . . . 1--12
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 10  2--12
      Christos H. Papadimitriou   Database metatheory: asking the big
                                  queries  . . . . . . . . . . . . . . . . 13--30
                Michael C. Loui   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 32--41
                 Janice E. Cuny   Workshops offer mentoring opportunities  42--44
                     Rocky Ross   Education and the World Wide Web . . . . 45--48
             Rajeev Motwani and   
              Prabhaka Raghavan   Randomized Algorithms  . . . . . . . . . 48--50

ACM SIGACT News
Volume 26, Number 4, December, 1995

               Amihood Amir and   
                Manuel Blum and   
               Michael Loui and   
                John Savage and   
                     Carl Smith   Contributions of theoretical computer
                                  science  . . . . . . . . . . . . . . . . 2--4
       Lane A. Hemaspaandra and   
          Ajit Ramachandran and   
                  Marius Zimand   Worlds to die for  . . . . . . . . . . . 5--15
                Serge Abiteboul   Report on PODS'95  . . . . . . . . . . . 16--18
                Joseph O'Rourke   Computational geometry column 27 . . . . 19--21
                 Dana May Latch   NSF Announcements: Theory of Computing
                                  Program  . . . . . . . . . . . . . . . . 22--23
                  Mark A. Weiss   Journal Backlog Report . . . . . . . . . 24--31
                     Rocky Ross   Education Forum: Beware the Backlash:
                                  The Teaching vs. Research Conundrum
                                  Revisited  . . . . . . . . . . . . . . . 36--38
               Mark Allen Weiss   Algorithms, Problem Solving, and Data
                                  Structures with C + +  . . . . . . . . . 39--50
         Ricardo A. Baeza-Yates   Teaching algorithms  . . . . . . . . . . 51--59


ACM SIGACT News
Volume 27, Number 1, March, 1996

           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 12  2--13
                Michael C. Loui   Reprint from \booktitleComputing Reviews 14--15
                  Mark A. Weiss   Technical Report Column  . . . . . . . . 16--23
                     Rocky Ross   Education Forum: Java\ldotsHot Java!:
                                  What is that Brewing on the Web? . . . . 24--27
                 Michael Sipser   Introduction to the Theory of
                                  Computation  . . . . . . . . . . . . . . 27--29
                  Harry Buhrman   A short note on Shor's factoring
                                  algorithm  . . . . . . . . . . . . . . . 89--90

ACM SIGACT News
Volume 27, Number 2, June, 1996

                   Michael Luby   SICACT Treasurer's Report  . . . . . . . 5--6
                Joseph O'Rourke   Computational geometry column 28 . . . . 18--19
             Judy Goldsmith and   
            Matthew A. Levy and   
                Martin Mundhenk   Limited nondeterminism . . . . . . . . . 20--29
   Stéphane Grumbach and   
              Leonid Libkin and   
                  Tova Milo and   
                   Limsoon Wong   Query languages for bags: expressive
                                  power and complexity . . . . . . . . . . 30--37
                  Mark A. Weiss   Journal Backlog Report . . . . . . . . . 38--44
                Michael C. Loui   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 45--46
                  Samir Khuller   Open Problems: 13  . . . . . . . . . . . 52--54
                     Rocky Ross   Education Forum: Making Theory Come
                                  Alive  . . . . . . . . . . . . . . . . . 58--64
               David S. Johnson   How to do experiments (extended
                                  advertisement) . . . . . . . . . . . . . 87
            William Gasarch and   
                Wayne Kelly and   
                   William Pugh   Finding the $i$ th largest of $n$ for
                                  small $ i, n$  . . . . . . . . . . . . . 88--96

ACM SIGACT News
Volume 27, Number 3, September, 1996

  Christos H. Papadimitriou and   
             Oded Goldreich and   
              Avi Wigderson and   
      Alexander A. Razborov and   
                 Michael Sipser   The future of computational complexity
                                  theory: part I . . . . . . . . . . . . . 6--12
            Gilles Brassard and   
          Claude Crépeau   25 years of quantum cryptography . . . . 13--24
             Mihalis Yannakakis   Perspectives on database theory  . . . . 25--49
                  Cynthia Dwork   Distributed computing column . . . . . . 50--54
                Joseph O'Rourke   Computational Geometry Column 29 . . . . 55--59
                     Rocky Ross   Education forum: retrospective . . . . . 69--70
                Leonid A. Levin   Fundamentals of computing (a cheatlist)  89
               David S. Johnson   A Brief History of SIGACT News and its
                                  Editors  . . . . . . . . . . . . . . . . 125
          Stephen A. Fenner and   
           Lance J. Fortnow and   
             William J. Gasarch   Complexity Theory Newsflash  . . . . . . 126

ACM SIGACT News
Volume 27, Number 4, December, 1996

                E. Allender and   
              J. Feigenbaum and   
               J. Goldsmith and   
                 T. Pitassi and   
                      S. Rudich   The future of computational complexity
                                  theory: part II  . . . . . . . . . . . . 3--7
                   Richard Hull   Report on PODS '96 . . . . . . . . . . . 8--10
                  Samir Khuller   Open Problems 14 . . . . . . . . . . . . 11
               Rockford J. Ross   Education forum: loops and induction
                                  proofs . . . . . . . . . . . . . . . . . 15--19
                Susan H. Rodger   Report on The First International
                                  Workshop on Implementing Automata 1996   38--45
                   Steve Seiden   Theoretical computer science cheat sheet 52--61
                   Ian Parberry   Paul Erd\Hos (1913--1996)  . . . . . . . 62--65


ACM SIGACT News
Volume 28, Number 1, March, 1997

           Lane A. Hemaspaandra   Journals to Die For  . . . . . . . . . . 2
                Joseph O'Rourke   Computational Geometry Column 30 . . . . 7
                Michael C. Loui   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 9
                     Rocky Ross   Education Forum  . . . . . . . . . . . . 13
              Ruiguang Yang and   
               Longyun Ding and   
                      Shurun Xu   Some better results estimating the shift
                                  function in terms of busy beaver
                                  function . . . . . . . . . . . . . . . . 43--48
                  Zhizhang Shen   Correcting an Error in a 'Cheat Sheet'   49

ACM SIGACT News
Volume 28, Number 2, June, 1997

         Edith Hemaspaandra and   
       Lane A. Hemaspaandra and   
                Jörg Rothe   Raising NP lower bounds to parallel NP
                                  lower bounds . . . . . . . . . . . . . . 2--13
            Gilles Brassard and   
         Peter Hòyer and   
                     Alain Tapp   Quantum cryptanalysis of hash and
                                  claw-free functions  . . . . . . . . . . 14--19
                Joseph O'Rourke   Computational geometry column 31 . . . . 20--23
           John C. Mitchell and   
                  Jon G. Riecke   The analysis of programming structure    24--31
                  Jon G. Riecke   The Analysis of Programming Structure    24--31
                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 32--33
                 Zeke Zalcstein   NSF Report: Theory of Computing Program  34
                     Rocky Ross   Education Forum: Matter of Salesmanship  37--39
                Dorit S. Hochba   Approximation Algorithms for NP-Hard
                                  Problems . . . . . . . . . . . . . . . . 40--52
                  Ming-Yang Kao   Multiple-size divide-and-conquer
                                  recurrences  . . . . . . . . . . . . . . 67--69
                   A. E. Kostin   The novel algorithm for determining the
                                  reachability in acyclic Petri nets . . . 70--79
                   Leonid Levin   Errata to ``Fundamentals of Computing''  80
                   Rajeev Raman   Recent results on the single-source
                                  shortest paths problem . . . . . . . . . 81--87

ACM SIGACT News
Volume 28, Number 3, September, 1997

           Lane A. Hemaspaandra   SIGACT News complexity theory column 18  2--11
                Joseph O'Rourke   Computational geometry column 32 . . . . 12--16
      Z. Meral Özsoyo\uglu   Report on PODS'97  . . . . . . . . . . . 17--20
                   Yossi Matias   Parallel algorithms column: on the
                                  search for suitable models . . . . . . . 21--29
                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 30
                 Zeke Zalcstein   NSF report: theory of computing program  32
                  Samir Khuller   Open problems: 15  . . . . . . . . . . . 33--36
                William Gasarch   Book Review: \booktitleAn Introduction
                                  to Kolmogorov Complexity and its
                                  Applications Second Edition, 1997 by
                                  Ming Li and Paul Vitanyi (Springer
                                  (Graduate Text Series))  . . . . . . . . 37--40
                     Rocky Ross   Education forum: Where Have all the
                                  Women Gone?  . . . . . . . . . . . . . . 41--49
              Alfred V. Aho and   
           David S. Johnson and   
            Richard M. Karp and   
            S. Rao Kosaraju and   
       Catherine C. McGeoch and   
  Christos H. Papadimitriou and   
                  Pavel Pevzner   Emerging opportunities for theoretical
                                  computer science . . . . . . . . . . . . 65--74
                Anne Condon and   
                 Faith Fich and   
       Greg N. Frederickson and   
         Andrew V. Goldberg and   
           David S. Johnson and   
            Michael C. Loui and   
             Steven Mahaney and   
         Prabhakar Raghavan and   
             John E. Savage and   
             Alan L. Selman and   
                David B. Shmoys   Strategic directions in research in
                                  theory of computing  . . . . . . . . . . 75--93
                     Faith Fich   Infrastructure issues related to theory
                                  of computing research  . . . . . . . . . 94--99
             Oded Goldreich and   
                  Avi Wigderson   Theory of computing: a scientific
                                  perspective (extended abstract)  . . . . 100--102

ACM SIGACT News
Volume 28, Number 4, December, 1997

                  Eric Allender   Making computation count: arithmetic
                                  circuits in the nineties . . . . . . . . 2--15
                William Gasarch   The Book Review Column . . . . . . . . . 16
                      K. Puxang   Book Review: \booktitleMetamathematics,
                                  Machines, and Gödels Proof, by N. Shankar 16--19
             Alexander Dekhtyar   Book Review: \booktitleReasoning About
                                  Knowledge, by Ronald Fagin, Joseph
                                  Halpern, Yoram Moses and Moshe Verdi . . 20--23
             Christopher League   Book Review: \booktitleIsomorphisms of
                                  Types: From $ \lambda $-Calculus to
                                  Information Retrieval and Language
                                  Design, by Roberto Di Cosmo (Birkhäuser,
                                  1995)  . . . . . . . . . . . . . . . . . 24--27
                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 28--30
                 Zeke Zalcstein   NSF Report: Theory of Computing Program  31
                     Rocky Ross   Education Forum: Computer Science,
                                  Engineering, or Home Economics?  . . . . 37--40
                   Dan Gusfield   \booktitleAlgorithms on Strings, Trees,
                                  and Sequences: Computer Science and
                                  Computational Biology  . . . . . . . . . 41--60
                       Jie Wang   Report on the Third Annual International
                                  Computing and Combinatorics Conference
                                  (COCOON'97): Shanghai, China, August
                                  20--23, 1997 . . . . . . . . . . . . . . 69--76
            Bernard M. E. Moret   Workshop on algorithm engineering: a
                                  report . . . . . . . . . . . . . . . . . 77--79
             Luc Longpré   Report on Complexity 1997  . . . . . . . 80--83
                  Peter Schorer   Is a solution to the $ 3 x + 1 $ problem
                                  in sight?  . . . . . . . . . . . . . . . 90--93


ACM SIGACT News
Volume 29, Number 3, September, 1998

          Pankaj K. Agarwal and   
                Joseph O'Rourke   Computational geometry . . . . . . . . . 27--32

ACM SIGACT News
Volume 29, Number 1, March, 1998

                  Eric Allender   Book Review: \booktitleComplexity Theory
                                  Retrospective II. Edited by: Lane A.
                                  Hemaspaandra and Alan L. Selman
                                  (Springer Verlag)  . . . . . . . . . . . 2--5

ACM SIGACT News
Volume 29, Number 3, September, 1998

                    Anish Arora   Book Review: \booktitleVerification of
                                  Sequential and Concurrent Programs, by
                                  Krzysztof R. Apt and Ernst-Rüdiger
                                  Olderog (Springer-Verlag New York, 1997) 46--48
                    Gary Benson   Book Review: \booktitleAlgorithms on
                                  Strings, Trees, and Sequences: Computer
                                  Science and Computational Biology, by
                                  Dan Gusfield (Cambridge University
                                  Press, Cambridge, England, 1997) . . . . 43--46

ACM SIGACT News
Volume 29, Number 2, June, 1998

             Randeep Bhatia and   
              Yoram J. Sussmann   Book review: \booktitleApproximation
                                  Algorithms for NP-hard Problems. Edited
                                  by Dorit S. Hochbaum (PWS, 1997) . . . . 17--20

ACM SIGACT News
Volume 29, Number 3, September, 1998

                 Avrim Blum and   
             Prabhakar Raghavan   On a theory of computing symposia  . . . 104--111

ACM SIGACT News
Volume 29, Number 4, December, 1998

        Pierluigi Crescenzi and   
                     Viggo Kann   How to find the best approximation
                                  results  . . . . . . . . . . . . . . . . 90--97
             Alexander Dekhtyar   Book Review: \booktitleVicious Circles,
                                  by Jon Barwise and Lawrence Moss
                                  (Cambridge University Press 1996)  . . . 10--14

ACM SIGACT News
Volume 29, Number 1, March, 1998

                William Gasarch   The Book Review Column . . . . . . . . . 2

ACM SIGACT News
Volume 29, Number 2, June, 1998

                William Gasarch   The Book Review Column . . . . . . . . . 17

ACM SIGACT News
Volume 29, Number 3, September, 1998

                William Gasarch   The Book Review Column . . . . . . . . . 43

ACM SIGACT News
Volume 29, Number 4, December, 1998

                William Gasarch   The Book Review Column . . . . . . . . . 2--4


ACM SIGACT News
Volume 30, Number 1, March, 1999

                William Gasarch   The Book Review Column . . . . . . . . . 2


ACM SIGACT News
Volume 29, Number 4, December, 1998

                   Sanjay Gupta   Book Review: \booktitleTheories of
                                  Computability, by Nicholas Pippenger
                                  (Cambridge University Press 1997)  . . . 5--10

ACM SIGACT News
Volume 29, Number 2, June, 1998

           Lane A. Hemaspaandra   Take-home complexity . . . . . . . . . . 9--13

ACM SIGACT News
Volume 29, Number 3, September, 1998

         Edith Hemaspaandra and   
       Lane A. Hemaspaandra and   
                  Harald Hempel   What's up with downward collapse: using
                                  the easy-hard technique to link Boolean
                                  and polynomial hierarchy collapses . . . 10--22

ACM SIGACT News
Volume 29, Number 4, December, 1998

       Lane A. Hemaspaandra and   
                 Alan L. Selman   Writing and editing complexity theory:
                                  tales and tools  . . . . . . . . . . . . 20--27

ACM SIGACT News
Volume 29, Number 3, September, 1998

                     Andy Huang   Computation of the Knuth--Morris--Pratt
                                  skip tables  . . . . . . . . . . . . . . 59--61
                    Jerry James   Book Review: \booktitleAlgorithms and
                                  Programming: Problems and Solutions, by
                                  Alexander Shen (Birkhäuser Boston, 1997)  48--52

ACM SIGACT News
Volume 29, Number 2, June, 1998

                  Samir Khuller   Book Review: \booktitleSelected Papers
                                  on Computer Science, by Donald E. Knuth  21--26

ACM SIGACT News
Volume 29, Number 1, March, 1998

                  Samir Khuller   Open problems: 16  . . . . . . . . . . . 15--17
                   Neal Koblitz   Book Review: \booktitleDiscrete
                                  Mathematics in the Schools. Edited by
                                  Joseph G. Rosenstein, Deborah S.
                                  Franzblau, and Fred S. Roberts (American
                                  Mathematical Society)  . . . . . . . . . 8--12

ACM SIGACT News
Volume 29, Number 4, December, 1998

        Alexander E. Kostin and   
       Svetlana A. Tchoudaikina   Yet another reachability algorithm for
                                  Petri nets . . . . . . . . . . . . . . . 98--110

ACM SIGACT News
Volume 29, Number 3, September, 1998

             Harry R. Lewis and   
      Christos H. Papadimitriou   Elements of the Theory of Computation    62--78
             Luc Longpré   Report on Complexity 1998  . . . . . . . 92--93


ACM SIGACT News
Volume 30, Number 1, March, 1999

              Joseph Maklevitch   Book Review: \booktitlePrivacy on the
                                  Line, by Whitfield Diffie and Susan
                                  Landau (MIT Press 1998)  . . . . . . . . 6--8
           Timothy H. McNicholl   Book Review: \booktitleStable Marriage
                                  and its Relation to Other Combinatorial
                                  Problems: An Introduction to Algorithm
                                  Analysis, by Donald E. Knuth (American
                                  Mathematical Society 1996) . . . . . . . 2--4


ACM SIGACT News
Volume 29, Number 4, December, 1998

               Peter W. O'Hearn   Polymorphism, objects and abstract types 39--50

ACM SIGACT News
Volume 29, Number 2, June, 1998

                Joseph O'Rourke   Computational geometry column 33 . . . . 14--20
                   Ian Parberry   Everything you wanted to know about the
                                  running time of Mergesort but were
                                  afraid to ask  . . . . . . . . . . . . . 50--57

ACM SIGACT News
Volume 29, Number 3, September, 1998

                  Jan Paredaens   Database theory column: report on PODs
                                  '98  . . . . . . . . . . . . . . . . . . 23--26

ACM SIGACT News
Volume 29, Number 1, March, 1998

                   Brian Postow   Book Review: \booktitleBasic Simple Type
                                  Theory, by J. Roger Hindley (Cambridge
                                  University Press 1997) . . . . . . . . . 5--8


ACM SIGACT News
Volume 30, Number 1, March, 1999

                   Brian Postow   Book Review: \booktitleA Theory of
                                  Objects, by Martin Abadi and Luca
                                  Cardelli (Springer-Verlag, 1996):
                                  Series--Monographs in Computer Science   9--11


ACM SIGACT News
Volume 29, Number 1, March, 1998

                     Kirk Pruhs   How to design dynamic programming
                                  algorithms sans recursion  . . . . . . . 32--35
                     Rocky Ross   Education Forum: Reflections on Turning
                                  Fifty  . . . . . . . . . . . . . . . . . 21--31

ACM SIGACT News
Volume 29, Number 4, December, 1998

                     Rocky Ross   Education forum: Web Enhanced Textbooks  51--57

ACM SIGACT News
Volume 29, Number 3, September, 1998

                     Rocky Ross   Graduate degrees on the Web  . . . . . . 56--57

ACM SIGACT News
Volume 29, Number 2, June, 1998

                     Rocky Ross   Mathematics on the Web . . . . . . . . . 33--41

ACM SIGACT News
Volume 29, Number 4, December, 1998

                 John E. Savage   A new approach to the first theory
                                  course . . . . . . . . . . . . . . . . . 58--62

ACM SIGACT News
Volume 29, Number 1, March, 1998

                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 13--14

ACM SIGACT News
Volume 29, Number 2, June, 1998

                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 27--28

ACM SIGACT News
Volume 29, Number 3, September, 1998

                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 53--54

ACM SIGACT News
Volume 29, Number 4, December, 1998

                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 15--16


ACM SIGACT News
Volume 30, Number 1, March, 1999

                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 12--13


ACM SIGACT News
Volume 29, Number 2, June, 1998

                Rakesh K. Sinha   Technical report column  . . . . . . . . 30--32

ACM SIGACT News
Volume 29, Number 4, December, 1998

                      Dan Suciu   An overview of semistructured data . . . 28--38


ACM SIGACT News
Volume 30, Number 1, March, 1999

                 Vladimir Tasic   Book Review: \booktitleThe Limits of
                                  Mathematics, by G. J. Chaitin (Springer
                                  Verlag 1998) . . . . . . . . . . . . . . 5
               Heribert Vollmer   Uniform characterizations of complexity
                                  classes  . . . . . . . . . . . . . . . . 17--27


ACM SIGACT News
Volume 29, Number 3, September, 1998

             Dennis Volpano and   
                 Geoffrey Smith   Confinement properties for programming
                                  languages  . . . . . . . . . . . . . . . 33--42

ACM SIGACT News
Volume 29, Number 2, June, 1998

               Mark Allen Weiss   Data structures and problem solving
                                  using Java . . . . . . . . . . . . . . . 42--49


ACM SIGACT News
Volume 30, Number 1, March, 1999

                  Jon G. Riecke   Report on POPL 1999  . . . . . . . . . . 28--29
                     Rocky Ross   Education forum: Taking the Pulse:
                                  Assessing Student Perception of Learning 30--32
           Donald L. Kreher and   
             Douglas R. Stinson   Combinatorial algorithms: generation,
                                  enumeration, and search  . . . . . . . . 33--35
                      Paul Cull   Table-automata\slash finite co-finite
                                  languages  . . . . . . . . . . . . . . . 41

ACM SIGACT News
Volume 30, Number 2, June, 1999

                William Gasarch   The book review column . . . . . . . . . 2--2
                William Gasarch   Book Review: \booktitleAlgorithms and
                                  Theory of Computation Handbook, edited
                                  by Mikhail Atallah . . . . . . . . . . . 3--3
                William Gasarch   Book Review: \booktitleHandbook of
                                  Combinatorics (in two volumes), edited
                                  by R. L. Graham, M. Grötschel, L. Lovász   7--7
                  Danny Krizanc   Book Review: \booktitleProbabilistic
                                  Combinatorics and Its Applications,
                                  edited by Béla Bollobás  . . . . . . . . . 12--14
                    Jacob Lurie   Book Review: \booktitleSpectral Graph
                                  Theory: by Fan R. K. Chung . . . . . . . 14--16
                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 17--18
           Lane A. Hemaspaandra   Biomolecular computing: recent
                                  theoretical and experimental advances    22--30
                  Jon G. Riecke   Computational geometry column 35 . . . . 31--32
                 Hayo Thielecke   Continuations, Functions and Jumps . . . 33--42
                     Ricky Ross   Education forum  . . . . . . . . . . . . 43--46
                   Tomi Pasanen   Ph.D. Thesis: In-place algorithms for
                                  sorting problems . . . . . . . . . . . . 61--61

ACM SIGACT News
Volume 30, Number 3, September, 1999

            William Gasarch and   
                  Samir Khuller   The Book Review Column . . . . . . . . . 8
               Michael Dekhtyar   Book review: \booktitleComputational
                                  Geometry in C, Second Edition, by Joseph
                                  O'Rourke (Cambridge University Press
                                  1988)  . . . . . . . . . . . . . . . . . 8--13
                  Lance Fortnow   Book review: \booktitleBounded Queries
                                  in Recursion Theory, by William A.
                                  Gasarch and Georgia A. Martin
                                  (Birkhäuser. Boston, Basel, Berlin, 1999) 13--15
             Alexander Dekhtyar   Book Review: \booktitleLogic for
                                  Applications, Second Edition, by Anil
                                  Nerode and Richard A. Shore (Springer
                                  Verlag 1997) . . . . . . . . . . . . . . 15--18
                 Colin Stirling   Decidability of bisimulation equivalence
                                  for normed pushdown processes  . . . . . 19--21
                  Amnon Ta-Shma   Classical versus quantum communication
                                  complexity . . . . . . . . . . . . . . . 25--34
                Joseph O'Rourke   Computational geometry column 36 . . . . 35--38
            Erik D. Demaine and   
                Joseph O'Rourke   Computational geometry column 37 . . . . 39--42
                  Tao Jiang and   
               Paul Kearney and   
                        Ming Li   Some open problems in computational
                                  molecular biology  . . . . . . . . . . . 43--49
               Steven S. Skiena   Who is interested in algorithms and
                                  why?: lessons from the Stony Brook
                                  algorithms repository  . . . . . . . . . 65--74
                     Carl Smith   On the importance of refereeing  . . . . 75--76

ACM SIGACT News
Volume 30, Number 4, December, 1999

                William Gasarch   The Book Review Column . . . . . . . . . 3
         Chrystopher L. Nehaniv   Book Review: \booktitleMathematical
                                  Support for Molecular Biology, edited by
                                  Martin Farach-Colton, Fred S. Roberts,
                                  Martin Vingron, and Michael Waterman . . 4--7
          Mitsunori Ogihara and   
                    Animesh Ray   Book Review: \booktitleDNA Based
                                  Computers II, edited by Laura F.
                                  Landweber and Eric K. Baum . . . . . . . 7--9
                    Martyn Amos   Book Review: \booktitleDNA Based
                                  Computers III, edited by Harvey Rubin
                                  and David Harlan Wood  . . . . . . . . . 10--12
                  Neal E. Young   Book Review: \booktitleOnline
                                  Computation and Competitive Analysis, by
                                  Allan Borodin and Ran El-Yaniv . . . . . 13--17
                 Zeke Zalcstein   NSF report: theory of computing program  20--21
                David J. Haglin   Technical report column  . . . . . . . . 22--24
          Alina Beygelzimer and   
       Lane A. Hemaspaandra and   
       Christopher M. Homan and   
                Jörg Rothe   One-way functions in worst-case
                                  cryptography: algebraic and security
                                  properties are on the house  . . . . . . 25--40
                  Leonid Libkin   Query languages with arithmetic and
                                  constraint databases . . . . . . . . . . 41--50
                     Rocky Ross   Education Forum  . . . . . . . . . . . . 51--52
                Susan H. Rodger   Teaching automata theory with JFLAP  . . 53--56
       Catherine C. McGeoch and   
            Bernard M. E. Moret   How to present a paper on experimental
                                  work with algorithms . . . . . . . . . . 85--90
      Suresh Venkatasubramanian   A theory repository on the Web: a
                                  proposal . . . . . . . . . . . . . . . . 91--95


ACM SIGACT News
Volume 31, Number 1, March, 2000

                   Ian Parberry   Editor's Letter  . . . . . . . . . . . . 1
                William Gasarch   The Book Review Column . . . . . . . . . 2--3
                Maurice Herlihy   Book Review: \booktitleDistributed
                                  Computing, by Attiya and Welch . . . . . 3
                  Randall Pruim   Book Review: \booktitleHilbert's Tenth
                                  Problem, by Yttri Matiyasevich . . . . . 4
             Christopher League   Book Review: \booktitleLambda Calculi: A
                                  Guide for Computer Scientists, by Chris
                                  Hankin . . . . . . . . . . . . . . . . . 8--13
                     Carl Smith   Book Review: \booktitleSystems that
                                  Learn (second edition) by Jain,
                                  Osherson, Royer, Sharma  . . . . . . . . 12--13
                David J. Haglin   Technical Report Column  . . . . . . . . 14--15
                    Madhu Sudan   List decoding: algorithms and
                                  applications . . . . . . . . . . . . . . 16--27
                Joseph O'Rourke   Computational geometry column 38 . . . . 28--30
                 Martin Hofmann   Programming languages capturing
                                  complexity classes . . . . . . . . . . . 31--42
                     Rocky Ross   Education Forum  . . . . . . . . . . . . 43--48
           J. Järvinen and   
                     T. Pasanen   Two exercises  . . . . . . . . . . . . . 75--76
                   Ian Parberry   How to Present a Paper in Theoretical
                                  Computer Science: a Speaker's Guide for
                                  Students . . . . . . . . . . . . . . . . 77--86
              Publication years   The Book Review Column . . . . . . . . . 101

ACM SIGACT News
Volume 31, Number 2, June 1, 2000

                William Gasarch   The Book Review Column . . . . . . . . . 2
                  Danny Krizanc   Book Review: \booktitleGems of
                                  Theoretical Computer Science, by Uwe
                                  Schöning and Randall Pruim
                                  (Springer-Verlag, 1998)  . . . . . . . . 2--5
              Boris Goldengorin   Book Review: \booktitleNetwork Design:
                                  Connectivity and Facilities Location.
                                  Proceedings from DIMACS workshop in
                                  April 1997 (AMS 1998)  . . . . . . . . . 5--9
                William Gasarch   Book review: \booktitleIndiscrete
                                  Thoughts, by Gina-Carlo Rota (Birkhäuser,
                                  1996)  . . . . . . . . . . . . . . . . . 9--11
                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 12--13
               Ulrich Hertrampf   Algebraic acceptance mechanisms for
                                  polynomial time machines . . . . . . . . 22--33
                     Rocky Ross   Education forum  . . . . . . . . . . . . 34--38
                  Eric Allender   Report on the annual summer meeting of
                                  the New Zealand mathematics research
                                  institute  . . . . . . . . . . . . . . . 60--61
              Charles B. Dunham   Partially Wrong Completions  . . . . . . 69

ACM SIGACT News
Volume 31, Number 3, September, 2000

              Jeffery S. Vitter   ACM SIGACT 1999--2000 annual report  . . 2--6
                William Gasarch   The Book Review Column . . . . . . . . . 10
                 Judy Goldsmith   Book Review: \booktitleTheory of
                                  Computing: A Gentle Introduction, by
                                  Kinber and Smith (Prentice-Hall, 2001)   19--22
                   Hassan Masum   Book Review: \booktitleMicrosurveys in
                                  Discrete Probability, edited by David
                                  Aldous and James Propp. (AMS 1998) . . . 22--24
              Paliath Narendran   Book review: \booktitleTerm Rewriting
                                  and All That, by Franz Baader and Tobias
                                  Nipkow (Cambridge University Press, 313
                                  pages) . . . . . . . . . . . . . . . . . 24--26
                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 27--28
       Lane A. Hemaspaandra and   
         Christian Glaßer   A moment of perfect clarity I: the
                                  parallel census technique  . . . . . . . 37--42
                  Georg Gottlob   Report on PODS 2000  . . . . . . . . . . 43--46
                Joseph O'Rourke   Computational geometry column 39 . . . . 47--49
                     Rocky Ross   International efforts in computer
                                  science education  . . . . . . . . . . . 50--53
          Gregory C. Harfst and   
             Edward M. Reingold   A potential-based amortized analysis of
                                  the union-find data structure  . . . . . 86--95

ACM SIGACT News
Volume 31, Number 4, December, 2000

                William Gasarch   The Book Review Column . . . . . . . . . 3--4
                William Gasarch   Reviews of THREE books on Fair Division
                                  of Resources . . . . . . . . . . . . . . 4--10
                   Hassan Masum   Book Review: \booktitleComputational
                                  Geometry: Algorithms and Applications
                                  (2nd ed.) by Mark de Berg, Marc van
                                  Kreveld, Mark Overmars, and Otfried
                                  Schwarzkopf  . . . . . . . . . . . . . . 10--12
                Gabriel Istrate   Book Review: \booktitleParameterized
                                  Complexity, by R. Downey and M. Fellows  13--15
                    E. W. Cenek   Book Review: \booktitleModern Graph
                                  Theory, by Béla Bollobás . . . . . . . . . 15--18
              Vladik Kreinovich   Book Review: \booktitle$ A = B $, by
                                  Marko Petkov\vsek, Herbert S. Wilf, and
                                  Doron Zeilberger . . . . . . . . . . . . 18--24
               Riccardo Pucella   Book Review: \booktitleCommunicating and
                                  Mobile Systems: the $ \pi $-Calculus, by
                                  Robin Milner . . . . . . . . . . . . . . 24--26
                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 27
                  Dana Richards   NSF Report: Theory of Computing Program  37--38
     Christian Glaßer and   
           Lane A. Hemaspaandra   A moment of perfect clarity II:
                                  consequences of sparse sets hard for NP
                                  with respect to weak reductions  . . . . 39--51
                Sergio Rajsbaum   Principles of distributed computing: an
                                  exciting challenge . . . . . . . . . . . 52--61
                Joseph O'Rourke   Computational geometry column 40 . . . . 62--73
                     Rocky Ross   Going Backwards: Introductory
                                  Programming LAnguages  . . . . . . . . . 65--73
                   Ian Parberry   Report on the 6th international meeting
                                  on DNA-based computers . . . . . . . . . 118--120
                      Lila Kari   Half century of automata theory  . . . . 121--124
              Publication years   Death of a monster . . . . . . . . . . . 130--133


ACM SIGACT News
Volume 32, Number 1, March, 2001

                William Gasarch   The book review column . . . . . . . . . 2--3
                   Hassan Masum   Book Review: \booktitleData Structures
                                  and Algorithms in Java (2nd ed): Michael
                                  T Goodrich and Roberto Tamassia  . . . . 3--5
           Timothy H. McNicholl   A review of \booktitleSelected Papers on
                                  Analysis of Algorithms: by Donald E.
                                  Knuth  . . . . . . . . . . . . . . . . . 5--8
                   Hassan Masum   Book Review: \booktitleHow to Solve It:
                                  Modern Heuristics, by Zbigniew
                                  Michalewicz and David B. Fogel . . . . . 8--12
               Riccardo Pucella   Book Review: \booktitleProof, Language,
                                  and Interaction: Essays in Honour of
                                  Robin Milner, edited by Plotkin,
                                  Stirling and Tofte . . . . . . . . . . . 12--16
                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 17--18
           Lane A. Hemaspaandra   SIGACT news complexity theory column 31  21--31
                Sergio Rajsbaum   ACM SIGACT news distributed computing
                                  column 2 . . . . . . . . . . . . . . . . 32--32
                    Lisa Higham   Report on DISC'00  . . . . . . . . . . . 32--36
                 Cyril Gavoille   Routing in Distributed Networks:
                                  Overview and Open Problems . . . . . . . 36--52
                Joseph O'Rourke   Computational geometry column 41 . . . . 53--55
                     Rocky Ross   Education forum  . . . . . . . . . . . . 56--59
           John E. Hopcroft and   
             Rajeev Motwani and   
              Jeffrey D. Ullman   \booktitleIntroduction to Automata
                                  Theory, Languages, and Computation, 2nd
                                  edition  . . . . . . . . . . . . . . . . 60--65
                David Harel and   
               Dexter Kozen and   
                   Jerzy Tiuryn   Dynamic logic  . . . . . . . . . . . . . 66--69
           Michael Mitzenmacher   Challenging students with creative
                                  assignments  . . . . . . . . . . . . . . 70--73
           Michael Mitzenmacher   An experimental assignment on random
                                  processes  . . . . . . . . . . . . . . . 74--78
                   Steve Seiden   Can a computer proof be elegant? . . . . 111--114
              Vladik Kreinovich   Itanium's New Basic Operation of Fused
                                  Multiply-Add: Theoretical Explanation
                                  and Theoretical Challenge  . . . . . . . 115--117

ACM SIGACT News
Volume 32, Number 2, June, 2001

                William Gasarch   The book review column . . . . . . . . . 3--4
                William Gasarch   Book Review: \booktitleThe Codebreakers:
                                  the Story of Secret Writing, by David
                                  Kahn. Scribner . . . . . . . . . . . . . 5--6
                      Jim Reeds   Book Review: \booktitleThe Code Book:
                                  the Evolution of Secrecy from Mary Queen
                                  Of Scots to Quantum Cryptography, by
                                  Simon Singh. Anchor Books  . . . . . . . 6--11
              Mitsunori Ogihara   Book Review: \booktitleDNA Based
                                  Computers V, by Eric Winfree and David
                                  K. Gifford. American Mathematics Society 11--13
           Timothy H. McNicholl   Book Review: \booktitleComplexity and
                                  Real Computation, by Blum, Cucker, Shub,
                                  and Smale. Springer-Verlag . . . . . . . 14--15
                  Jeremy Avigad   Book Review: \booktitleBasic Proof
                                  Theory: second edition, by A. S.
                                  Troelstra and H. Schwichtenberg.
                                  Cambridge University Press . . . . . . . 15--19
                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 20--21
                  Samir Khuller   Algorithms column  . . . . . . . . . . . 28--31
           Lane A. Hemaspaandra   SIGACT News complexity theory column 32  32--43
                Sergio Rajsbaum   ACM SIGACT News distributed computing
                                  column 3 . . . . . . . . . . . . . . . . 44--45
                Idit Keidar and   
                Sergio Rajsbaum   On the cost of fault-tolerant consensus
                                  when there are no faults: preliminary
                                  version  . . . . . . . . . . . . . . . . 45--63
                     Rocky Ross   Molasses and theories of learning  . . . 64--71

ACM SIGACT News
Volume 32, Number 3, September 1, 2001

           Lane A. Hemaspaandra   Complexity theory  . . . . . . . . . . . 40--52
                Sergio Rajsbaum   Distributed Computing  . . . . . . . . . 53--62
      Joseph S. B. Mitchell and   
                Joseph O'Rourke   Computational geometry . . . . . . . . . 63--72

ACM SIGACT News
Volume 32, Number 4, December, 2001

                William Gasarch   The book review column . . . . . . . . . 2--5
                William Gasarch   Book Review: \booktitleProofs and
                                  Refutations, by Imre Lakatos . . . . . . 6--8
               Riccardo Pucella   Book Review: \booktitleDynamic Logic
                                  (Foundations of Computing), by D. Harel,
                                  D. Kozen and J. Tiuryn . . . . . . . . . 9--17
        Christopher G. Jennings   Book Review: \booktitleAnalysis of
                                  Algorithms: An Active Learning Approach,
                                  by Jeffrey J. McConnell  . . . . . . . . 17--18
           Lane A. Hemaspaandra   SIGACT news complexity theory column 34  24--33
                Sergio Rajsbaum   ACM SIGACT news distributed computing
                                  column 5 . . . . . . . . . . . . . . . . 34--58
                     Rocky Ross   Education forum  . . . . . . . . . . . . 59--65
       Lane A. Hemaspaandra and   
              Mitsunori Ogihara   The complexity theory companion  . . . . 66--68


ACM SIGACT News
Volume 33, Number 1, March, 2002

                William Gasarch   The book review column . . . . . . . . . 3--20
                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 21--22
                   Robert Sloan   NSF report: theory of computing program  28--28
           Lane A. Hemaspaandra   SIGACT news complexity theory column 35  32--45
                Sergio Rajsbaum   ACM SIGACT news Distributed Computing
                                  Column 6 . . . . . . . . . . . . . . . . 46--53
                     Ted Herman   Self-stabilization at WSS'01 and DISC'01 54--57
                Joseph O'Rourke   Computational geometry column 43 . . . . 58--60
                     Rocky Ross   Accountability and the public trust  . . 61--66
            Henry Hamburger and   
                  Dana Richards   Logic and language models for computer
                                  science  . . . . . . . . . . . . . . . . 67--70
                Jeffrey Shallit   The computational complexity of the
                                  local postage stamp problem  . . . . . . 90--94

ACM SIGACT News
Volume 33, Number 2, June, 2002

                William Gasarch   The book review column . . . . . . . . . 2--9
           Boleslaw Mikolajczak   Book Review: \booktitlePetri Net Algebra 10--14
                  Ivelin Ivanov   Book Review: \booktitleCombinatorial
                                  Optimization --- Theory and Algorithms   14--16
            Marios Mavronicolas   Book Review: \booktitleIntroduction to
                                  Distributed Algorithms . . . . . . . . . 16--18
                William Gasarch   Book Review: \booktitleCalculated Bets   19--20
                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 21--23
                   Robert Sloan   NSF report: theory of computing program  27--28
                David J. Haglin   Technical report column  . . . . . . . . 29--30
                  Samir Khuller   Algorithms column: the vertex cover
                                  problem  . . . . . . . . . . . . . . . . 31--33
           Lane A. Hemaspaandra   SIGACT news complexity theory column 36  34--47
                Sergio Rajsbaum   ACM SIGACT news distributed computing
                                  column 7 . . . . . . . . . . . . . . . . 48--51
               Seth Gilbert and   
                    Nancy Lynch   Brewer's conjecture and the feasibility
                                  of consistent, available,
                                  partition-tolerant Web services  . . . . 51--59
             Rajmohan Rajaraman   Topology control and routing in ad hoc
                                  networks: a survey . . . . . . . . . . . 60--73
               Scott Ferson and   
               Lev Ginzburg and   
          Vladik Kreinovich and   
         Luc Longpré and   
                  Monica Aviles   Computing Variance for Interval Data is
                                  NP-Hard  . . . . . . . . . . . . . . . . 108--118

ACM SIGACT News
Volume 33, Number 3, September, 2002

                William Gasarch   The book review column . . . . . . . . . 6--6
              R. Gregory Taylor   Modern computer algebra  . . . . . . . . 7--16
                    E. W. Cenek   Computability and complexity theory and
                                  the complexity theory companion  . . . . 17--19
              P. Daniel Hestand   Mathematical theory of domains . . . . . 19--22
                  Joel Seiferas   Reprints from \booktitleComputing
                                  Reviews  . . . . . . . . . . . . . . . . 23--24
           Lane A. Hemaspaandra   SIGACT news complexity theory comun 37   32--49
                Sergio Rajsbaum   ACM SIGACT news distributed computing
                                  column 8 . . . . . . . . . . . . . . . . 50--50
                 Henri Casanova   Distributed computing research issues in
                                  grid computing . . . . . . . . . . . . . 50--70
                     Rocky Ross   Space wars and other things  . . . . . . 71--74
        Vijay Shivshanker Gupta   Communication complexity for file
                                  synchronization is undecidable . . . . . 110--112

ACM SIGACT News
Volume 33, Number 4, December, 2002

                William Gasarch   The book review column . . . . . . . . . 4--5
                William Gasarch   Bioinformatics: the machine learning
                                  approach . . . . . . . . . . . . . . . . 5--8
                    Maulik Dave   Book Review: \booktitleThe Clausal
                                  Theory of Types  . . . . . . . . . . . . 8--9
      Suresh Venkatasubramanian   Discrete mathematical problems with
                                  medical applications DIMACS volume 55    9--11
                  Ivelin Ivanov   Parallel processing and parallel
                                  algorithms: theory and computation . . . 12--14
                   Ian Parberry   Things a computer scientist rarely talks
                                  about  . . . . . . . . . . . . . . . . . 14--15
                   Hassan Masum   Book Review: \booktitleA New Kind of
                                  Science  . . . . . . . . . . . . . . . . 15--21
           Lane A. Hemaspaandra   SIGACT news complexity theory column 38  22--36
                Sergio Rajsbaum   ACM SIGACT news distributed computing
                                  column 9 . . . . . . . . . . . . . . . . 37--54


ACM SIGACT News
Volume 34, Number 1, March, 2003

                William Gasarch   The book review column . . . . . . . . . 3--3
              Prodromos Saridis   Book Review: \booktitleNumber Theory for
                                  Computing  . . . . . . . . . . . . . . . 4--5
           Riccardo Pucella and   
                  Stephen Chong   Book Review: \booktitleType-Logical
                                  Semantics  . . . . . . . . . . . . . . . 6--17
           Lane A. Hemaspaandra   Book Review: \booktitleThe $ \pi
                                  $-Calculus: a Theory of Mobile Processes 17--24
                Sergio Rajsbaum   Partial information classes  . . . . . . 32--46
                     Rocky Ross   Deconstructing Paxos . . . . . . . . . . 47--67
                     Rocky Ross   Teaching (and research) squeezed . . . . 68--77
                  Xiaofei Huang   A polynomial-time algorithm for solving
                                  NP-hard problems in practice . . . . . . 101--108

ACM SIGACT News
Volume 34, Number 2, June, 2003

                William Gasarch   The book review column . . . . . . . . . 2--2
                Anthony Widjaja   Book Review: \booktitleAlgorithms
                                  Sequential & Parallel: a Unified
                                  Approach, by R. Miller & L. Boxer.
                                  Prentice Hall 2000 . . . . . . . . . . . 3--5
                   Hassan Masum   Book Review: \booktitleAlgorithmics for
                                  Hard Problems: Introduction to
                                  Combinatorial Optimization,
                                  Randomization, Approximation, and
                                  Heuristics, by Juraj Hromkovic. Springer
                                  2001 . . . . . . . . . . . . . . . . . . 6--8
                 Vicky Weissman   Book Review: \booktitleModal and
                                  Temporal Properties of Processes, by
                                  Colin Stirling. Springer Verlag 2001 . . 8--15
              P. Daniel Hestand   Book Review: \booktitleModal Logic:
                                  Cambridge tracts in theoretical computer
                                  science #53 by Patrick Blackburn,
                                  Maarten de Rijke, and Yde Venema.
                                  Cambridge University Press 2001  . . . . 15--19
           Lane A. Hemaspaandra   SIGACT news complexity theory column 40  27--41
                Sergio Rajsbaum   ACM SIGACT news distributed computing
                                  column 11  . . . . . . . . . . . . . . . 42--57
                Joseph O'Rourke   Computational geometry column 44 . . . . 58--60
              Josh Cogliati and   
                     Rocky Ross   Mathematics on the Web: part II  . . . . 61--68
                       B. Litow   The Hamiltonian circuit problem and
                                  automaton theory . . . . . . . . . . . . 91--94

ACM SIGACT News
Volume 34, Number 3, September, 2003

                William Gasarch   The book review column . . . . . . . . . 3--4
                Robert J. Irwin   Book Review: \booktitleSet Theory for
                                  Computing: From Decision Procedures to
                                  Declarative Programming with Sets, by
                                  Domenico Cantone, Eugenio Omodeo and
                                  Alberto Policriti. Springer-Verlag 2001  4--11
                    E. W. Cenek   Book Review: \booktitleTheory of
                                  Computational Complexity, by Ding-Zhu Du
                                  and Ker-I Ko. John Wiley & Sons . . . . . 11--12
       George A. Constantinides   Book Review: \booktitleComputer
                                  Arithmetic Algorithms, by Israel Koren.
                                  A.K. Peters  . . . . . . . . . . . . . . 13--15
                Andrea Marchini   Book Review: \booktitleAn Introduction
                                  to Quantum Computing Algorithms, by
                                  Arthur O. Pittenger. Birkhäuser 2000  . . 16--18
           Lane A. Hemaspaandra   SIGACT News complexity theory column 41  26--39
                Sergio Rajsbaum   ACM SIGACT News distributed computing
                                  column 12  . . . . . . . . . . . . . . . 40--61
                     Rocky Ross   Education forum  . . . . . . . . . . . . 62--67
           Steven S. Skiena and   
              Miguel A. Revilla   Programming challenges: the programming
                                  contest training manual  . . . . . . . . 68--74
                  K. Alagarsamy   Some myths about famous mutual exclusion
                                  algorithms . . . . . . . . . . . . . . . 94--103

ACM SIGACT News
Volume 34, Number 4, December, 2003

                Donald E. Knuth   Robert W Floyd, In Memoriam  . . . . . . 3--13
                William Gasarch   The book review column . . . . . . . . . 14--15
                  Andrew C. Lee   Book Review: \booktitleIntroduction to
                                  Cryptography, by Johannes A. Buchmann.
                                  Springer Verlag, 2001  . . . . . . . . . 15--17
                Robert J. Irwin   Book Review: \booktitleCoding Theory and
                                  Cryptography: the Essentials, second
                                  edition, revised and expanded by D.R.
                                  Hankerson, et al. Marcel Dekker, 2000    17--21
         William M. Springer II   Book Review: \booktitleCryptography:
                                  Theory and Practice, second edition by
                                  Douglas R. Stinson. CRC Press  . . . . . 22--25
               Riccardo Pucella   Joint review of \booktitleFoundations of
                                  Cryptography: Basic Tools, by O.
                                  Goldreich. Cambridge University Press,
                                  and \booktitleModelling and Analysis of
                                  Security Protocols, by P. Ryan and S.
                                  Schneider. Addison Wesley  . . . . . . . 26--31
                  Andrew C. Lee   Book Review: \booktitleModern
                                  Cryptography, Probabilistic Proofs and
                                  Pseudorandomness Algorithms and
                                  Combinatorics, vol 17, by Oded
                                  Goldreich. Springer Verlag, 1999 . . . . 32--34
             E. Böhler and   
                N. Creignou and   
                   S. Reith and   
                     H. Vollmer   Playing with Boolean blocks, part I:
                                  Post's lattice with applications to
                                  complexity theory  . . . . . . . . . . . 38--52
           Lane A. Hemaspaandra   SIGACT news complexity theory column 42  38--52
                Sergio Rajsbaum   ACM SIGACT news distributed computing
                                  column 13  . . . . . . . . . . . . . . . 53--56
                 Ravi Kumar and   
               Ronitt Rubinfeld   Algorithms column: sublinear time
                                  algorithms . . . . . . . . . . . . . . . 57--67
                     Ricky Ross   SIGACT news online algorithms column 1   68--77
                     Rocky Ross   Education forum  . . . . . . . . . . . . 78--83


ACM SIGACT News
Volume 35, Number 1, March, 2004

             William I. Gasarch   The book review column . . . . . . . . . 3--4
                Dan A. Simovici   Book Review: \booktitleThe Classical
                                  Decision Problem, by Egon Börger, Erich
                                  Grädel and Yuri Gurevich. Springer-Verlag
                                  1997 . . . . . . . . . . . . . . . . . . 4--7
           Lawrence S. Moss and   
           Hans-Jörg Tiede   Book Review: \booktitleAutomata Theory
                                  and its Applications, by Bakhadyr
                                  Khoussainov and Anil Nerode. Birkhäuser
                                  Boston, Inc. 2001.: and
                                  \booktitleAutomata, Logics, and Infinite
                                  Games, by E. Grädel, W. Thomas, and T.
                                  Wilke. Springer-Verlag . . . . . . . . . 8--12
                   Jean Berstel   Book Review: \booktitleAutomatic
                                  Sequences: Theory, Applications,
                                  Generalizations, by Jean-Paul Allouche
                                  and Jeffrey Shallit. Cambridge
                                  University Press . . . . . . . . . . . . 12--16
             E. Böhler and   
                N. Creignou and   
                   S. Reith and   
                     H. Vollmer   Playing with Boolean blocks, part II:
                                  constraint satisfaction problems . . . . 22--35
           Lane A. Hemaspaandra   SIGACT news complexity theory column 43  22--35
                  Marek Chrobak   SIGACT news online algorithms column 2   38--48
                     Rocky Ross   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 and   
               Michael Peck and   
                    David Evans   Pancakes, puzzles, and polynomials:
                                  cracking the Cracker Barrel  . . . . . . 80--84

ACM SIGACT News
Volume 35, Number 2, June, 2004

             William I. Gasarch   The book review column . . . . . . . . . 3--4
                 Sabina Petride   Book Review: \booktitleConcurrent and
                                  Real-Time Systems: the CSP Approach, by
                                  Steve Schneider. Wiley 1999  . . . . . . 4--12
              Robert McNaughton   Book Review: \booktitleIntroduction to
                                  Languages, Machines and Logic:
                                  Computable Languages, Abstract Machines
                                  and Formal Logic, by Alan P. Parkes.
                                  Springer-Verlag 2002 . . . . . . . . . . 13--14
            Pavol Návrat   Book Review: \booktitleAlgorithm Design:
                                  Foundations, Analysis and Internet
                                  Examples, by Michael T. Goodrich and
                                  Roberto Tamassia. John Wiley & Sons, Inc.
                                  2001 . . . . . . . . . . . . . . . . . . 14--16
                  Lance Fortnow   Book Review: \booktitleTheory 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
                  Samir Khuller   A pleasant stroll through the land of
                                  infinitely many creatures  . . . . . . . 36--59
      Jittat Fakcharoenphol and   
                 Satish Rao and   
                   Kunal Talwar   Approximating metrics by tree metrics    60--70
                Joseph O'Rourke   Approximating metrics by tree metrics    60--70
                  Marek Chrobak   Computational geometry column 45 . . . . 71--73
                Joseph O'Rourke   Computational geometry column 45 . . . . 71--73
                  Marek Chrobak   A princess swimming in the fog looking
                                  for a monster cow  . . . . . . . . . . . 74--78
                     Rocky Ross   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

ACM SIGACT News
Volume 35, Number 3, September, 2004

             William I. Gasarch   Book Review: \booktitleHandbook of Graph
                                  Theory, edited by Gross and Yellen. CRC,
                                  2004 . . . . . . . . . . . . . . . . . . 5--8
                  Wenzhong Zhao   Book Review: \booktitleReasoning about
                                  Uncertainty, by Joseph Y. Halpern. The
                                  MIT Press, 2003  . . . . . . . . . . . . 8--12
                   Luc T. Wille   Book Review: \booktitleLearning Kernel
                                  Classifiers: Theory and Algorithms, by
                                  Ralf Herbrich. MIT Press, Cambridge,
                                  Mass., 2002. ISBN 0-262-08306-X, 384
                                  pages; and \booktitleLearning with
                                  Kernels: Support Vector Machines,
                                  Regularization Optimization and Beyond
                                  by Bernhard Scholkopf and Alexander J.
                                  Smola. MIT Press, Cambridge, Mass.,
                                  2002, ISBN 0-262-19475-9, 644 pages  . . 13--17
                Carlos Oliveira   Book Review: \booktitleEssentials 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   Guest column: error-correcting codes and
                                  expander graphs  . . . . . . . . . . . . 25--41
                Joseph O'Rourke   Computational geometry column 46 . . . . 42--45
                Sergio Rajsbaum   Computational geometry column 46 . . . . 42--45
                  Marek Chrobak   ACM SIGACT news distributed computing
                                  column 15  . . . . . . . . . . . . . . . 46--57
                Sergio Rajsbaum   ACM SIGACT news distributed computing
                                  column 15  . . . . . . . . . . . . . . . 46--57
                  Marek Chrobak   SIGACT news online algorithms column 4   58--66
                     Rocky Ross   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 and   
              Nikolay V. Shilov   Etude on theme of Dijkstra . . . . . . . 102--108

ACM SIGACT News
Volume 35, Number 4, December, 2004

             William I. Gasarch   The book review column . . . . . . . . . 4--5
              R. Gregory Taylor   Book Review: \booktitleBoolean Functions
                                  and Computation Models, by Peter Clote
                                  and Evangelos Kranakis, Springer-Verlag,
                                  2002 . . . . . . . . . . . . . . . . . . 5--11
          Carlos A. S. Oliveira   Book Review: \booktitleSelected Papers
                                  on Discrete Mathematics, by D. Knuth,
                                  CSLI (Center for the Study of Language
                                  and Information Publication) paperback,
                                  \$72.00} . . . . . . . . . . . . . . . . 11--14
          Carlos A. S. Oliveira   Book Review: \booktitleLinear
                                  Optimization and Extensions --- Problems
                                  and Solutions, by Dimitris Alevras and
                                  Manfred Padberg, Springer-Verlag, 450
                                  pages, \$54.95}  . . . . . . . . . . . . 15--18
                  William Fahle   Book Review: \booktitleIntroduction to
                                  the Design and Analysis of Algorithms,
                                  by Ananay Levitin, Addison-Wesley  . . . 18--19
            Bruno Codenotti and   
        Sriram V. Pemmaraju and   
         Kasturi R. Varadarajan   The computation of market equilibria . . 23--37
                Sergio Rajsbaum   The computation of market equilibria . . 23--37
                Sergio Rajsbaum   ACM SIGACT news distributed computing
                                  column 16  . . . . . . . . . . . . . . . 38--38
                Sergio Rajsbaum   Larry Stockmeyer: 1948--2004 . . . . . . 39--39
                  Marek Chrobak   Distributed approximation: a survey  . . 40--57
                  Michael Elkin   Distributed approximation: a survey  . . 40--57
              Marek Chrobak and   
              Elias Koutsoupias   Coordination mechanisms for congestion
                                  games  . . . . . . . . . . . . . . . . . 58--71
               Riccardo Pucella   Coordination mechanisms for congestion
                                  games  . . . . . . . . . . . . . . . . . 58--71
               Riccardo Pucella   Specifying confidentiality . . . . . . . 72--83
          Pim van den Broek and   
                   Joost Noppen   Comparison of two approaches to dynamic
                                  programming  . . . . . . . . . . . . . . 111--116
                Harry B. Coonce   Computer science and the mathematics
                                  genealogy project  . . . . . . . . . . . 117--117
              S. O. Shilova and   
              Nikolay V. Shilov   Addendum to Etude on theme of Dijkstra   118--118


ACM SIGACT News
Volume 36, Number 1, March, 2005

             William I. Gasarch   Book Review: \booktitleProofs that
                                  Really Count: The Art of Combinatorial
                                  Proof, by Arthur T. Benjamin and
                                  Jennifer J. Quinn; MAA, 2003 . . . . . . 12--14
                   Mats Kindahl   Book Review: \booktitleTypes and
                                  Programming Languages, by Benjamin C.
                                  Pierce; The MIT Press, 2002  . . . . . . 15--20
               Lawrence S. Moss   Joint review of \booktitleIntroduction
                                  To Natural Computation, by Dana H.
                                  Ballard; MIT Press, 1997, ISBN
                                  0-262-52258-6 and \booktitleMathematical
                                  Methods in Artificial Intelligence, by
                                  Edward A. Bender, IEEE Press, 1996, ISBN
                                  0-8186-7200-5  . . . . . . . . . . . . . 21--24
                 Scott Aaronson   Guest Column: NP-complete problems and
                                  physical reality . . . . . . . . . . . . 30--52
                Sergio Rajsbaum   Guest Column: NP-complete problems and
                                  physical reality . . . . . . . . . . . . 30--52
                  Marek Chrobak   A short introduction to failure
                                  detectors for asynchronous distributed
                                  systems  . . . . . . . . . . . . . . . . 53--70
                      M. Raynal   A short introduction to failure
                                  detectors for Asynchronous Distributed
                                  Systems  . . . . . . . . . . . . . . . . 53--70
                  Michel Reynal   A short introduction to failure
                                  detectors for asynchronous distributed
                                  systems  . . . . . . . . . . . . . . . . 53--70
                 Wojciech Jawor   Three dozen papers on online algorithms  71--85
               Riccardo Pucella   Three dozen papers on online algorithms  71--85
               Riccardo Pucella   The finite and the infinite in temporal
                                  logic  . . . . . . . . . . . . . . . . . 86--99
          Dror G. Feitelson and   
               Ahuva W. Mu'alem   On the Definition of ``On-Line'' in Job
                                  Scheduling Problems  . . . . . . . . . . 122--131
                 Antti Ylikoski   The halting problem on finite and
                                  infinite computers . . . . . . . . . . . 132--138

ACM SIGACT News
Volume 36, Number 2, June, 2005

             William I. Gasarch   The book review column . . . . . . . . . 3--4
             William I. Gasarch   Book Review: \booktitleCryptological
                                  Mathematics, by Robert Lewand; MAA,
                                  2000, \$33.95, Softcover}  . . . . . . . 4--7
          Nikolaos Papanikolaou   Book Review: \booktitleData Privacy and
                                  Security, by David Salomon;
                                  Spring-Verlag, 2003, \$51.48, Hardcover} 8--13
                  Jonathan Katz   Comparative book review:
                                  \booktitleCryptography: An Introduction,
                                  by V. V. Yaschenko (American
                                  Mathematical Society, 2002);
                                  \booktitleCryptanalysis of Number
                                  Theoretic Ciphers, by S. S. Wagstaff,
                                  Jr. (Chapman & Hall/CRC Press, 2003);
                                  \booktitleRSA and Public-Key
                                  Cryptography, by R. A. Mollin (Chapman &
                                  Hall/CRC Press, 2003);
                                  \booktitleFoundations of Cryptography,
                                  vol. 1: Basic Tools, by O. Goldreich,
                                  (Cambridge University Press, 2001) . . . 14--19
                   Subhash Khot   Guest column: inapproximability results
                                  via Long Code based PCPs . . . . . . . . 25--42
                  Samir Khuller   Guest column: inapproximability results
                                  via Long Code based PCPs . . . . . . . . 25--42
                  Samir Khuller   Four colors suffice! . . . . . . . . . . 43--44
                Sergio Rajsbaum   Four colors suffice! . . . . . . . . . . 43--44
                  Marek Chrobak   Algorithmic foundations of the Internet  45--62
   Alejandro López-Ortiz   Algorithmic foundations of the internet  45--62
                Sandy Irani and   
                     Kirk Pruhs   Algorithmic problems in power management 63--76
               Riccardo Pucella   Algorithmic problems in power management 63--76
               Riccardo Pucella   Logical verification and equational
                                  verification . . . . . . . . . . . . . . 77--88
               Ulisses Ferreira   The sets of real and complex numbers are
                                  denumerable  . . . . . . . . . . . . . . 126--130
                      Y. C. Tay   What should computer science students
                                  learn from mathematics?  . . . . . . . . 131--143

ACM SIGACT News
Volume 36, Number 3, September, 2005

             William I. Gasarch   The book review column . . . . . . . . . 4--5
          Nikolaos Papanikolaou   Book Review: \booktitleClassical and
                                  Quantum Computing with C++ and Java
                                  Simulations, by Yorick Hardy and
                                  Willi-Hans Steeb, Birkhäuser Verlag, 2001 5--9
             E. Jonathan Chapin   Book Review: \booktitleInteger
                                  Programming, by Laurence A. Wolsey,
                                  Wiley and Sons 1998  . . . . . . . . . . 10--12
                     Georg Essl   Book Review: \booktitleComputational
                                  Line Geometry, by H. Pottmann and J.
                                  Wallner, Springer Verlag, 2001 . . . . . 13--17
               Riccardo Pucella   Book Review: \booktitleLogic for
                                  Computer Scientists, by Uwe Schöning,
                                  Birkhäuser, 1994  . . . . . . . . . . . . 17--19
                    James Glenn   Book Review: \booktitleTeaching
                                  Statistics Using Baseball, by Jim
                                  Albert, MAA, 2003  . . . . . . . . . . . 19--21
              Lane Hemaspaandra   Technical report column  . . . . . . . . 22--23
                    Dean Kelley   Technical report column  . . . . . . . . 22--23
           Lane A. Hemaspaandra   SIGACT news complexity theory column 48  24--38
                   Victor Viann   SIGACT news complexity theory column 48  24--38
                 Foto N. Afrati   Report on PODS 2005  . . . . . . . . . . 39--40
                Sergio Rajsbaum   Report on PODS 2005  . . . . . . . . . . 39--40
               Riccardo Pucella   ACM SIGACT news distributed computing
                                  column 19  . . . . . . . . . . . . . . . 41--50
                Sergio Rajsbaum   ACM SIGACT news distributed computing
                                  column 19  . . . . . . . . . . . . . . . 41--50
                  Marek Chrobak   SIGACT news logic column 13  . . . . . . 51--66
               Riccardo Pucella   SIGACT news logic column 13  . . . . . . 51--66
                  Marek Chrobak   SIGACT news online algorithms column 8   67
              Reza Dorrigiv and   
   Alejandro López-Ortiz   A Survey of Performance Measures for
                                  On-line Algorithms . . . . . . . . . . . 67--81
                     Rocky Ross   SIGACT news online algorithms column 8   67--81
                     Rocky Ross   Education forum: trying again with
                                  MathML . . . . . . . . . . . . . . . . . 82--84
                     Rocky Ross   Textbooks  . . . . . . . . . . . . . . . 84--93
          Vladik Kreinovich and   
             Luc Longpré   Kolmogorov complexity leads to a
                                  representation theorem for idempotent
                                  probabilities (sigma-maxitive measures)  107--112
              Amir M. Ben-Amram   The Church--Turing thesis and its
                                  look-alikes  . . . . . . . . . . . . . . 113--114

ACM SIGACT News
Volume 36, Number 4, December, 2005

             William I. Gasarch   The book review column . . . . . . . . . 4--5
                 Maulik A. Dave   Book Review: \booktitleData Structures,
                                  Near Neighbor Searches, and Methodology:
                                  Fifth and Sixth DIMACS Implementation
                                  Challenge, by Michael H. Goldwasser,
                                  David S. Johnson, Catherine C. McGeoch,
                                  American Mathematical Society 2002 . . . 5--8
                    Raymond Wan   Book Review: \booktitleGenomic Perl From
                                  Bioinformatics Basics to Working Code,
                                  by Rex A. Dwyer, Cambridge University
                                  Press 2003, 0-521-80177-X  . . . . . . . 9--12
                  William Fahle   Book Review: \booktitleGraphs, Networks,
                                  and Algorithms (second edition) by
                                  Dieter Jungnickel, Springer-Verlag 2005  12--14
                  Wenzhong Zhao   Book Review: \booktitleImmunocomputing:
                                  Principles and Applications, by
                                  Alexander O. Tarakanov, Victor A.
                                  Skormin, Svetlana P. Sokolova,
                                  Springer-Verlag New York, Inc. 2003  . . 14--17
Frédéric Loulergue   Book Review: \booktitleTerm Rewriting
                                  Systems, by Terese, Cambridge University
                                  Press 2003, 0-521-39115-6  . . . . . . . 17--20
           Lane A. Hemaspaandra   SIGACT news complexity theory column 49  24--35
                Sergio Rajsbaum   ACM SIGACT news distributed computing
                                  column 20  . . . . . . . . . . . . . . . 36--46
               Riccardo Pucella   SIGACT news logic column 14  . . . . . . 47--69
                     Rocky Ross   Education forum  . . . . . . . . . . . . 70--71
             Evgeny Dantsin and   
          Vladik Kreinovich and   
              Alexander Wolpert   On quantum versions of record-breaking
                                  algorithms for SAT . . . . . . . . . . . 103--108
     Isaiah Pinchas Kantorovitz   A note on Turing machine computability
                                  of rule driven systems . . . . . . . . . 109--110
                Tim Roughgarden   An interview with Vladimir Trifonov 2005
                                  Danny Lewin Best Student Paper Award
                                  winner . . . . . . . . . . . . . . . . . 111--114


ACM SIGACT News
Volume 37, Number 1, March, 2006

             William I. Gasarch   The book review column . . . . . . . . . 9--11
                  Jonathan Katz   Book Review: \booktitleA Computational
                                  Introduction to Number Theory and
                                  Algebra, by Victor Shoup, Cambridge
                                  University Press, 2005 . . . . . . . . . 12--13
                  Jonathan Katz   Book Review: \booktitlePrimality Testing
                                  in Polynomial Time, by Martin
                                  Dietzfelbinger, Springer-Verlag, 2004    14--15
         William M. Springer II   Book Review: \booktitleIntroduction to
                                  Coding Theory, by Juergen Bierbrauer,
                                  Chapman and Hall/CRC, 2005, ISBN
                                  1-58488-421-5  . . . . . . . . . . . . . 16--18
                    Adam Bender   Book Review: \booktitleCodes: The Guide
                                  to Secrecy from Ancient to Modern Times,
                                  by Richard A. Mollin, Chapman & Hall/CRC,
                                  2005 . . . . . . . . . . . . . . . . . . 18--21
          Carlos A. S. Oliveira   Book Review: \booktitleComputational
                                  Complexity: a Quantitative Perspective,
                                  by Marius Zimand, Elsevier, ISBN
                                  0-444-82841-9  . . . . . . . . . . . . . 21--25
                 Maulik A. Dave   Book Review: \booktitleSecure
                                  Communicating Systems: Design, analysis,
                                  and implementation, by Michael R. A.
                                  Huth, Cambridge University Press, 2001   26--27
                Pierre Lescanne   Book Review: \booktitleAlfred Tarski:
                                  Life and Logic, by Anita Burdman
                                  Feferman and Solomon Feferman, Cambridge
                                  University Press 2004  . . . . . . . . . 27--28
                    Dean Kelley   Technical report column  . . . . . . . . 29--32
                  Samir Khuller   Technical report column  . . . . . . . . 29--32
              Lane Hemaspaandra   Approximation algorithms for $2$-stage
                                  stochastic optimization problems . . . . 33--46
            Chaitanya Swamy and   
                David B. Shmoys   Algorithms Column: Approximation
                                  algorithms for $2$-stage stochastic
                                  optimization problems  . . . . . . . . . 33--46
          Piotr Faliszewski and   
           Lane A. Hemaspaandra   Open questions in the theory of
                                  semifeasible computation . . . . . . . . 47--65
                Sergio Rajsbaum   Open questions in the theory of
                                  semifeasible computation . . . . . . . . 47--65
                  Marek Chrobak   Travelling through wormholes: a new look
                                  at distributed systems models  . . . . . 66--81
         Paulo Veríssimo   Travelling through wormholes: a new look
                                  at distributed systems models  . . . . . 66--81
                  Marek Chrobak   2005: an offline persepctive . . . . . . 82--98

ACM SIGACT News
Volume 37, Number 2, June, 2006

             William I. Gasarch   The book review column . . . . . . . . . 10--12
                    Varsha Dani   Book Review: \booktitleFair Division and
                                  Collective Welfare, by Hervé Moulin, MIT
                                  Press, 2003  . . . . . . . . . . . . . . 12--17
             William Schmeister   Book Review: \booktitleAlgorithms:
                                  Sequential, Parallel, and Distributed,
                                  by Kenneth A. Berman and Jerome L. Paul,
                                  Thomson Course Technology, 2005  . . . . 17--22
             Anthony Widjaja To   Book Review: \booktitleAlgebraic
                                  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--31
                 Oded Goldreich   Guest Column: Bravely, Moderately --- a
                                  Common Theme in Four Recent Works  . . . 31--46
                Joseph O'Rourke   Computational geometry column 47 . . . . 47--49
                Sergio Rajsbaum   Computational geometry column 47 . . . . 47--49
               Riccardo Pucella   ACM SIGACT news distributed computing
                                  column 22  . . . . . . . . . . . . . . . 50--56
                Sergio Rajsbaum   ACM SIGACT news distributed computing
                                  column 22  . . . . . . . . . . . . . . . 50--56
               Riccardo Pucella   SIGACT news logic column 15  . . . . . . 57--57
                 Alexander Kurz   Coalgebras and their logics  . . . . . . 57--77

ACM SIGACT News
Volume 37, Number 3, September, 2006

             William I. Gasarch   The book review column . . . . . . . . . 14--17
             William I. Gasarch   A joint review of \booktitleReality
                                  Conditions: Short Mathematical Fiction,
                                  by Alex Kasman, MAA 2005;
                                  \booktitleNumb3rs, TV show. CBS, Free.
                                  Currently running Fridays at 10:00PM;
                                  \booktitleMathematical Apocryphia:
                                  Stories and Anecdotes of Mathematicians
                                  and the Mathematical, by Steven Kranz,
                                  MAA, 2002; \booktitleMathematical
                                  Apocryphia Redux: More Stories and
                                  Anecdotes of Mathematicians and the
                                  Mathematical, by Steven Kranz, MAA, 1999 17--19
                    Brian Blank   A Joint Review of \booktitleA History of
                                  Pi, by Petr Beckmann, St. Martins's
                                  Press, 1976, Barnes and Noble Books,
                                  1989; \booktitleThe Joy of Pi, by David
                                  Blatner, Walker & Co., 1997;
                                  \booktitleThe Nothing That Is, by Robert
                                  Kaplan, Oxford University Press, 1999;
                                  \booktitle$e$: The Story of a Number, by
                                  Eli Maor, Princeton University Press,
                                  1998; \booktitleAn Imaginary Tale, by
                                  Paul Nahin, Princeton University Press,
                                  1998; \booktitleZero: The Biography of a
                                  Dangerous Idea, by Charles Seife, Viking
                                  Press, 2000  . . . . . . . . . . . . . . 19--26
         William I. Gasarch and   
          Alexander Kruskal and   
             Justin Kruskal and   
                Rebecca Kruskal   Book Review: \booktitleThe Square Root
                                  of 2: A Dialogue Concerning a Number and
                                  a Sequence, by David Flannery,
                                  Copernicus Books, 2006 . . . . . . . . . 27--32
              Lane Hemaspaandra   Technical report column  . . . . . . . . 33--35
                    Dean Kelley   Technical report column  . . . . . . . . 33--35
           Lane A. Hemaspaandra   SIGACT news complexity theory column 52  36--54
                Joseph O'Rourke   SIGACT news complexity theory column 52  36--54
                Joseph O'Rourke   Computational geometry column 48 . . . . 55--57
                Sergio Rajsbaum   Computational geometry column 48 . . . . 55--57
                Idit Keidar and   
                 Assaf Schuster   Want scalable computing?: speculate! . . 59--66
                    Ran Canetti   Security and composition of
                                  cryptographic protocols: a tutorial
                                  (part I) . . . . . . . . . . . . . . . . 67--92
               Riccardo Pucella   Security and composition of
                                  cryptographic protocols: a tutorial
                                  (Part I) . . . . . . . . . . . . . . . . 67--92
                 Karl Crary and   
                  Robert Harper   Higher-order abstract syntax: setting
                                  the record straight  . . . . . . . . . . 93--96
          Vladik Kreinovich and   
                      Max Shpak   Aggregability is NP-hard . . . . . . . . 97--104

ACM SIGACT News
Volume 37, Number 4, December, 2006

            Pavel Pudlák   Gödel and computations: a 100th
                                  anniversary retrospective  . . . . . . . 13--21
            Joan Feigenbaum and   
           Michael Mitzenmacher   Towards a theory of networked
                                  computation  . . . . . . . . . . . . . . 22--26
             William I. Gasarch   The book review column . . . . . . . . . 27--29
                   Mats Kindahl   Book Review: \booktitleTypes and
                                  Programming Languages, by Benjamin C.
                                  Pierce, MIT Press, 2002  . . . . . . . . 29--34
                 Maulik A. Dave   Book Review: \booktitleVerification of
                                  Reactive Systems: Formal Methods and
                                  Algorithms, by Klaus Schneider,
                                  Springer-Verlag Berlin Heidelberg, 2004  36--37
                      James Law   Book Review: \booktitleAlgorithmic
                                  Learning in a Random World, by Vovk,
                                  Gammerman and Shafer, Springer, 2005,
                                  ISBN 0-387-00152-2 . . . . . . . . . . . 38--40
             Aravind Srinivasan   Book Review: \booktitleThe 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
            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 and   
          Claire Kenyon-Mathieu   SIGACT news online algorithms column 10:
                                  competitiveness via doubling . . . . . . 115--126


ACM SIGACT News
Volume 38, Number 1, March, 2007

                William Gasarch   The joys of being an NSF program
                                  director . . . . . . . . . . . . . . . . 7--8
                Robert H. Sloan   The joys of being an NSF program
                                  director . . . . . . . . . . . . . . . . 7--8
             William I. Gasarch   Book Review: \booktitleExcellence
                                  Without a Soul: How a Great University
                                  Forgot Education, by Harry Lewis, Public
                                  Affairs, 290 pages . . . . . . . . . . . 9--13
                 Ronald de Wolf   Joint review of \booktitleAn
                                  Introduction to Quantum Computing
                                  Algorithms, by Arthur O. Pittenger,
                                  Birkhäuser, ISBN 0-8176-4127-0;
                                  \booktitleQuantum Computing, by Mika
                                  Hirvensalo, Springer, ISBN
                                  3-540-66783-0; and \booktitleClassical
                                  and Quantum Computation, by A. Yu.
                                  Kitaev, A. Shen, and M. N. Vyalyi,
                                  American Mathematical Society, ISBN
                                  0-8218-2161-X  . . . . . . . . . . . . . 14--17
                 Jonathan Cohen   Book Review: \booktitleIntroduction to
                                  Lattices and Order, by B. A. Davey and
                                  H. A. Priestley, Cambridge University
                                  Press  . . . . . . . . . . . . . . . . . 17--23
              Vladik Kreinovich   Book Review: \booktitleComputational
                                  Techniques for the Summation of Series,
                                  by Anthony Sofo, Kluwer Academic
                                  Publishers, 2003 . . . . . . . . . . . . 24--27
           Lane A. Hemaspaandra   Technical report column  . . . . . . . . 28--30
                    Dean Kelley   Technical report column  . . . . . . . . 28--30
                  Jiong Guo and   
               Rolf Niedermeier   Invitation to data reduction and problem
                                  kernelization  . . . . . . . . . . . . . 31--45
                Sergio Rajsbaum   Invitation to data reduction and problem
                                  kernelization  . . . . . . . . . . . . . 31--45
                   Shlomi Dolev   A review of the DISC 2006 conference . . 46--52
    Bernadette Charron-Bost and   
           André Schiper   Harmful dogmas in fault tolerant
                                  distributed computing  . . . . . . . . . 53--61
  Alexander (Sasha) A. Razborov   Eulogy: Michael (Misha) Alekhnovich
                                  1978--2006 . . . . . . . . . . . . . . . 70--71

ACM SIGACT News
Volume 38, Number 2, June, 2007

             William I. Gasarch   The book review column . . . . . . . . . 8--10
              James C. Beaumont   Book Review: \booktitleSymbolic
                                  Asymptotics, by John R. Shackell,
                                  Springer Verlag, 243 pages, \$79.95} . . 11--16
                Jörg Rothe   Book Review: \booktitleComplexity and
                                  Cryptography: An Introduction, by John
                                  Talbot and Dominic Welsh, Cambridge
                                  University Press, 2006, 292 pages  . . . 16--20
              Piotr Faliszewski   Book Review: \booktitleComplexity Theory
                                  and Cryptology: An Introduction to
                                  Cryptocomplexity, by Jörg Rothe,
                                  Springer, 2005, 484 pages  . . . . . . . 20--22
             William I. Gasarch   Joint review of \booktitleThree Blogs by
                                  Theorists: Computational Complexity (\tt
                                  weblog.fortnow.com), by Lance Fortnow,
                                  \booktitleShtetl-Optimized (\tt
                                  www.scottaaronson.com/blog/), by Scott
                                  Aaronson, \booktitleIn theory (\tt
                                  in-theory.blogspot.com) by Luca Trevisan 23--25
           Lane A. Hemaspaandra   Technical report column  . . . . . . . . 26--28
                    Dean Kelley   Technical report column  . . . . . . . . 26--28
             Debajyoti Bera and   
             Frederic Green and   
                   Steven Homer   Small depth quantum circuits . . . . . . 35--50
                Joseph O'Rourke   Computational geometry column 49 . . . . 51--55
      Paolo A. G. Sivilotti and   
                  Scott M. Pike   A collection of kinesthetic learning
                                  activities for a course on distributed
                                  computing: ACM SIGACT news distributed
                                  computing column 26  . . . . . . . . . . 56--74
               Riccardo Pucella   Alternative Logics: a book review:
                                  SIGACT news logic column 18  . . . . . . 75--86
                  Robin K. Hill   How close did Kurt Gödel get to the
                                  University of Wyoming? . . . . . . . . . 87--90

ACM SIGACT News
Volume 38, Number 3, September, 2007

             William I. Gasarch   The book review column . . . . . . . . . 14--16
               Rajesh Natarajan   Book Review: \booktitleThe Political
                                  Mapping of Cyberspace, by Jeremy W.
                                  Crampton, The University of Chicago
                                  Press, 2003  . . . . . . . . . . . . . . 17--20
                  Jonathan Katz   Book Review: \booktitleProbability and
                                  Computing: Randomized Algorithms and
                                  Probabilistic Analysis, by Michael
                                  Mitzenmacher and Eli Upfal, Cambridge
                                  University Press, 2005 . . . . . . . . . 20--22
            Yannis C. Stamatiou   Book Review: \booktitleProbability and
                                  Computing: Randomized Algorithms and
                                  Probabilistic Analysis, by Michael
                                  Mitzenmacher and Eli Upfal, Cambridge
                                  University Press, 2005 . . . . . . . . . 22--27
                 Brian Borchers   Book Review: \booktitleComputational
                                  Techniques of the Simplex Method, by
                                  István Maros, Kluwer Academic Publishers,
                                  2003 . . . . . . . . . . . . . . . . . . 27--30
                    Dean Kelley   Technical report column  . . . . . . . . 31--33
           Lane A. Hemaspaandra   Introduction . . . . . . . . . . . . . . 34--38
                Salil P. Vadhan   The unified theory of pseudorandomness:
                                  guest column . . . . . . . . . . . . . . 39--54
                Sergio Rajsbaum   Introduction . . . . . . . . . . . . . . 55--55
           Markus Jakobsson and   
                   Steven Myers   Delayed password disclosure  . . . . . . 56--75
               Riccardo Pucella   Introduction . . . . . . . . . . . . . . 76--76
           Alessio Lomuscio and   
               Wojciech Penczek   Symbolic model checking for
                                  temporal-epistemic logics  . . . . . . . 77--99
                  Marek Chrobak   Competitiveness via primal-dual  . . . . 100--105
                  Samir Khuller   Introduction . . . . . . . . . . . . . . 106--106
                Chandra Chekuri   Routing and network design with
                                  robustness to changing or uncertain
                                  traffic demands  . . . . . . . . . . . . 106--129

ACM SIGACT News
Volume 38, Number 4, December, 2007

             William I. Gasarch   The book review column . . . . . . . . . 16--18
                 Scott Aaronson   Book Review: \booktitleThe Access
                                  Principle, by John Willinsky, MIT Press,
                                  2005 . . . . . . . . . . . . . . . . . . 19--23
             William I. Gasarch   Book Review: \booktitleA Century of
                                  Scientific Publishing: A collection of
                                  essays, edited by Fredriksson, IOS Press 23--24
                 Frederic Green   Book Review: \booktitleMathematics of
                                  Physics and Engineering, by Edward K.
                                  Blum and Sergey V. Lototsky, World
                                  Scientific . . . . . . . . . . . . . . . 25--30
             William I. Gasarch   Book Review: \booktitleResearch Problems
                                  in Discrete Geometry, by Brass, Moser,
                                  Pach, Springer-Verlag  . . . . . . . . . 31--34
                    Dean Kelley   Technical report column  . . . . . . . . 35--38
           Lane A. Hemaspaandra   Introduction . . . . . . . . . . . . . . 39--40
              Arnaud Durand and   
          Clemens Lautemann and   
                    Malika More   A simple proof of the polylog counting
                                  ability of first-order logic: guest
                                  column . . . . . . . . . . . . . . . . . 40--45
                    Idit Keidar   Introduction . . . . . . . . . . . . . . 46--49
               Edward Bortnikov   Review of DISC '07 . . . . . . . . . . . 49--53
               Michael Kuhn and   
              Roger Wattenhofer   The theoretic center of computer science 54--63
               Riccardo Pucella   Introduction . . . . . . . . . . . . . . 64--64
                   Simon Kramer   Logical concepts in cryptography . . . . 65--66


ACM SIGACT News
Volume 39, Number 1, March, 2008

             William I. Gasarch   The book review column . . . . . . . . . 9--12
                       S. Terai   Book Review: \booktitleCryptography in C
                                  and C++, by Michael Welschenbach,
                                  Apress, 2005 . . . . . . . . . . . . . . 12--16
                 James V. Rauff   Book Review: \booktitleA Beginner's
                                  Guide to Discrete Mathematics, by W. D.
                                  Wallis, Birkhäuser, 2003  . . . . . . . . 16--18
         Lawrence C. Washington   Book Review: \booktitleHandbook of
                                  Elliptic and Hyperelliptic Curve
                                  Cryptography, by H. Cohen and G. Frey,
                                  Chapman & Hall/CRC, 2006, 1-58488-518-1   19--22
                  Danny Krizanc   Book Review: \booktitleThe Game's Afoot:
                                  Game Theory in Myth and Paradox, by
                                  Alexander Mehlmann, American
                                  Mathematical Society, 2000,
                                  0-8218-2121-0  . . . . . . . . . . . . . 22--24
         William M. Springer II   Book Reviews: \booktitleIntroducing Game
                                  Theory and Its Applications, by Elliott
                                  Mendelson, CRC Press, and \booktitleGame
                                  Theory and Strategy, by Philip D.
                                  Straffin, MAA Press  . . . . . . . . . . 24--27
                 Maulik A. Dave   Book Review: \booktitleSemantic
                                  Integration of Heterogeneous Software
                                  Specifications, by Martin Große-Rhode,
                                  Springer-Verlag, 2004  . . . . . . . . . 28--29
           Lane A. Hemaspaandra   Technical report column  . . . . . . . . 30--32
                    Dean Kelley   Technical report column  . . . . . . . . 30--32
           Jonathan F. Buss and   
          Tarique Mesbaul Islam   The complexity of fixed-parameter
                                  problems: guest column . . . . . . . . . 33--46
                    Idit Keidar   The complexity of fixed-parameter
                                  problems: guest column . . . . . . . . . 33--46
                    Idit Keidar   ACM SIGACT News Distributed Computing
                                  Column 29  . . . . . . . . . . . . . . . 47--48
              Pascal Felber and   
            Christof Fetzer and   
           Rachid Guerraoui and   
                     Tim Harris   Transactions are back---but are they the
                                  same?: \booktitleLe Retour de Martin
                                  Guerre (Sommersby) . . . . . . . . . . . 48--58
                   Hagit Attiya   Needed: foundations for transactional
                                  memory . . . . . . . . . . . . . . . . . 59--61
            Maurice Herlihy and   
               Victor Luchangco   Distributed computing and the multicore
                                  revolution . . . . . . . . . . . . . . . 62--72
                Joseph O'Rourke   Computational geometry column 50 . . . . 73--76
                  Marek Chrobak   Database theory column . . . . . . . . . 77--79
                   Victor Vianu   Database theory column . . . . . . . . . 77--79
       Benjamin E. Birnbaum and   
                 Claire Mathieu   On-line bipartite matching made simple   80--87

ACM SIGACT News
Volume 39, Number 2, June, 2008

             Gagan Aggarwal and   
                  Nir Ailon and   
          Florin Constantin and   
              Eyal Even-Dar and   
                Jon Feldman and   
            Gereon Frahling and   
     Monika Rauch Henzinger and   
           S. Muthukrishnan and   
                 Noam Nisan and   
          Martin Pál and   
               Mark Sandler and   
        Anastasios Sidiropoulos   Theory research at Google  . . . . . . . 10--28
                William Gasarch   Theory research at Google  . . . . . . . 10--28
             William I. Gasarch   The book review column . . . . . . . . . 29--31
                 John D. Rogers   Book Review: \booktitleThe Art of
                                  Computer Programming, Volume 4,
                                  Fascicles 2, 3, and 4, by Donald E.
                                  Knuth, Pearson Education
                                  (Addison-Wesley), 2005 . . . . . . . . . 32--35
                 Timothy Kelley   Book Review: \booktitleA Course in
                                  Computational Algebraic Number Theory,
                                  by Henri Cohen, Springer, 2000 . . . . . 36--39
              Richard Jankowski   Book Review: \booktitleFoundations of
                                  Computer Security, by David Salomon,
                                  Springer-Verlag, 2006  . . . . . . . . . 40--41
                Robert J. Irwin   Book Review: \booktitleDerivation and
                                  Computation: Taking the Curry--Howard
                                  Correspondence Seriously, by Harold
                                  Simmons, Cambridge University Press,
                                  2000 . . . . . . . . . . . . . . . . . . 42--44
                 Maulik A. Dave   Book Review: \booktitleTheoretical and
                                  Experimental DNA Computation, by M.
                                  Amos, Springer-Verlag Berlin Heidelberg,
                                  2005 . . . . . . . . . . . . . . . . . . 45--46
                    Dean Kelley   Technical report column  . . . . . . . . 47--49
           Lane A. Hemaspaandra   SIGACT news complexity theory column 59:
                                  introduction . . . . . . . . . . . . . . 50--50
                     Jin-yi Cai   Holographic algorithms: guest column . . 51--81
                    Idit Keidar   On distributed computing principles in
                                  systems research: introduction . . . . . 82--83
                  Allen Clement   Distributed computing in SOSP and OSDI   84--91
               Roy Friedman and   
       Anne-Marie Kermarrec and   
                  Michel Raynal   Modularity: a first class concept to
                                  address distributed systems  . . . . . . 91--110
                   Victor Vianu   Modularity: a first class concept to
                                  address distributed systems  . . . . . . 91--110
                      Dan Suciu   Probabilistic databases  . . . . . . . . 111--124

ACM SIGACT News
Volume 39, Number 3, September, 2008

                  Brian Borcher   Book Review: \booktitleCombinatorial
                                  Optimization: Packing and Covering, by
                                  Gérard Cornuéjols  . . . . . . . . . . . . 16--18
      Bernd S. W. Schröder   Book Review: \booktitleOrdered Sets: An
                                  Introduction . . . . . . . . . . . . . . 18--21
              Jonathan A. Cohen   Joint review of \booktitleGeneral
                                  Lattice Theory (second edition) and
                                  \booktitleThe Congruences of a Finite
                                  Lattice: a Proof-by-Picture Approach, by
                                  George Grätzer  . . . . . . . . . . . . . 22--26
            George Grätzer   A brief response to J. A. Cohen's joint
                                  review . . . . . . . . . . . . . . . . . 26--28
                 Maulik A. Dave   Book Review: \booktitleApplied
                                  Combinatorics on Words . . . . . . . . . 28--30
  Ganesh Lalitha Gopalakrishnan   Review computation engineering: applied
                                  automata theory and logic  . . . . . . . 30--32
                    Dean Kelley   Technical report column  . . . . . . . . 33--34
                 Oded Goldreich   Computational complexity: a conceptual
                                  perspective  . . . . . . . . . . . . . . 35--39
           Lane A. Hemaspaandra   Research Notices: The injectivity of the
                                  global function of a cellular automaton
                                  in the hyperbolic plane is undecidable   40--40
            Maurice Margenstern   Research Notices: The injectivity of the
                                  global function of a cellular automaton
                                  in the hyperbolic plane is undecidable   40
                     Irit Dinur   PCPs with small soundness error  . . . . 41--57
                Joseph O'Rourke   Computational geometry column 51 . . . . 58--62
             Maurizio Lenzerini   Database theory column: report on PODS
                                  2008 . . . . . . . . . . . . . . . . . . 63--65
                    Idit Keidar   ACM SIGACT News Distributed Computing
                                  Column 31: quantum computers meet
                                  distributed computing  . . . . . . . . . 66--66
             Anne Broadbent and   
                     Alain Tapp   Can quantum mechanics help distributed
                                  computing? . . . . . . . . . . . . . . . 67--76
           Vasil S. Denchev and   
              Gopal Pandurangan   Distributed quantum computing: a new
                                  frontier in distributed systems or
                                  science fiction? . . . . . . . . . . . . 77--95
                  Marek Chrobak   SIGACT news online algorithms column 13:
                                  2007 --- an offine perspective . . . . . 96--121

ACM SIGACT News
Volume 39, Number 4, December, 2008

                William Gasarch   The book review column . . . . . . . . . 15--17
             Douglas R. Stinson   Combinatorial designs: constructions and
                                  analysis . . . . . . . . . . . . . . . . 17--21
      Miklós Bóna   Combinatorics of permutations  . . . . . 21--25
   Charalambos A. Charalambides   Enumerative combinatorics  . . . . . . . 25--27
       Brittany Terese Fasy and   
               David L. Millman   Book Review: \booktitleGeometric Algebra
                                  for Computer Science, by Leo Dorst,
                                  Daniel Fontijne, and Stephen Mann
                                  (Morgan Kaufmann Publishers, 2007) . . . 27--30
              Richard Jankowski   Book Review: \booktitlePrivacy on the
                                  Line: The Politics of Wiretapping and
                                  Encryption, by Whitfield Diffie and
                                  Susan Landau . . . . . . . . . . . . . . 30--32
                    Dean Kelley   Technical report column  . . . . . . . . 33--34
           Lane A. Hemaspaandra   SIGACT news complexity theory column 61  35--36
                  Ryan Williams   Applying practice to theory  . . . . . . 37--52
                    Idit Keidar   ACM SIGACT news distributed computing
                                  column 32: the year in review  . . . . . 53--54
       Armando Castañeda   A review of PODC 2008  . . . . . . . . . 55--59
               Robert Danek and   
             Wojciech Golab and   
            Wojciech Wawrzyniak   Review of DISC 2008  . . . . . . . . . . 60--65
                      Zvika Guz   Review of SPAA'08  . . . . . . . . . . . 66--68
                  Gabriel Kliot   Review of DSN'08 . . . . . . . . . . . . 69--73


ACM SIGACT News
Volume 40, Number 1, March, 2009

                William Gasarch   The book review column . . . . . . . . . 8--10
                William Gasarch   Book Review: \booktitleBlown to Bits:
                                  Your Life, Liberty, and Happiness After
                                  the Digital Explosion, by Hal Abelson,
                                  Ken Ledeen, and Harry Lewis (Addison
                                  Wesley, 2008)  . . . . . . . . . . . . . 10--13
                 S. C. Coutinho   Book Review: \booktitleSolving
                                  Polynomial Equation Systems II:
                                  Macaulay's Paradigm and Gröbner
                                  Technology, by Teo Mora (Cambridge
                                  University Press 2005) . . . . . . . . . 14--17
                    Brent Smith   Book Review: \booktitleHow to Prove It:
                                  a Structured Approach, by Daniel J.
                                  Velleman (Cambridge University Press,
                                  2006)  . . . . . . . . . . . . . . . . . 18--20
                 Brian Borchers   Book Review: \booktitlePractical
                                  Optimization: Algorithms and Engineering
                                  Applications, by Andreas Antoniou and
                                  Wu-Sheng Lu (Springer Verlag, 2007)  . . 20--22
                William Gasarch   Book Review: \booktitleRock, Paper,
                                  Scissors: Game Theory for Everyday Life,
                                  by Len Fisher (Basic Books, 2008)  . . . 22--23
                    Dean Kelley   Technical report column  . . . . . . . . 24--25
           Lane A. Hemaspaandra   SIGACT news complexity theory column 62  26--26
                 Emanuele Viola   Guest Column: correlation bounds for
                                  polynomials over $ \{ 0, 1 \} $  . . . . 27--44
                    Idit Keidar   ACM SIGACT news distributed computing
                                  column 33 teaching concurrency . . . . . 45--46
                  Danny Hendler   Book Review: \booktitleSynchronization
                                  Algorithms and Concurrent Programming,
                                  by Gadi Taubenfeld (Pearson/Prentice
                                  Hall, 2006)  . . . . . . . . . . . . . . 47--50
                 Alan D. Fekete   Teaching about threading: where and
                                  what?  . . . . . . . . . . . . . . . . . 51--57
                 Leslie Lamport   Teaching concurrency . . . . . . . . . . 58--62

ACM SIGACT News
Volume 40, Number 2, June, 2009

                William Gasarch   The book review column . . . . . . . . . 10--13
Kyriakos N. Kyriakos N. Sgarbas   Book Review: \booktitleHow to Think
                                  about Algorithms, by Je Edmonds
                                  (Cambridge University Press, 2008) . . . 13--17
                    Dean Kelley   Book Review: \booktitleA Programmer's
                                  Companion to Algorithm Analysis, by
                                  Ernst Leiss (Chapman & Hall/CRC, 2007)    18--22
                    Dean Kelley   Joint review of \booktitleAlgorithms, by
                                  Richard Johnsonbaugh and Marcus Schaefer
                                  (Pearson/Prentice-Hall, 2004) and
                                  \booktitleAlgorithms by Sanjoy Dasgupta,
                                  Christos Papadimitriou and Umesh
                                  Vazirani (McGraw-Hill, 2008) . . . . . . 23--25
            Marios Mavronicolas   Book Review: \booktitleDesign and
                                  Analysis of Randomized Algorithms:
                                  Introduction to Design Paradigms, by
                                  Juraj Hromkovic (Published by Springer)  25--27
                  Jakub Marecek   Book Review: \booktitleTheoretical
                                  Aspects of Local Search, by Wil P. A. J.
                                  Michiels, Emile H. L. Aarts, and Jan H.
                                  M. Korst (Springer in the EATCS Series
                                  Monographs in Theoretical Computer
                                  Science, 007)  . . . . . . . . . . . . . 27--30
         William M. Springer II   Book Review: \booktitleThe Traveling
                                  Salesman Problem: a Computational Study,
                                  by Applegate, Bixby, Chvátal, and Cook
                                  (Princeton University Press) . . . . . . 30--32
                  Alice M. Dean   Book Review: \booktitleVisibility
                                  Algorithms in the Plane, by Subir Kumar
                                  Ghosh (Cambridge University Press, 2007) 33--35
                    Elisa Schae   Book Review: \booktitleA Course on the
                                  Web Graph, by Anthony Bonato (American
                                  Mathematical Society, Providence, Rhode
                                  Island, USA) . . . . . . . . . . . . . . 35--37
       Brittany Terese Fasy and   
               David L. Millman   Book Review: \booktitleHigher
                                  Arithmetic: an Algorithmic Introduction
                                  to Number Theory, by H. M. Edwards
                                  (American Mathematical Society Student
                                  Mathematical Library Vol. 45, 2008)  . . 38--41
                    Dean Kelley   Technical report column  . . . . . . . . 42--44
                    R. Demontis   A simple NP-hard problem . . . . . . . . 45--48
           Lane A. Hemaspaandra   SIGACT news complexity theory column 63  49--49
                  Luca Trevisan   Guest column: additive combinatorics and
                                  theoretical computer science . . . . . . 50--66
                    Idit Keidar   ACM SIGACT news distributed computing
                                  column 34: distributed computing in the
                                  clouds . . . . . . . . . . . . . . . . . 67--67
                 Ken Birman and   
           Gregory Chockler and   
            Robbert van Renesse   Toward a cloud computing research agenda 68--80
           Christian Cachin and   
                Idit Keidar and   
               Alexander Shraer   Trusting the cloud . . . . . . . . . . . 81--86
               Edward Bortnikov   Open-source grid technologies for
                                  web-scale computing  . . . . . . . . . . 87--93
                Roger Barga and   
        Jose Bernabeu-Auban and   
              Dennis Gannon and   
             Christophe Poulain   Cloud computing architecture and
                                  application programming: DISC'09
                                  tutorial, half day, Sept. 22nd 2009  . . 94--95

ACM SIGACT News
Volume 40, Number 3, September, 2009

                William Gasarch   The book review column . . . . . . . . . 21--24
                William Gasarch   Book Review: \booktitleThe Mathematical
                                  Coloring Book: Mathematics of Coloring
                                  and the Colorful Life of Its Creators,
                                  by Alexander Soifer  . . . . . . . . . . 24--31
                William Gasarch   Joint review of \booktitleProfessor
                                  Stewart's Cabinet of Mathematical
                                  Curiosities, by Ian Stewart and
                                  \booktitleFive Minute Mathematics, by
                                  Ehrhard Behrends and \booktitleAha
                                  Gotcha!-Aha Insight! by Martin Gardner
                                  and \booktitleOrigami, Eleusis, and the
                                  Soma Cube, by Martin Gardner and
                                  \booktitleHexaexagons, Probability
                                  Paradoxes, and the Tower of Hanoi, by
                                  Martin Gardner and \booktitleGroup
                                  Theory in the Bedroom and Other
                                  Mathematical Diversions, by Brian Hayes  32--37
      Miklós Bóna   Book Review: \booktitleCombinatorics and
                                  Graph Theory: (second edition) by John
                                  M. Harris, Jeffry L. Hirst and Michael
                                  J. Mossinghoff . . . . . . . . . . . . . 37--39
      Miklós Bóna   Book Review: \booktitleAlgorithmic
                                  Combinatorics on Partial Words, by
                                  Francine Blanchet-Sadri  . . . . . . . . 39--41
                  Adel El-Atawy   Book Review: \booktitleAn Introduction
                                  to Difference Equations: third edition
                                  by Saber Elaydi  . . . . . . . . . . . . 42--46
      Miklós Bóna   Book Review: \booktitleRandom Graphs:
                                  (second edition) by Béla Bollobás  . . . . 46--48
                    Eowyn Cenek   Chases and escapes by Paul J. Nahin  . . 48--50
                    Dean Kelley   Technical report column  . . . . . . . . 51--52
                 Oded Goldreich   On our duties as scientists  . . . . . . 53--59
           Lane A. Hemaspaandra   SIGACT news complexity theory column 64  60--76
                    Idit Keidar   ACM SIGACT news distributed computing
                                  column 35: theory and practice in large
                                  distributed systems  . . . . . . . . . . 77--77
                    Lidong Zhou   Building reliable large-scale
                                  distributed systems: when theory meets
                                  practice . . . . . . . . . . . . . . . . 78--85
                  Marek Chrobak   SIGACT news online algorithms column 14  86--98

ACM SIGACT News
Volume 40, Number 4, December, 2009

                William Gasarch   The book review column . . . . . . . . . 8--10
                  George Hacken   Quantum computation and quantum
                                  communication: theory and experiments
                                  Author of book: Mladen Pavicic . . . . . 10--14
                 S. C. Coutinho   Book Review: \booktitleQuantum Computing
                                  for Computer Scientists, by Noson S.
                                  Yanofsky and Mirco A. Mannucci,
                                  Cambridge University Press, 2008 . . . . 14--17
                   Brad G. Kyer   Book Review: \booktitleBiologically
                                  Inspired Algorithms for Financial
                                  Modelling, by Anthony Brabazon, Michael
                                  O'Neill Springer-Verlag Berlin
                                  Heidelberg, 2006 . . . . . . . . . . . . 17--23
             Kushal Chakrabarti   Book Review: \booktitleThe Handbook of
                                  Bioinspired Algorithms and Applications,
                                  edited by Stephan Olariu and Albert Y.
                                  Zomaya, Chapman & Hall / CRC, 679 pages,
                                  \$139.95}  . . . . . . . . . . . . . . . 23--35
                 Maulik A. Dave   Review 17 of \booktitleTheoretical and
                                  Experimental DNA Computation, by M.
                                  Amos. Published in 2005 by
                                  Springer-Verlag, Berlin, Heidelberg  . . 35--36
                   Fatima Talib   Book Review: \booktitleCoding for Data
                                  and Computer Communications, by David
                                  Salomon. Springer, 2005  . . . . . . . . 36--41
                    Dean Kelley   Technical report column  . . . . . . . . 42--44
           Lane A. Hemaspaandra   SIGACT news complexity theory column 65  45--45
                        Z. Dvir   Guest column: from randomness extraction
                                  to rotating needles  . . . . . . . . . . 46--61
                     Jianwen Su   Database theory column: report on PODS
                                  2009 . . . . . . . . . . . . . . . . . . 62--63
                    Idit Keidar   Distributed computing column 36:
                                  Distributed Computing: 2009 edition  . . 64--67
              Rodrigo Rodrigues   Barbara Liskov's Turing award  . . . . . 68--70
               Keren Censor and   
               Christoph Lenzen   A review of PODC 2009  . . . . . . . . . 71--74
               Andreas Tielmann   A review of DISC 2009  . . . . . . . . . 75--79
                Vincent Gramoli   What theory for transactional memory?    79--81
             Petr Kuznetsov and   
              Rodrigo Rodrigues   BFTW 3: Why? When? Where? Workshop on
                                  the theory and practice of Byzantine
                                  fault tolerance  . . . . . . . . . . . . 82--86
               Seth Gilbert and   
            Dariusz R. Kowalski   Reliability and security in wireless
                                  networks . . . . . . . . . . . . . . . . 86--87
            Roberto Baldoni and   
        Alexander A. Shvartsman   Theoretical aspects of dynamic
                                  distributed systems: report on the
                                  workshop, Elche, Spain, September 26,
                                  2009 . . . . . . . . . . . . . . . . . . 87--89
              Chryssis Georgiou   Game-theoretic aspects of distributed
                                  computing  . . . . . . . . . . . . . . . 89--92
                   Shantanu Das   Review of SIROCCO 2009 . . . . . . . . . 93--97
                  Marek Chrobak   Introduction to the SIGACT news online
                                  algorithms column  . . . . . . . . . . . 98
              Reza Dorrigiv and   
   Alejandro López-Ortiz   On Developing New Models, with Paging as
                                  a Case Study . . . . . . . . . . . . . . 98--123


ACM SIGACT News
Volume 41, Number 1, March, 2010

                William Gasarch   The book review column . . . . . . . . . 10
              Richard Jankowski   Book Review: \booktitleData Structures
                                  and Algorithms Using Python and C++, by
                                  David M. Reed and John Zelle Franklin,
                                  Beedle and Associates 2009 . . . . . . . 13--15
                  Adel El-Atawy   Book Review: \booktitleAn Introduction
                                  to Data Structures and Algorithms, by
                                  James A. Storer, Birkhäuser . . . . . . . 15--19
              Richard Jankowski   Book Review: \booktitleAdvanced Data
                                  Structures, by Peter Brass, Cambridge
                                  University Press 2008  . . . . . . . . . 19--20
             Shoshana Neuburger   Book Review: \booktitleThe
                                  Burrows--Wheeler Transform: Data
                                  Compression, Suffix Arrays, and Pattern
                                  Matching, by Donald Adjeroh, Timothy
                                  Bell and Amar Mukherjee Springer, 2008   21--24
             Matthew J. Sottile   Book Review: \booktitleCurve and Surface
                                  Reconstruction: Algorithms with
                                  Mathematical Analysis, by Tamal K. Dey,
                                  Cambridge University Press . . . . . . . 24--27
             Aravind Srinivasan   Book Review: \booktitleConcentration of
                                  Measure for the Analysis of Randomized
                                  Algorithms, by Devdatt P. Dubhashi and
                                  Alessandro Panconesi, Cambridge
                                  University Press, 2009 . . . . . . . . . 28--30
                John S. Griffin   Book Review: \booktitleThe modern
                                  algebra of information retrieval by
                                  Sandor Dominich, Springer-Verlag, Berlin
                                  /Heidelberg  . . . . . . . . . . . . . . 30--34
                     Haris Aziz   Book Review: \booktitleMultiagent
                                  Systems: Algorithmic, Game-Theoretic,
                                  and Logical Foundations, by Y. Shoham
                                  and K. Leyton-Brown, Cambridge
                                  University Press, 2008 . . . . . . . . . 34--37
               Rajesh Natarajan   Book Review: \booktitleThe Political
                                  Mapping of Cyberspace, by Jeremy W.
                                  Crampton, Publisher: The University of
                                  Chicago Press, 2003  . . . . . . . . . . 38--41
                     Haris Aziz   Book Review: \booktitleThe Princeton
                                  Companion to Mathematics, by Timothy
                                  Gowers, June Barrow-Green and Imre
                                  Leader, Princeton University Press, 2008 41--43
                Michael Sanford   Book Review: \booktitleComputer Viruses
                                  and Malware, by John Aycock  . . . . . . 44--47
            Yannis C. Stamatiou   Book Review: \booktitleFormal
                                  Correctness of Security Protocols, by
                                  Giampaolo Bella, Springer-Verlag . . . . 47--50
                 Wesley Calvert   Book Review: \booktitleComputability of
                                  Julia Sets, by Mark Braverman and
                                  Michael Yampolsky, Publisher: Springer,
                                  2009 . . . . . . . . . . . . . . . . . . 51--53
                    Dean Kelley   Technical report column  . . . . . . . . 54--56
                    Idit Keidar   Distributed computing column 37:
                                  Reconfiguring state machines \ldots and
                                  the history of common knowledge  . . . . 57--57
                    Yoram Moses   Behind the scenes of K&CK: the
                                  undelivered speech for the 2009 Dijkstra
                                  Prize  . . . . . . . . . . . . . . . . . 58--62
             Leslie Lamport and   
              Dahlia Malkhi and   
                    Lidong Zhou   Reconfiguring a state machine  . . . . . 63--73
               Riccardo Pucella   SIGACT news logic column 21  . . . . . . 74--74
               Simon Kramer and   
         Rajeev Goré and   
                   Eiji Okamoto   Formal definitions and complexity
                                  results for trust relations and trust
                                  domains fit for TTPs, the web of trust,
                                  PKIs, and ID-based cryptography  . . . . 75--98
                  Marek Chrobak   SIGACT news online algorithms column 16  99--99
          Michael H. Goldwasser   A survey of buffer management policies
                                  for packet switches  . . . . . . . . . . 100--128

ACM SIGACT News
Volume 41, Number 2, June, 2010

                William Gasarch   The book review column . . . . . . . . . 7--10
      Miklós Bóna   Book Review: \booktitleAnalytic
                                  Combinatorics, by Philippe Flajolet and
                                  Robert Sedgewick, published by Cambridge
                                  Press, 2009, 824 pages, hardcover  . . . 11--14
                     John Mount   Book Review: \booktitleCombinatorics:
                                  the Rota Way, by Joseph P. S. Kung,
                                  Gian-Carlo Rota and Catherine H. Yan,
                                  published by Cambridge Press, 2009 396
                                  pages, softcover . . . . . . . . . . . . 14--17
                   Peter Boothe   Book Review: \booktitleA Course in
                                  Enumeration, by Martin Aigner, Springer,
                                  2007 555 pages, hardcover  . . . . . . . 17--19
      Miklós Bóna   Book Review: \booktitleA Combinatorial
                                  Approach to Matrix Theory and Its
                                  Applications, by Richard Brualdi and
                                  Drago\vs Cvetkovi\'c, Published by
                                  Cambridge Press, 2009, 824 pages,
                                  hardcover  . . . . . . . . . . . . . . . 19--22
                Kevin A. Wilson   Book Review: \booktitleThe Annotated
                                  Turing, by Charles Petzold, Publisher
                                  Wiley, 2008  . . . . . . . . . . . . . . 22--26
                William Gasarch   Book Review: \booktitleLogicomix Text,
                                  by Apostolos Doxiadis and Christos
                                  Papadimitriou Art by Alecos Papadatos
                                  and Annie di Donna, published by
                                  Bloomsbury, 2009 314 pages, softcover.
                                  comic book!  . . . . . . . . . . . . . . 26--28
            Christopher Pincock   Book Review: \booktitleProof and Other
                                  Dilemmas: Mathematics and Philosophy,
                                  edited by Bonnie Gold & Roger A. Simons,
                                  Spectrum Series, MAA, 2008 346 pages,
                                  hardcover  . . . . . . . . . . . . . . . 28--33
                 S. C. Coutinho   Book Review: \booktitleEssays in
                                  Constructive Mathematics, by Harold M.
                                  Edwards, published by Springer, 2005 211
                                  pages, hardcover . . . . . . . . . . . . 33--36
José de Oliveira Guimarães   Book Review: \booktitleIs Mathematics
                                  Inevitable? A Miscellany, by Underwood
                                  Dudley (editor), The Mathematical
                                  Association of America, 2008 324 pages,
                                  hardcover  . . . . . . . . . . . . . . . 36--37
                  Mike Williams   Book Review: \booktitleIntroduction to
                                  Languages and Machines, by Alan P.
                                  Parkes, Springer, 2008 . . . . . . . . . 37--40
                Kevin A. Wilson   Book Review: \booktitleA Second Course
                                  in Formal Languages and Automata Theory,
                                  by Jeffrey Shallit, publisher: Cambridge
                                  University Press, 2008 . . . . . . . . . 40--43
            Kyriakos N. Sgarbas   Book Review: \booktitleAutomata Theory
                                  with Modern Applications, by James A.
                                  Anderson, Cambridge University Press,
                                  2006, viii + 256 pages . . . . . . . . . 43--46
            Sorelle A. Friedler   Book Review: \booktitleChange is
                                  Possible: Stories of Women and
                                  Minorities in Mathematics, by Patricia
                                  Clark Kenschaft, published by AMS, 2005
                                  212 pages, softcover . . . . . . . . . . 47--50
                William Gasarch   Book Review: \booktitleRiot at the Calc
                                  Exam and Other Mathematically Bent
                                  Stories, by Colin Adams, published by
                                  the AMS, 2009 271 pages, softcover and
                                  \booktitleThe Great Debate: Which Is the
                                  Best Number?, by Colin Adams VS Thomas
                                  Garrity, moderated by Edward Burger,
                                  published by the MAA, 2006 and
                                  \booktitleThe United States of
                                  Mathematics Presidential Debate, by
                                  Colin Adams VS Thomas Garrity, moderated
                                  by Edward Burger, published by the MAA,
                                  2009 . . . . . . . . . . . . . . . . . . 50--51
           Lane A. Hemaspaandra   Technical report column  . . . . . . . . 53--56
                 Ronen Shaltiel   Typically-correct derandomization  . . . 57--72
                    Idit Keidar   Distributed Computing Column 38: Models
                                  for algorithm design in wireless
                                  networks . . . . . . . . . . . . . . . . 73--73
                 Zvi Lotker and   
                    David Peleg   Structure and algorithms in the SINR
                                  wireless model . . . . . . . . . . . . . 74--84

ACM SIGACT News
Volume 41, Number 3, September, 2010

                William Gasarch   The book review column . . . . . . . . . 15--17
                William Gasarch   Book Review: \booktitleRandom Curves:
                                  Journeys of a Mathematician, by Neal
                                  Koblitz, published by Springer, 2008,
                                  390 pages  . . . . . . . . . . . . . . . 18--25
                William Gasarch   Book Review: \booktitleGames of No
                                  Chance (1998, edited by Richard
                                  Nowakowski) and \booktitleMore Games of
                                  No Chance (2002, edited by Richard
                                  Nowakowski) and \booktitleGames of No
                                  Chance III (2009, edited by Michael
                                  Albert and Richard Nowakowski published
                                  by Cambridge Press)  . . . . . . . . . . 26--28
                William Gasarch   Book Review: \booktitleMathematical
                                  Treks: from Surreal Numbers to Magic
                                  Circles, by Ivars Peterson published by
                                  the MAA, 2002 170 pages  . . . . . . . . 29--30
                David Pritchard   Book Review: \booktitleDecisions and
                                  Elections: Explaining the Unexpected, by
                                  Donald G. Saari, Cambridge University
                                  Press, 2001, ISBN 0-521-80816-2  . . . . 30--33
                 Mark C. Wilson   Book Review: \booktitleThe Mathematics
                                  of Voting and Elections: a Hands-On
                                  Approach, by Jonathan K. Hodge and
                                  Richard E. Klima, American Mathematical
                                  Society (Mathematical World Series,
                                  volume 22) 226 + xiv pages . . . . . . . 34--36
                 Samuel Johnson   Book Review: \booktitleBranching
                                  Programs and Binary Decision Diagrams:
                                  Theory and Applications, by Ingo
                                  Wegener, Society for Industrial and
                                  Applied Mathematics, 2000, 408 pages . . 36--38
                Eleanor Rieffel   Book Review: \booktitleQuantum Computer
                                  Science: an Introduction, by N. David
                                  Mermin, Cambridge Press, 2007, 236 pages 39--44
                Jeffrey Shallit   Book Review: \booktitleCryptographic
                                  Applications of Analytic Number Theory:
                                  Lower Bounds and Pseudorandomness, by
                                  Igor Shparlinski, Birkäuser, 2003 . . . . 44--45
             Yannis Haralambous   Book Review: \booktitleHistory of
                                  Mathematics, Princeton University Press,
                                  2004, xxvi + 372 pages . . . . . . . . . 46--50
              Nick Papanikolaou   Book Review: \booktitleThe Space and
                                  Motion of Communicating Agents, by Robin
                                  Milner, Cambridge University Press,
                                  2009, ISBN 978-0-521-73833-0 . . . . . . 51--55
           Lane A. Hemaspaandra   Technical report column  . . . . . . . . 56--58
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 67  58
      Arkadev Chattopadhyay and   
                Toniann Pitassi   The story of set disjointness  . . . . . 59--85
                 Dirk Van Gucht   Database theory column report on PODS
                                  2010 . . . . . . . . . . . . . . . . . . 86--87
                    Idit Keidar   Distributed Computing Column 39:
                                  Byzantine Generals: The Next Generation  88
               Valerie King and   
                     Jared Saia   Scalable Byzantine computation . . . . . 89--104
                Marko Vukoli\'c   The Byzantine Empire in the intercloud   105--111

ACM SIGACT News
Volume 41, Number 4, December, 2010

                William Gasarch   The book review column . . . . . . . . . 12--15
                    Daniel Apon   Joint review of \booktitleComputational
                                  Complexity: a Conceptual Perspective, by
                                  Oded Goldreich, published by Cambridge
                                  University Press, 2008 and
                                  \booktitleComputational Complexity: a
                                  Modern Approach, by Sanjeev Arora and
                                  Boaz Barak, published by Cambridge
                                  University Press, 2009 . . . . . . . . . 15--21
                     Dave Levin   Book Review: \booktitleAlgorithmic Game
                                  Theory, edited by Noam Nisan, Tim
                                  Roughgarden, Eva Tardos, Vijay V.
                                  Vazirani. Cambridge University Press,
                                  ISBN 978-0-521-87282-9 . . . . . . . . . 21--24
                William Gasarch   Book Review: \booktitleThe P = NP
                                  question and Gödel's lost letter, by
                                  Richard J. Lipton, Springer, 2010  . . . 25--29
                William Gasarch   Book Review: \booktitleThe Pea and the
                                  Sun: a Mathematical Paradox, by Leonard
                                  Wapner Published by A. K. Peters, 2005   30--32
                David A. Werden   Book Review: \booktitleCoding for Data
                                  and Computer Communications, by David
                                  Salomon, Springer, 2005  . . . . . . . . 32--34
                 Graham Coleman   Book Review: \booktitleBinary Quadratic
                                  Forms: an Algorithmic Approach, by
                                  Johannes Buchmann and Ulrich Vollmer
                                  Springer 2007  . . . . . . . . . . . . . 34--35
                     David Chen   Book Review: \booktitleElliptic Curves,
                                  by Lawrence C. Washington 2008, Chapman
                                  and Hall . . . . . . . . . . . . . . . . 36--38
              Sarvagya Upadhyay   Book Review: \booktitleConcurrent
                                  Zero-Knowledge, by Alon Rosen,
                                  Springer-Verlag, 2006  . . . . . . . . . 38--42
                 Cillian Murphy   Book Review: \booktitleIntroduction to
                                  Cryptography, by Hans Delfs and Helmut
                                  Knebl, Publisher: Springer, 2007, ISBN
                                  978-3-540-49243-6  . . . . . . . . . . . 42--44
                     Ben Fulton   Book Review: \booktitleIntroduction to
                                  Modern Cryptography, by Jonathan Katz
                                  and Yehuda Lindell, Publisher: Chapman &
                                  Hall-CRC 2008 1-58488-551-3  . . . . . . 44--47
               Sarah Meiklejohn   Book Review: \booktitleAn Introduction
                                  to Mathematical Cryptography, by Jeffrey
                                  Hoffstein, Jill Pipher, and Joseph
                                  Silverman Springer-Verlag, 2008  . . . . 47--50
                  Andrew C. Lee   Book Review: \booktitleSoftware
                                  Abstractions: Logic, Language and
                                  Analysis, by Daniel Jackson, MIT Press,
                                  2006 . . . . . . . . . . . . . . . . . . 50--54
                    Dean Kelley   Technical report column  . . . . . . . . 55--57
                Dave Clarke and   
             David Eppstein and   
            Kaveh Ghasemloo and   
                 Lev Reyzin and   
      András Salamon and   
                 Peter Shor and   
             Aaron Sterling and   
      Suresh Venkatasubramanian   Questions answered. in theory:
                                  http://cstheory.stackexchange.com  . . . 58--60
             Misha Koshelev and   
             Luc Longpré   Algorithmic information theory may
                                  explain the pathogenic number of DNA
                                  repeats in myotonic dystrophy type 1
                                  (and in similar diseases)  . . . . . . . 61--64
               Samir Kuller and   
             Michael W. Mahoney   SIGACT news algorithms column:
                                  Computation in large-scale scientific
                                  and Internet data applications is a
                                  focus of MMDS 2010 . . . . . . . . . . . 65--72
           Lane A. Hemaspaandra   SIGACT news complexity theory column 68  73--94
                    Idit Keidar   Distributed computing column 40: Annual
                                  review 2010  . . . . . . . . . . . . . . 95--99
               Leonid Barenboim   A review of PODC 2010  . . . . . . . . . 100--105
         François Bonnet   Review of DISC 2010  . . . . . . . . . . 106--108
             Srivatsan Ravi and   
            Vincent Gramoli and   
               Victor Luchangco   Transactional memory, linking theory and
                                  practice . . . . . . . . . . . . . . . . 109--115
                  Marek Chrobak   SIGACT news online algorithms column 17  114--121


ACM SIGACT News
Volume 42, Number 1, March, 2011

                William Gasarch   The book review column . . . . . . . . . 12--15
                William Gasarch   Joint review of \booktitleThe
                                  Mathemagician and Pied Puzzler: a
                                  Collection in Tribute to Martin Gardner  16--22
                   Sage LaTorra   Book Review: \booktitleComprehensive
                                  Mathematics for Computer Scientists 1,
                                  by Guerino B. Mazzola, Gerard
                                  Milmeister, Jody Weissmann . . . . . . . 23--24
                     Jason Dyer   Book Review: \booktitleCreative
                                  Mathematics, by H. S. Wall . . . . . . . 24--25
                  Justin Melvin   Book Review: \booktitleNonlinear Integer
                                  Programming, by Duan Li and Xiaoling Sun 26--29
                 Carl Kingsford   Book Review: \booktitleComplex Social
                                  Networks, by Fernando Vega-Redondo . . . 29--31
                 Carlo A. Furia   Book Review: \booktitleThe Calculus of
                                  Computation: Decision Procedures with
                                  Applications to Verification, by Aaron
                                  R. Bradley and Zohar Manna . . . . . . . 32--35
            Yiorgos Adamopoulos   Book Review: \booktitleAlgorithms on
                                  Strings, by Crochemore, Hanchart and
                                  Lecroq. Published by Cambridge 2007, 392
                                  pages, Hardcover, \$60.00} . . . . . . . 36--37
             Yannis Haralambous   Book Review: \booktitleA View from the
                                  Top: Analysis, Combinatorics and Number
                                  Theory, by Alex Iosevich . . . . . . . . 38--42
       Brittany Terese Fasy and   
               David L. Millman   Book Review: \booktitleGeometric Folding
                                  Algorithms, by E. D. Demaine and J.
                                  O'Rourke . . . . . . . . . . . . . . . . 43--46
            Brittany Terese and   
               David L. Millman   Book Review: \booktitleGeometric
                                  Algebra: an Algebraic System for
                                  Computer Games and Animation, by J.
                                  Vince  . . . . . . . . . . . . . . . . . 46--48
                William Gasarch   Book Review: \booktitleDude, Can You
                                  Count?: Stories, Challenges, and
                                  Adventures in Mathematics, by Christian
                                  Constanda  . . . . . . . . . . . . . . . 49--54
                    Dean Kelley   Technical report column  . . . . . . . . 55--57
           Lane A. Hemaspaandra   SIGACT news complexity theory column 69  58--58
                    Madhu Sudan   Guest column: Testing linear properties:
                                  Some general theme . . . . . . . . . . . 59--80
                    Idit Keidar   Distributed computing column 41:
                                  Computing over dynamic networks  . . . . 81--81
                Fabian Kuhn and   
                   Rotem Oshman   Dynamic networks: models and algorithms  82--96
               Dimitris Fotakis   Online and incremental algorithms for
                                  facility location  . . . . . . . . . . . 97--131

ACM SIGACT News
Volume 42, Number 2, June, 2011

                William Gasarch   The book review column . . . . . . . . . 7--10
                  Vaishak Belle   Book Review: \booktitleFrom Zero to
                                  Infinity: What Makes Numbers
                                  Interesting, by Constance Reid . . . . . 10--11
                   Mladen Miksa   Book Review: \booktitleMathematics for
                                  the Analysis of Algorithms, by Daniel H.
                                  Greene and Donald E. Knuth . . . . . . . 12--14
              Joseph Fitzsimons   Book Review: \booktitleAlgebraic
                                  Cryptanalysis, by Gregory V. Bard  . . . 14--18
               Swastik Kopparty   Book Review: \booktitleAlgebraic
                                  Function Fields and Codes, by Henning
                                  Stichtenoth  . . . . . . . . . . . . . . 19--24
                William Gasarch   Book Review: \booktitleThose Fascinating
                                  Numbers, by Jean-Marie De Koninck  . . . 24--27
               Stephen Stanhope   Book Review: \booktitlePólya Urn Models,
                                  by Hosam Mahmoud . . . . . . . . . . . . 27--33
                 S. C. Coutinho   Book Review: \booktitleNot Always Buried
                                  Deep: A Second Course in Elementary
                                  Number Theory, by Paul Pollack . . . . . 34--37
            Sorelle A. Friedler   Book Review: \booktitlePioneering Women
                                  in American Mathematics: the pre-1940
                                  PhD's, by Judy Green and Jeanne LaDuke   37--41
                       Song Yan   Book Review: \booktitleA Guide to
                                  Elementary Number Theory, by Underwood
                                  Dudley . . . . . . . . . . . . . . . . . 41--42
                Pauli Miettinen   Book Review: \booktitleMathematical
                                  Tools for Data Mining: Set Theory,
                                  Partial Orders, Combinatorics, by Dan A.
                                  Simovici and Chabane Djeraba . . . . . . 43--46
                    Dean Kelley   Technical report column  . . . . . . . . 47--50
           Lane A. Hemaspaandra   SIGACT news complexity theory column 70  51--51
                   John Watrous   Guest column: An introduction to quantum
                                  information and quantum circuits 1 . . . 52--67
                    Idit Keidar   Distributed computing column 42: Game
                                  theory and fault tolerance in
                                  distributed computing  . . . . . . . . . 68--68
              Ittai Abraham and   
             Lorenzo Alvisi and   
              Joseph Y. Halpern   Distributed computing meets game theory:
                                  combining insights from two fields . . . 69--76
                        Li Chen   Education Forum  . . . . . . . . . . . . 77--81
                  Marek Chrobak   SIGACT news online algorithms column 19  82--82
                 Sungjin Im and   
           Benjamin Moseley and   
                     Kirk Pruhs   A tutorial on amortized local
                                  competitiveness in online scheduling . . 83--97

ACM SIGACT News
Volume 42, Number 3, September, 2011

                William Gasarch   The book review column . . . . . . . . . 14--15
                   Andy Parrish   Book Review: \booktitleErd\Hos on
                                  Graphs: His Legacy of Unsolved Problems,
                                  by Fan Chung and Ron Graham  . . . . . . 16--20
                    Eowyn Cenek   Book Review: \booktitleRoots to
                                  Research, by Judith D. Sally and Paul J.
                                  Sally, Jr. . . . . . . . . . . . . . . . 20--22
                    Vance Faber   Book Review: \booktitleChromatic Graph
                                  Theory, by Gary Chartrand and Ping Zhang 23--28
           Dimitris Papamichail   Book Review: \booktitleApplied
                                  Combinatorics, by Fred S. Roberts and
                                  Barry Tesman . . . . . . . . . . . . . . 29--32
      Miklós Bóna   Book Review: \booktitleApplied
                                  Combinatorics, by Fred S. Roberts and
                                  Barry Tesman . . . . . . . . . . . . . . 32--34
          Michaël Cadilhac   Book Review: \booktitleCombinatorics: a
                                  Guided Tour, by David R. Mazur . . . . . 34--36
                     Lev Reyzin   Book Review: \booktitleFamous Puzzles of
                                  Great Mathematicians, by Miodrag S.
                                  Petkovi\'c . . . . . . . . . . . . . . . 36--39
                Myriam Abramson   Book Review: \booktitleCombinatorics: A
                                  Problem Oriented Approach, by Daniel A.
                                  Marcus . . . . . . . . . . . . . . . . . 40--41
      Miklós Bóna   Book Review: \booktitleProbability:
                                  Theory and Examples, 4th edition, by
                                  Rick Durrett . . . . . . . . . . . . . . 42--45
                    Daniel Apon   Book Review: \booktitleGames, Puzzles, &
                                  Computation, by Robert A. Hearn and Erik
                                  D. Demaine . . . . . . . . . . . . . . . 45--49
                    Dean Kelley   Technical report column  . . . . . . . . 50--52
           Lane A. Hemaspaandra   SIGACT news complexity theory column 71  53--54
                  Ryan Williams   Guest column: a casual tour around a
                                  circuit complexity bound . . . . . . . . 54--76
                    Idit Keidar   Distributed computing column 43: Using
                                  social networks to overcome Sybil
                                  attacks  . . . . . . . . . . . . . . . . 79--79
                     Haifeng Yu   Sybil defenses via social networks: a
                                  tutorial and survey  . . . . . . . . . . 80--101

ACM SIGACT News
Volume 42, Number 4, December, 2011

                William Gasarch   The book review column . . . . . . . . . 15--16
                     Saif Terai   Book Review: \booktitleFoundations of
                                  Logic and Mathematics Applications to
                                  Computer Science and Cryptography, by
                                  Yves Nievergelt  . . . . . . . . . . . . 17--21
                 Maulik A. Dave   Book Review: \booktitleRippling:
                                  Meta-Level Guidance for Mathematical
                                  Reasoning Cambridge Tracts in
                                  Theoretical Computer Science 56 by Alan
                                  Bundy, David Basin, Dieter Hutter, and
                                  Andrew Ireland . . . . . . . . . . . . . 21--23
                 Aaron Sterling   Book Review: \booktitleHandbook of
                                  Nature-Inspired and Innovative
                                  Computing, by Albert Y. Zomaya . . . . . 23--26
                   Hal C. Elrod   Book Review: \booktitleAlgorithms and
                                  Data Structures: the Basic Toolbox, by
                                  Kurt Mehlhorn and Peter Sanders  . . . . 26--29
             Neelakantan Kartha   Book Review: \booktitleThe Algorithm
                                  Design Manual, second edition by Steven
                                  S. Skiena  . . . . . . . . . . . . . . . 29--31
                     Haris Aziz   Book Review: \booktitleGraph Theory: a
                                  Problem Oriented Approach, by Daniel
                                  Marcus . . . . . . . . . . . . . . . . . 31--32
      Miklós Bóna   Book Review: \booktitleProofs from THE
                                  BOOK (4th edition) by Martin Aigner and
                                  Günter M. Ziegler . . . . . . . . . . . . 32--37
                 Aaron Sterling   Book Review: \booktitleHandbook of
                                  Chemoinformatics Algorithms, by Faulon   37--48
                       Song Yan   Book Review: \booktitleDynamic Fuzzy
                                  Logic and Its Applications, by Fanzhang
                                  Li . . . . . . . . . . . . . . . . . . . 48--49
                    Dean Kelley   Technical report column  . . . . . . . . 50--52
           Lane A. Hemaspaandra   SIGACT news complexity theory column 72  53--53
                        X. Chen   Guest column: Complexity dichotomies of
                                  counting problems  . . . . . . . . . . . 54--76
                    Idit Keidar   Distributed computing column 44: 2011 in
                                  review . . . . . . . . . . . . . . . . . 76--78
                   Hagit Attiya   Sharing memories, robustly . . . . . . . 79--82
                   Maryam Helmi   A review of PODC 2011  . . . . . . . . . 83--86
             Michael Hakimi and   
                  Adam Morrison   A review of DISC 2011  . . . . . . . . . 87--91
            Adrian Kosowski and   
              Dominik Pajak and   
            Zuzanna Stamirowska   SIROCCO 2011 . . . . . . . . . . . . . . 92--95


ACM SIGACT News
Volume 43, Number 1, March, 2012

                William Gasarch   The book review column . . . . . . . . . 7--9
Abu Mohammad Omar Shehab Uddin Ayub   Book Review: \booktitleThe Cryptoclub:
                                  Using Mathematics to Make and Break
                                  Secret Codes, by Janet Beissinger and
                                  Vera Pless . . . . . . . . . . . . . . . 9--14
                 Leo Irakliotis   Book Review: \booktitleCryptanalytic
                                  Attacks on RSA, by Song Y. Yan . . . . . 14--16
                  Antoine Rojat   Book Review: \booktitleCryptanalysis of
                                  RSA and its variants, by Jason Hinek . . 16--18
    Jérémy Barbay   Book Review: \booktitleUnderstanding and
                                  Applying Cryptography and Data Security,
                                  by Adam J. Elbirt  . . . . . . . . . . . 18--21
                  Jonathan Katz   Book Review: \booktitleEfficient Secure
                                  Two-Party Protocols: Techniques and
                                  Constructions, by Carmit Hazay and
                                  Yehuda Lindell . . . . . . . . . . . . . 21--23
                    Daniel Apon   Book Review: \booktitleTheory of
                                  Computation, by Dexter C. Kozen  . . . . 23--27
                  Robert J. Low   Book Review: \booktitleCodes: an
                                  Introduction to Information
                                  Communication and Cryptography, by
                                  Norman L. Biggs  . . . . . . . . . . . . 27--29
                Jeffrey Shallit   Book Review: \booktitleFinite Fields and
                                  Applications, by Gary L. Mullen and Carl
                                  Mummert  . . . . . . . . . . . . . . . . 30--31
      Miklós Bóna   Book Review: \booktitleThe Life and
                                  Times of the Central Limit Theorem, by
                                  William J. Adams . . . . . . . . . . . . 32--33
                  Robert Szarka   Book Review: \booktitlePearls of
                                  Discrete Mathematics, by Martin Erickson 33--34
           Dimitris Papamichail   Book Review: \booktitleDesign Theory, by
                                  C. C. Lindner and C. A. Rodger . . . . . 35--37
                William Gasarch   Book Review: \booktitleAn Introduction
                                  to the History of Algebra Solving
                                  Equations from Mesopotamian Times to the
                                  Renaissance, by Jacques Sesiano  . . . . 39--39
                    Dean Kelley   Technical report column  . . . . . . . . 40--43
                 Oded Goldreich   On struggle and competition in scientic
                                  fields . . . . . . . . . . . . . . . . . 43--60
           Lane A. Hemaspaandra   SIGACT news complexity theory column 73  61--61
                Dana Moshkovitz   Guest column: Algebraic construction of
                                  projection PCPs  . . . . . . . . . . . . 62--81
                Joseph O'Rourke   Computational geometry column 52 . . . . 82--85
                    Idit Keidar   Distributed computing column 45: What
                                  theory for transactional memory? . . . . 86--86
             Petr Kuznetsov and   
                 Srivatsan Ravi   WTTM 2011: The Third Workshop on the
                                  Theory of Transactional Memory . . . . . 87--92

ACM SIGACT News
Volume 43, Number 2, June, 2012

                William Gasarch   The book review column . . . . . . . . . 6--8
           Ville Hautamäki   Review of \booktitleA Concise
                                  Introduction to Data Compression by
                                  David Salomon  . . . . . . . . . . . . . 9--10
                      Mihai Pop   Review of \booktitleParallel Algorithms
                                  by Henri Casanova, Arnaud Legrand, and
                                  Yves Robert  . . . . . . . . . . . . . . 11--14
                    Akash Kumar   Review of \booktitlePolynomia and
                                  Related Realms by Dan Kalman . . . . . . 15--20
                Jeffrey Shallit   Review of \booktitleBiscuits of Number
                                  Theory by Arthur T. Benjamin and Ezra
                                  Brown  . . . . . . . . . . . . . . . . . 21--24
                Gabriel Istrate   Review of \booktitleHandbook of
                                  Large-Scale Random Networks by Bela
                                  Bollobás, Robert Kozma and Deszö Miklós . . 25--28
              Nick Papanikolaou   Review of \booktitleAlgorithms and
                                  Theory of Computation Handbook by
                                  Mikhail J. Atallah and Marina Blanton    29--32
                 S. C. Coutinho   Review of \booktitlePrimality Testing
                                  and Integer Factorization in Public Key
                                  Cryptography by Song Y. Yan  . . . . . . 33--35
                 Wesley Calvert   Review of \booktitleProcess Algebra:
                                  Equational Theories of Communicating
                                  Processes by J. C. M. Baeten, T. Basten,
                                  and M. A. Reniers  . . . . . . . . . . . 36--38
         Kim-Kwang Raymond Choo   Review of \booktitleInsider Threats in
                                  Cyber Security by Probst, Hunker,
                                  Gollman, Bishop  . . . . . . . . . . . . 38--40
                    Dean Kelley   Technical report column  . . . . . . . . 41--44
                 Oded Goldreich   On intellectual and instrumental values
                                  in science . . . . . . . . . . . . . . . 45--50
           Lane A. Hemaspaandra   SIGACT news complexity theory column 74  51--52
             William I. Gasarch   Guest Column: the second P =? NP poll    53--77
              Adrian Dumitrescu   Computational geometry column 53 . . . . 78--83
                    Idit Keidar   Distributed computing column 46:
                                  synthesizing distributed and concurrent
                                  programs . . . . . . . . . . . . . . . . 84--84
        Borzoo Bonakdarpour and   
            Sandeep S. Kulkarni   Automated model repair for distributed
                                  programs . . . . . . . . . . . . . . . . 85--107
         Michael Kuperstein and   
              Martin Vechev and   
                     Eran Yahav   Automatic inference of memory fences . . 108--123
                 Chong-Zhang Li   Hilbert's formalistic method and its
                                  development in computer science  . . . . 124--126
                   Rob van Stee   SIGACT news online algorithms column 20:
                                  the power of harmony . . . . . . . . . . 127--136

ACM SIGACT News
Volume 43, Number 3, September, 2012

                William Gasarch   The book review column . . . . . . . . . 15--18
                William Gasarch   Review of \booktitleCombinatorial Games:
                                  Tic-Tac-Toe Theory, by Jozsef Beck . . . 19--21
             Antonio E. Porreca   Review of \booktitleAlgorithmic
                                  Adventures: From Knowledge to Magic, by
                                  Juraj Hromkovi\'c  . . . . . . . . . . . 22--24
                      Yulai Xie   Review of \booktitleApplied Algebra:
                                  Codes, Ciphers and Discrete Algorithms,
                                  by Darel W. Hardy, Fred Richman, and
                                  Carol L. Walker  . . . . . . . . . . . . 25--27
José de Oliveira Guimarães   Review of \booktitleModels of
                                  Computation: an Introduction to
                                  Computability Theory, by Maribel
                                  Fernández . . . . . . . . . . . . . . . . 28--31
          Michaël Cadilhac   Review of \booktitleHandbook of Weighted
                                  Automata, edited by Manfred Droste,
                                  Werner Kuich and Heiko Vogler  . . . . . 32--37
                     Haris Aziz   Review of \booktitleMatching Theory, by
                                  László Lovász and Michael D. Plummer  . . . 38--40
                  Stephan Falke   Review of \booktitleIntroduction to
                                  Mathematics of Satisfiability, by Victor
                                  W. Marek . . . . . . . . . . . . . . . . 41--44
                  Shiva Kintali   Review of \booktitleElements of Automata
                                  Theory, by Jacques Sakarovitch,
                                  Translator (from French) Reuben Thomas   45--47
                Anthony Labarre   Review of \booktitleCombinatorial
                                  Pattern Matching Algorithms in
                                  Computational Biology using Perl and R,
                                  by Gabriel Valiente  . . . . . . . . . . 48--50
                     Haris Aziz   Review of \booktitleIn Pursuit of the
                                  Traveling Salesman, by William J. Cook   51--53
                Karolina Soltys   Review of \booktitlePermutation
                                  Patterns, edited by Steve Linton, Nik
                                  Ru\vskuc, Vincent Vatter . . . . . . . . 54--55
                    Dean Kelley   Technical report column  . . . . . . . . 56--59
          Nachum Dershowitz and   
             Edward M. Reingold   Modulo intervals: a proposed notation    60--64
           Lane A. Hemaspaandra   SIGACT news complexity theory column 75  65--66
                Amir Yehudayoff   Proving expansion in three steps . . . . 67--84
               Michael Benedikt   Report on PODS 2012  . . . . . . . . . . 85--86
                    Idit Keidar   Distributed computing column 47:
                                  distributed computability  . . . . . . . 87--87
            Maurice Herlihy and   
            Sergio Rajsbaum and   
                  Michel Raynal   Computability in distributed computing:
                                  a Tutorial . . . . . . . . . . . . . . . 88--110

ACM SIGACT News
Volume 43, Number 4, December, 2012

      Alexandre Anzala-Yamajako   Review of \booktitleAlgorithmic
                                  Cryptanalysis, by Antoine Joux . . . . . 13--16
                 Aaron Sterling   Review of \booktitleAlgorithmic
                                  Bioprocesses, edited by Condon, Harel,
                                  Kok, Salomaa, Winfree  . . . . . . . . . 17--24
                        Yu Wang   Review of \booktitleVehicular Networks,
                                  from Theory to Practice, edited by
                                  Stephan Olariu and Michele C. Weigle . . 25--29
            Francesco Silvestri   Review of \booktitleGraph Theory and
                                  Interconnection Networks, by Lih-Hsing
                                  Hsu and Cheng-Kuan Lin . . . . . . . . . 30--34
                  Stephan Falke   Review of \booktitleTransitions and
                                  Trees: an Introduction to Structural
                                  Operational Semantics, by Hans Hüttel . . 34--37
                     Haim Kilov   Review of \booktitleOrigins and
                                  Foundations of Computing, by Friedrich
                                  L. Bauer . . . . . . . . . . . . . . . . 38--40
                     Ben Fulton   Review of \booktitleIntroduction to
                                  Scheduling, by Yves Robert and Frédéric
                                  Vivien . . . . . . . . . . . . . . . . . 41--43
            Kyriakos N. Sgarbas   Review of \booktitleSemantic Techniques
                                  in Quantum Computation, edited by Simon
                                  Gay and Ian Mackie . . . . . . . . . . . 44--48
                       Song Yan   Review of \booktitleModern Computer
                                  Arithmetic, by Richard Brent and Paul
                                  Zimmermann . . . . . . . . . . . . . . . 49--51
          Deeparnab Chakrabarty   Review of \booktitleDesign of
                                  Approximation Algorithms, by David P.
                                  Williamson and David B. Shmoys . . . . . 52--54
                    Dean Kelley   Technical report column  . . . . . . . . 55--56
                  Samir Khuller   Algorithms column: an overview of the
                                  recent progress on matrix multiplication
                                  by Virginia Vassilevska Williams . . . . 57--59
       Lane A. Hemaspaandra and   
                  Ryan Williams   SIGACT News Complexity Theory Column 76:
                                  an atypical survey of typical-case
                                  heuristic algorithms . . . . . . . . . . 70--89
          Adrian Dumitrescu and   
           Csaba D. Tóth   Computational geometry column 54 . . . . 90--97
                    Idit Keidar   Distributed computing column 48: annual
                                  review 2012  . . . . . . . . . . . . . . 98--100
            Maurice Herlihy and   
                     Nir Shavit   Transactional memory: beyond the first
                                  two decades  . . . . . . . . . . . . . . 101--103
                 Siddhartha Sen   Review of \booktitlePODC 2012  . . . . . 104--111
            Mika Göös   Review of \booktitleDISC 2012  . . . . . 112--115
            Vincent Gramoli and   
                 Alessia Milani   WTTM 2012, the fourth workshop on the
                                  theory of transactional memory . . . . . 116--122
                   Rob van Stee   SIGACT news online algorithms column 21:
                                  APPROX and ALGO  . . . . . . . . . . . . 123--129


ACM SIGACT News
Volume 44, Number 1, March, 2013

                William Gasarch   The book review column . . . . . . . . . 7--9
                  S. V. Nagaraj   Review of \booktitleP, NP, and
                                  NP-Completeness by Oded Goldreich  . . . 10--11
      Miklós Bóna   Review of \booktitleBijective
                                  Combinatorics by Nicholas Loehr  . . . . 12--14
                      Tal Moran   Review of \booktitleSurveillance or
                                  Security? by Susan Landau  . . . . . . . 14--16
                    Dave Werden   Review of \booktitleSpyware and Adware
                                  by John Aycock . . . . . . . . . . . . . 17--19
                    Harry Lewis   Review of \booktitleBurdens of Proof by
                                  Jean-François Blanchette  . . . . . . . . 19--21
              Marcin Kami\'nski   Review of \booktitleBoolean Models and
                                  Methods in Mathematics, Computer
                                  Science, and Engineering by Yves Crama
                                  and Peter L. Hammer  . . . . . . . . . . 21--24
                  Jason Teutsch   Review of \booktitleAlgorithmic
                                  Randomness and Complexity by Downey and
                                  Hirschfeldt  . . . . . . . . . . . . . . 25--28
                     Paul Rubin   Review of \booktitleInformation
                                  Retrieval by Buettcher, Clarke, Cormack  29--33
                 Mark C. Wilson   Review of \booktitleModels of Conflict
                                  and Cooperation by Rick Gillman and
                                  David Housman  . . . . . . . . . . . . . 34--35
                  Marius Zimand   Review of \booktitleDeterministic
                                  Extraction from Weak Random Sources by
                                  Ariel Gabizon  . . . . . . . . . . . . . 36--37
                  Jonathan Katz   Review of \booktitleApplied Information
                                  Security by David Basin, Patrick
                                  Schaller, and Michael Schläpfer . . . . . 38--40
        Mohsen Mahmoudi Aznaveh   Review of \booktitleIntroduction to
                                  Bio-Ontologies by Peter N. Robinson and
                                  Sebastian Bauer  . . . . . . . . . . . . 40--42
                    Omar Shehab   Review of \booktitleThe Dots and Boxes
                                  Game: Sophisticated Child's Play by
                                  Elwyn Berlekamp  . . . . . . . . . . . . 42--45
                    Dean Kelley   Technical report column  . . . . . . . . 46--48
           Lane A. Hemaspaandra   SIGACT news complexity theory column 77  49--49
              Kai-Min Chung and   
                    Rafael Pass   Guest column: parallel repetition
                                  theorems for interactive arguments . . . 50--69
      Suresh Venkatasubramanian   Computational geometry column 55: new
                                  developments in nonnegative matrix
                                  factorization  . . . . . . . . . . . . . 70--78
                    Idit Keidar   Distributed computing column 49: coding
                                  for distributed storage  . . . . . . . . 79--79
                  Yuval Cassuto   What can coding theory do for storage
                                  systems? . . . . . . . . . . . . . . . . 80--88
            Anwitaman Datta and   
Frédérique Oggier   An overview of codes tailor-made for
                                  better repairability in networked
                                  distributed storage systems  . . . . . . 89--105
                  Mikkel Thorup   Mihai P\uatrascu: obituary and open
                                  problems . . . . . . . . . . . . . . . . 110--114

ACM SIGACT News
Volume 44, Number 2, June, 2013

                William Gasarch   The book review column . . . . . . . . . 7--9
                Mohsen Vakilian   Joint review of \booktitleHow to solve
                                  it: a new aspect of mathematical method
                                  by George Polya and
                                  \booktitleStreet-fighting mathematics by
                                  Sanjoy Mahajan . . . . . . . . . . . . . 10--12
          Matthias Gallé   Review of \booktitleGrammatical
                                  Inference: Learning Automata and
                                  Grammars by Colin de la Higuera  . . . . 12--14
                Arthur Milchior   Review of \booktitleLogical Foundation
                                  of Proof Complexity by Stephen Cook and
                                  Phuong Nguyen  . . . . . . . . . . . . . 14--17
                 Michael Lampis   Review of \booktitleExact Exponential
                                  Algorithms by Fedor V. Fomin and Dieter
                                  Kratsch  . . . . . . . . . . . . . . . . 17--21
                  Sven Herrmann   Review of \booktitleBioinspired
                                  Computation in Combinatorial
                                  Optimization by Frank Neumann and
                                  Carsten Witt . . . . . . . . . . . . . . 22--26
                 Michael Murphy   Review of \booktitleTriangulations:
                                  Structure for Algorithms and
                                  Applications by Jesús A. De Lorea, Jörg
                                  Rambau, and Francisco Santos . . . . . . 26--28
                      Yixin Cao   Review of \booktitleFlows in Networks by
                                  L. R. Ford, Jr. and D. R. Fulkerson  . . 28--30
            Kyriakos N. Sgarbas   Review of \booktitleQuantum Computing: a
                                  Gentle Introduction by Eleanor Rieffel
                                  and Wolfgang Polak . . . . . . . . . . . 31--35
                 John D. Rogers   Review of \booktitleThe Art of Computer
                                  Programming: volume 4a by Donald E.
                                  Knuth  . . . . . . . . . . . . . . . . . 36--39
                William Gasarch   Review of \booktitleBoolean Function
                                  Complexity: Advances and Frontiers by
                                  Stasys Jukna . . . . . . . . . . . . . . 39--41
                    Dean Kelley   Technical report column  . . . . . . . . 42--45
           Lane A. Hemaspaandra   SIGACT News complexity theory column 78  45--46
             Dorit Aharonov and   
                  Itai Arad and   
                  Thomas Vidick   Guest column: the quantum PCP conjecture 47--79
          Adrian Dumitrescu and   
                  Minghui Jiang   Computational geometry column 56 . . . . 80--87
                    Idit Keidar   Distributed computing column 50:
                                  distributing trusted third parties,
                                  innovation prize, and SIROCCO review . . 88--88
                    David Peleg   Prize for innovation in distributed
                                  computing: awarded to Roger Wattenhofer  89--91
Alptekin Küpçü   Distributing trusted third parties . . . 92--112
                  Heger Arfaoui   A review of SIROCCO 2012 . . . . . . . . 113--118
                        Li Chen   Education forum: digital geometry and
                                  its algorithms: an introduction  . . . . 119--124
                   Rob van Stee   SIGACT News online algorithms column 22  125--125
                 Michael Dinitz   Recent advances on the matroid secretary
                                  problem  . . . . . . . . . . . . . . . . 126--142

ACM SIGACT News
Volume 44, Number 3, September, 2013

                William Gasarch   Review of \booktitleTheoretical Computer
                                  Science: Introduction to Automata,
                                  Computability, Complexity, Algorithmics,
                                  Randomization, Communication, and
                                  Cryptography by Juraj Hromkovic  . . . . 7--8
                 Aaron Sterling   Review of \booktitleThe Mathematics of
                                  Life by Ian Stewart  . . . . . . . . . . 9--11
                 Wesley Calvert   Review of \booktitleUniversal Semantic
                                  Communication by B. Juba . . . . . . . . 12--15
                Anthony Labarre   Review of \booktitleGraph Algorithms
                                  (2nd edition) by Shimon Even, edited by
                                  Guy Even . . . . . . . . . . . . . . . . 15--16
       Brittany Terese Fasy and   
               David L. Millman   Review of \booktitleHow to Fold It by J.
                                  O'Rourke . . . . . . . . . . . . . . . . 17--19
           Dimitris Papamichail   Review of \booktitleBioinformatics for
                                  Biologists edited by Pavel Pevzner and
                                  Ron Shamir . . . . . . . . . . . . . . . 20--24
      Miklós Bóna   Review of \booktitleExtremal
                                  Combinatorics with Applications to
                                  Computer Science (2nd edition) by Stasys
                                  Jukna  . . . . . . . . . . . . . . . . . 24--27
               Ang\`ele M. Hame   Review of \booktitleEnumerative
                                  Combinatorics, volume 1, second edition
                                  by Richard P. Stanley  . . . . . . . . . 28--31
                    Akash Kumar   Review of \booktitleCombinatorial
                                  Optimization by B. Korte and J. Vygen    31--35
            Cynthia DiPaula and   
               Andrew Wonnacott   Review of \booktitleThe Golden Ticket:
                                  P, NP, and the Search for the Impossible
                                  by Lance Fortnow . . . . . . . . . . . . 35--37
            Joshua Brulé   Review of \booktitleProbably
                                  Approximately Correct by Leslie Valiant  38--39
                    Dean Kelley   Technical report column  . . . . . . . . 40--41
                Raghav Kulkarni   Gems in decision tree complexity
                                  revisited  . . . . . . . . . . . . . . . 42--55
      Suresh Venkatasubramanian   Moving heaven and earth: distances
                                  between distributions  . . . . . . . . . 56--68
                     Wenfei Fan   Report on PODS 2013  . . . . . . . . . . 69--71
                    Idit Keidar   Distributed computing column 51:
                                  large-scale transaction replication  . . 72--72
              Dahlia Malkhi and   
           Jean-Philippe Martin   Spanner's concurrency control  . . . . . 73--77
                     Ittay Eyal   Fault tolerant transaction architectures 78--84

ACM SIGACT News
Volume 44, Number 4, December, 2013

                William Gasarch   Joint review of the honor class:
                                  \booktitleHilbert's problems and their
                                  solver by Ben Yandell and:
                                  \booktitleMathematical developments
                                  arising from Hilbert's problems edited
                                  by Felix Browder . . . . . . . . . . . . 18--24
                   Farhan Nasim   Review of \booktitleVariable-length
                                  codes for data compression by David
                                  Salomon  . . . . . . . . . . . . . . . . 24--26
                  S. V. Nagaraj   Review of \booktitleHistory of
                                  mathematics: highways and byways by Amy
                                  Dahan-Dalmedico and Jeanne Peiffer . . . 27--28
                       Jon Katz   Review of \booktitleIdentity-based
                                  encryption by Sanjit Chattarjee and
                                  Palash Sarkar  . . . . . . . . . . . . . 29--31
                Myriam Abramson   Review of \booktitleResources for
                                  teaching discrete mathematics: classroom
                                  projects, history modules, and articles
                                  edited by Brian Hopkins  . . . . . . . . 31--34
          Michaël Cadilhac   Review of \booktitleProofs and
                                  algorithms by Gilles Dowek (translation
                                  by Maribel Fernandez)  . . . . . . . . . 35--37
           Dimitris Papamichail   Review of \booktitleIntroduction to
                                  computational proteomics by Golan Yona   38--41
                Jeffrey Shallit   Review of \booktitleComputability and
                                  complexity theory by Steven Homer and
                                  Alan L. Selman . . . . . . . . . . . . . 41--42
                 Frederic Green   Review: \booktitleQuantum computing
                                  since Democritus by Scott Aaronson . . . 42--47
                William Gasarch   Review of \booktitleAlgorithmic puzzles
                                  by Anany Levitin and Maria Levitin . . . 47--48
                    Dean Kelley   Technical report column  . . . . . . . . 49--51
           Lane A. Hemaspaandra   SIGACT news complexity theory column 80  52--52
            Arnab Bhattacharyya   Guest column: On testing
                                  affine-invariant properties over finite
                                  fields . . . . . . . . . . . . . . . . . 53--72
          Adrian Dumitrescu and   
                  Minghui Jiang   Computational geometry column 58 . . . . 73--78
              Jennifer L. Welch   Distributed computing column 52: annual
                                  review 2013  . . . . . . . . . . . . . . 79--80
                      Anonymous   2013 Dijkstra Prize in Distributed
                                  Computing to Nati Linial: 2013
                                  Principles of Distributed Computing
                                  Doctoral Dissertation Award to Shiri
                                  Chechik and Danupon Nanongkai  . . . . . 81--82
          Nicolas Braud-Santoni   PODC 2013 review . . . . . . . . . . . . 83--86
                  Shahar Timnat   DISC 2013 review . . . . . . . . . . . . 87--90
                        Ami Paz   Bremen workshop review . . . . . . . . . 91--97


ACM SIGACT News
Volume 45, Number 1, March, 2014

               Ravindran Kannan   14th Knuth prize: call for nominations   7--8
                    Omar Shehab   Review of \booktitleIn pursuit of the
                                  unknown: 17 equations that changed the
                                  world by Ian Stewart . . . . . . . . . . 11--15
                    Harry Lewis   Review of \booktitleUnauthorized access:
                                  the crisis in online privacy and
                                  security by Robert H. Sloan and Richard
                                  Warner . . . . . . . . . . . . . . . . . 16--19
                     Haris Aziz   Review of \booktitleboolean functions:
                                  theory, algorithms, and applications by
                                  Yves Crama and Peter L. Hammer . . . . . 20--23
               Raghunath Tewari   Review of \booktitleAdditive
                                  combinatorics by Terence Tao and Van H.
                                  Vu . . . . . . . . . . . . . . . . . . . 24--26
       Brittany Terese Fasy and   
               David L. Millman   Review of \booktitleDiscrete and
                                  computational geometry by Satyan L.
                                  Devadoss and Joseph O'Rourke . . . . . . 27--30
                     Yang D. Li   Review of \booktitleIterative methods in
                                  combinatorial optimization by Lap Chi
                                  Lau, R. Ravi and Mohit Singh . . . . . . 31--34
                 S. C. Coutinho   Review of \booktitlePerspectives on
                                  projective geometry by Jürgen
                                  Richter-Gebert . . . . . . . . . . . . . 34--37
                Nicholas Mattei   Review of \booktitleWho's #1?: the
                                  science of ranking and rating by Amy N.
                                  Langville and Carl D. Meyer  . . . . . . 38--40
                  Shiva Kintali   Review of \booktitleBoosting:
                                  foundations and algorithms by Robert E.
                                  Schapire and Yoav Freund . . . . . . . . 41--43
                    Dean Kelley   Technical report column  . . . . . . . . 44--46
           Lane A. Hemaspaandra   SIGACT news complexity theory column 81  47--47
                 Michael Lampis   Guest column: the elusive
                                  inapproximability of the TSP . . . . . . 48--65
              Jennifer L. Welch   Distributed computing column 53:
                                  Dagstuhl seminar review: consistency in
                                  distributed systems  . . . . . . . . . . 66--66
              Bettina Kemme and   
       André Schiper and   
              G. Ramalingam and   
                   Marc Shapiro   Dagstuhl seminar review: consistency in
                                  distributed systems  . . . . . . . . . . 67--89
                   Rob van Stee   SIGACT news online algorithms column 23  90--90
                  Marek Chrobak   Online aggregation problems  . . . . . . 91--102

ACM SIGACT News
Volume 45, Number 2, June, 2014

                William Gasarch   The book review column . . . . . . . . . 7--9
                    Daniel Apon   Review of \booktitleSelected papers on
                                  discrete mathematics by Donald E. Knuth  10--13
                    Daniel Apon   Review of \booktitleSelected papers on
                                  design of algorithms by Donald E. Knuth  14--16
                William Gasarch   Review of \booktitleSelected papers on
                                  fun & games by Donald E. Knuth  . . . . . 17--19
                William Gasarch   Review of \booktitleCompanion to the
                                  papers of Donald Knuth by Donald E.
                                  Knuth  . . . . . . . . . . . . . . . . . 19--21
                William Gasarch   Joint reviews of four articles . . . . . 22--27
          Matthias Gallé   Review of \booktitleBayesian reasoning
                                  and machine learning by David Barber . . 27--29
                  S. V. Nagaraj   Review of \booktitleIntegrated methods
                                  for optimization, second edition, 2012
                                  by John Hooker . . . . . . . . . . . . . 30--32
                  Vaishak Belle   Review of \booktitleProgramming with
                                  higher-order logic by Dale Miller and
                                  Gopalan Nadathur . . . . . . . . . . . . 32--35
                William Gasarch   Review of \booktitlePeople, problems,
                                  and proofs by Richard Lipton and Ken
                                  Regan  . . . . . . . . . . . . . . . . . 36--39
                Nicholas Mattei   Review of \booktitleWho's bigger?: where
                                  historical figures really rank by Steven
                                  Skiena and Charles B. Ward . . . . . . . 40--42
                    Dean Kelley   Technical report column  . . . . . . . . 43--45
           Lane A. Hemaspaandra   SIGACT news complexity theory column 82  46--46
          Alexander Okhotin and   
                    Kai Salomaa   Complexity of input-driven pushdown
                                  automata . . . . . . . . . . . . . . . . 47--67
          Adrian Dumitrescu and   
           Csaba D. Tóth   Computational geometry column 59 . . . . 68--72
              Jennifer L. Welch   Distributed computing column 54:
                                  Transactional memory: models and
                                  algorithms . . . . . . . . . . . . . . . 73--73
             Gokarna Sharma and   
                   Costas Busch   Transactional memory: models and
                                  algorithms . . . . . . . . . . . . . . . 74--103

ACM SIGACT News
Volume 45, Number 3, September, 2014

                William Gasarch   The book review column . . . . . . . . . 7--9
           Subhayan Roy Moulick   Review of \booktitleUnderstanding
                                  cryptography: a textbook for students
                                  and practitioners by Christof Paar and
                                  Jan Pelzl  . . . . . . . . . . . . . . . 10--12
                William Gasarch   Review of \booktitleThe Erd\Hos distance
                                  problem by Julia Garibaldi, Alex
                                  Iosevich and Steven Senger . . . . . . . 13--14
        Mohsen Mahmoudi Aznaveh   Review of \booktitleClustering in
                                  bioinformatics and drug design by John
                                  D. MacCuish and Norah E. MacCuish  . . . 15--17
                  Jonathan Katz   Review of \booktitleThe block cipher
                                  companion by Lars R. Knudsen and Matthew
                                  J. B. Robshaw  . . . . . . . . . . . . . 18--20
                  Jonathan Katz   Review of \booktitleNetworked life: 20
                                  questions and answers by Mung Chiang . . 21--23
          Michaël Cadilhac   Review of \booktitleGraph structure and
                                  monadic second-order logic: a
                                  language-theoretic approach by Bruno
                                  Courcelle and Joost Engelfriet . . . . . 24--25
            Kipper Fletez-Brant   Review of \booktitleBasic phylogenetic
                                  combinatorics by Andreas Dress,
                                  Katharina T. Huber, Jacobus Koolen,
                                  Vincent Moulton and Andreas Spillner . . 26--28
                     Haim Kilov   Review of \booktitleThe universal
                                  computer: the road from Leibniz to
                                  Turing by Martin Davis . . . . . . . . . 29--31
      Miklós Bóna   Review of \booktitleAnalytic
                                  combinatorics in several variables by
                                  Robin Pemantle and Mark Wilson . . . . . 32--33
     László Kozma   Review of \booktitleThe tower of Hanoi:
                                  myths and maths by Andreas M. Hinz,
                                  Sandi Klavzar, Uroz Milutinovi\'c and
                                  Ciril Petr . . . . . . . . . . . . . . . 34--36
                    Dean Kelley   Technical report column  . . . . . . . . 37--46
             Paul T. Scheid and   
               Ari J. Spilo and   
                  Ron K. Cytron   Inferring memory map instructions  . . . 47--52
           Lane A. Hemaspaandra   SIGACT news complexity theory column 83  53--53
           Lane A. Hemaspaandra   Beautiful structures: an appreciation of
                                  the contributions of Alan Selman . . . . 54--70
              Jennifer L. Welch   Distributed computing column 55: WTTM
                                  2013 review, and lower bounds for
                                  distributed quantum computing  . . . . . 71--71
Magnús Halldórsson and   
                 Calvin Newport   Making wireless algorithm theory more
                                  useful: five ideas from the 2013
                                  workshop on realistic models for
                                  algorithms in wireless networks  . . . . 72--74
         Claire Capdevielle and   
                   Sandeep Hans   WTTM 2013, the Fifth Workshop on the
                                  Theory of Transactional Memory . . . . . 75--81
              Heger Arfaoui and   
              Pierre Fraigniaud   What can be computed without
                                  communications?  . . . . . . . . . . . . 82--104
                   Rob van Stee   SIGACT news online algorithms column 24:
                                  2014 so far  . . . . . . . . . . . . . . 105--111

ACM SIGACT News
Volume 45, Number 4, December, 2014

                William Gasarch   The Book Review Column . . . . . . . . . 14--16
                     Haim Kilov   Review of \booktitleThe Universal
                                  Computer. The Road from Leibniz to
                                  Turing by Martin Davis . . . . . . . . . 17--20
               John Tucker Bane   Review of \booktitleFrom Zero to
                                  Infinity by Constance Reid . . . . . . . 21--23
             Krishnan Narayanan   Review of \booktitleThe LLL Algorithm,
                                  edited by Phong Q. Nguyen and Brigitte
                                  Vallée  . . . . . . . . . . . . . . . . . 24--31
                  Arya Mazumdar   Review of \booktitleClassic Papers in
                                  Combinatorics Edited by Ira Gessel and
                                  Gian-Carlo Rota  . . . . . . . . . . . . 32--35
               John Tucker Bane   Review of \booktitleMathematical Treks
                                  by Ivars Peterson  . . . . . . . . . . . 36--38
                    Eowyn Cenek   Review of \booktitleSix Sources of
                                  Collapse by Charles R. Hadlock . . . . . 38--40
             Aravind Srinivasan   Review of \booktitleVisions of Infinity:
                                  The Great Mathematical Problems by Ian
                                  Stewart  . . . . . . . . . . . . . . . . 41--45
                William Gasarch   Review of \booktitleThe Satisfiability
                                  Problem: Algorithms and Analyses by Uwe
                                  Schöning and Jacobo Torán  . . . . . . . . 45--47
                    Dean Kelley   Technical Report Column  . . . . . . . . 48--57
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 84  58--58
            C. Glaßer and   
                  A. Hughes and   
               A. L. Selman and   
                      N. Wisiol   Disjoint NP-Pairs and Propositional
                                  Proof Systems  . . . . . . . . . . . . . 59--75
          Adrian Dumitrescu and   
                  Minghui Jiang   Computational Geometry Column 60 . . . . 76--82
                   Martin Grohe   Database Theory Column Report on PODS
                                  2014 . . . . . . . . . . . . . . . . . . 83--85
              Jennifer L. Welch   Distributed Computing Column 56: Annual
                                  Review 2014  . . . . . . . . . . . . . . 86--88
                Oksana Denysyuk   Review of PODC 2014  . . . . . . . . . . 89--93
               Merav Parter and   
                 Edward Talmage   DISC 2014 Review . . . . . . . . . . . . 94--99
                    Mira Radeva   Review of BDA Workshop 2014  . . . . . . 100--104
                    Zhiyi Huang   SIGACT News Online Algorithms Column 25:
                                  Online Primal Dual: Beyond Linear
                                  Programs . . . . . . . . . . . . . . . . 105--119


ACM SIGACT News
Volume 46, Number 1, March, 2015

                William Gasarch   The Book Review Column . . . . . . . . . 8--9
           Subhayan Roy Moulick   Review of: \booktitleDigital Signatures
                                  by Jonathan Katz . . . . . . . . . . . . 10--12
                William Gasarch   Review of: \booktitleA Walk Through
                                  Combinatorics by Miklós Bóna . . . . . . . 13--14
                    Omar Shehab   Review of: A Wealth of Numbers: An
                                  Anthology of 500 Years of Popular
                                  Mathematics Writing by Benjamin
                                  Wardhaugh  . . . . . . . . . . . . . . . 15--19
                Shoshana Marcus   Review of: \booktitleA Guide to
                                  Experimental Algorithmics by Catherine
                                  C. McGeoch . . . . . . . . . . . . . . . 20--22
                 Rajesh Chitnis   Review of: \booktitleFundamentals of
                                  Parameterized Complexity by Rodney G.
                                  Downey and Michael R. Fellows  . . . . . 23--26
                    Eowyn Cenek   Review of: \booktitleThe King of
                                  Infinite Space: Euclid and his Elements
                                  by David Berlinski . . . . . . . . . . . 27--27
                    Dean Kelley   Technical Report Column  . . . . . . . . 28--38
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 85  39--39
         Cristian S. Calude and   
               Elena Calude and   
             Michael J. Dinneen   Guest Column: Adiabatic Quantum
                                  Computing Challenges . . . . . . . . . . 40--61
              Jennifer L. Welch   Distributed Computing Column 57:
                                  Distributed Algorithms as Combinatorial
                                  Structures . . . . . . . . . . . . . . . 62--62
            Keren Censor-Hillel   Distributed Algorithms as Combinatorial
                                  Structures . . . . . . . . . . . . . . . 63--76

ACM SIGACT News
Volume 46, Number 2, June, 2015

                 Frederic Green   The Book Review Column . . . . . . . . . 10--12
                William Gasarch   Review of: \booktitleThe Cult of
                                  Pythagoras: Math and Myths by Alberto A.
                                  Martinez . . . . . . . . . . . . . . . . 13--15
                William Gasarch   Review of: \booktitleInfinitesimal: How
                                  a dangerous mathematical theory shaped
                                  the modern world by Amir Alexander . . . 16--18
                William Gasarch   Review of: \booktitleMartin Gardner in
                                  the Twenty-First Century: Edited by
                                  Michael Henle and Brian Hopkins  . . . . 19--20
                William Gasarch   Review of: \booktitleAlgorithmic
                                  Barriers Falling: P=NP? by Donald E.
                                  Knuth and Edgar G. Daylight and
                                  \booktitleThe Essential Knuth by Donald
                                  E. Knuth and Edgar G. Daylight . . . . . 21--22
                William Gasarch   Review of: \booktitleLove and Math: The
                                  Heart of Hidden Reality by Edward
                                  Frenkel  . . . . . . . . . . . . . . . . 23--24
                William Gasarch   Review of: \booktitleStructure and
                                  Randomness: Pages from Year One of a
                                  Mathematical Blog by Terence Tao . . . . 25--27
                    Dean Kelley   Technical Report Column  . . . . . . . . 28--39
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 86:
                                  Introduction to Complexity Theory Column
                                  86 . . . . . . . . . . . . . . . . . . . 40--40
                   O. Weinstein   Information Complexity and the Quest for
                                  Interactive Compression  . . . . . . . . 41--64
     Bernardo Ábrego and   
          Adrian Dumitrescu and   
    Silvia Fernández and   
           Csaba D. Tóth   Computational Geometry Column 61 . . . . 65--77
              Jennifer L. Welch   Distributed Computing Column 58: Maurice
                                  Herlihy's 60th Birthday Celebration  . . 78--78
              Vassos Hadzilacos   A Quarter-Century of Wait-Free
                                  Synchronization  . . . . . . . . . . . . 79--88
                     Tim Harris   Hardware Trends: Challenges and
                                  Opportunities in Distributed Computing   89--95
                  Michael Scott   Transactional Memory Today . . . . . . . 96--104
                   Rob van Stee   SIGACT News Online Algorithms Column 26:
                                  Bin packing in multiple dimensions . . . 105--112

ACM SIGACT News
Volume 46, Number 3, September, 2015

                 Frederic Green   The Book Review Column . . . . . . . . . 5--6
                 S. C. Coutinho   Review of: \booktitleGames and
                                  Mathematics: Subtle Connections by David
                                  Wells  . . . . . . . . . . . . . . . . . 7--10
                Shoshana Marcus   Review of: \booktitleJewels of
                                  Stringology by Maxime Crochemore and
                                  Wojciech Rytter  . . . . . . . . . . . . 11--14
          Matthias Gallé   Review of: \booktitleAlgorithms on
                                  Strings by Maxime Crochemore, Christophe
                                  Hancart and Thierry Lecroq . . . . . . . 15--16
       Brittany Terese Fasy and   
               David L. Millman   Review of: \booktitlePolyhedral and
                                  Algebraic Methods in Computational
                                  Geometry by Michael Joswig and Thorsten
                                  Theobald . . . . . . . . . . . . . . . . 17--20
                  S. V. Nagaraj   Review of: \booktitleA Mathematical
                                  Orchard --- Problems and Solutions by
                                  Mark Krusemeyer, George Gilbert, and
                                  Loren Larson . . . . . . . . . . . . . . 21--22
                    Dean Kelley   Technical Report Column  . . . . . . . . 23--35
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 87:
                                  Introduction to Complexity Theory Column
                                  87 . . . . . . . . . . . . . . . . . . . 36--36
            Giovanni Pighizzini   Guest Column: One-Tape Turing Machine
                                  Variants and Language Recognition  . . . 37--55
              Jennifer L. Welch   Distributed Computing Column 59:
                                  Resource-Competitive Algorithms  . . . . 56--56
          Michael A. Bender and   
          Jeremy T. Fineman and   
           Mahnush Movahedi and   
                 Jared Saia and   
                Varsha Dani and   
               Seth Gilbert and   
                Seth Pettie and   
                  Maxwell Young   Resource-Competitive Algorithms  . . . . 57--71

ACM SIGACT News
Volume 46, Number 4, December, 2015

                 Frederic Green   The Book Review Column . . . . . . . . . 4--5
                 Frederic Green   Review of: \booktitleIncredible Numbers
                                  by Ian Stewart . . . . . . . . . . . . . 6--8
                William Gasarch   Review of \booktitleMathematics Galore:
                                  The First Five Years of the St. Marks'
                                  Institute of Mathematics by James Tanton 9--11
               John Tucker Bane   Review of: \booktitleMath Bytes 5 of
                                  Math Bytes by Tim Chartier . . . . . . . 12--13
                  Shiva Kintali   Review of \booktitleAlgorithms Unplugged
                                  by B. Vöcking, H. Alt, M. Dietzfelbinger,
                                  R. Reischuk, C. Scheideler, H. Vollmer,
                                  and D. Wagner: The Power of Algorithms
                                  by Giorgio Ausiello and Rossella
                                  Petreschi  . . . . . . . . . . . . . . . 14--16
                  S. V. Nagaraj   Review of: \booktitleHandbook of Finite
                                  Fields by Gary L. Mullen and Daniel
                                  Panario  . . . . . . . . . . . . . . . . 17--18
                    Dean Kelley   Technical Report Column  . . . . . . . . 19--30
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column
                                  88/89: Introduction to Complexity Theory
                                  Column 88/89 . . . . . . . . . . . . . . 31--31
          Michael A. Forbes and   
                   Amir Shpilka   Complexity Theory Column 88: Challenges
                                  in Polynomial Factorization  . . . . . . 32--49
           Benjamin Rossman and   
          Rocco A. Servedio and   
                    Li-Yang Tan   Complexity Theory Column 89: The
                                  Polynomial Hierarchy, Random Oracles,
                                  and Boolean Circuits . . . . . . . . . . 50--68
                  Jean Cardinal   Computational Geometry Column 62 . . . . 69--78
                Diego Calvanese   Report on PODS 2015  . . . . . . . . . . 79--81
              Jennifer L. Welch   Distributed Computing Column 60: Annual
                                  Review 2015  . . . . . . . . . . . . . . 82--83
               Leonid Barenboim   Distributed Symmetry: Breaking from a
                                  Local Point of View  . . . . . . . . . . 84--87
                      Marc Bury   SIROCCO 2015 Review  . . . . . . . . . . 88--93
                    Lewis Tseng   PODC 2015 Review . . . . . . . . . . . . 94--102
                Hillel Avni and   
                Rati Gelashvili   DISC 2015 Review . . . . . . . . . . . . 103--106


ACM SIGACT News
Volume 47, Number 1, March, 2016

                 Frederic Green   The Book Review Column . . . . . . . . . 4--5
                     Haris Aziz   Review of: \booktitleThe Nature of
                                  Computation by Cristopher Moore and
                                  Stephan Mertens  . . . . . . . . . . . . 6--8
                 Frederic Green   Review of: \booktitleThe Nature of
                                  Computation by Cristopher Moore and
                                  Stephan Mertens  . . . . . . . . . . . . 9--11
                    Steven Kelk   Review of \booktitleReCombinatorics: The
                                  Algorithmics of Ancestral Recombination
                                  Graphs and Explicit Phylogenetic
                                  Networks by Dan Gusfield . . . . . . . . 12--15
                William Gasarch   Review of \booktitleWhat is College
                                  For?: The Public Purpose of Higher
                                  Education by Ellen Condliffe Lagemann
                                  and Harry Lewis  . . . . . . . . . . . . 16--20
                William Gasarch   Review of \booktitleSlicing the Truth:
                                  On the Computability Theoretic and
                                  Reverse Mathematical Analysis of
                                  Combinatorial Principles by Denis
                                  Hirschfeldt  . . . . . . . . . . . . . . 21--24
                William Gasarch   Review of \booktitleThe Scholar and the
                                  State: In Search of Van der Waerden by
                                  Alexander Soifer . . . . . . . . . . . . 25--28
                    Dean Kelley   Technical Report Column  . . . . . . . . 29--40
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 90:
                                  Introduction to Complexity Theory Column
                                  90 . . . . . . . . . . . . . . . . . . . 41--41
              Jason Teutsch and   
                  Marius Zimand   A Brief on Short Descriptions  . . . . . 42--67
              Jennifer L. Welch   Distributed Computing Column 61:
                                  Distributed Algorithmic Foundations of
                                  Dynamic Networks . . . . . . . . . . . . 68--68
             John Augustine and   
          Gopal Pandurangan and   
                 Peter Robinson   Distributed Algorithmic Foundations of
                                  Dynamic Networks . . . . . . . . . . . . 69--98
                   Rob van Stee   SIGACT News Online Algorithms Column 27:
                                  Online Matching on the Line, Part 1  . . 99--110

ACM SIGACT News
Volume 47, Number 2, June, 2016

                 Frederic Green   The Book Review Column . . . . . . . . . 4--5
                 Frederic Green   Review of: \booktitlePrimality Testing
                                  for Beginners by Lasse Rempe-Gillen and
                                  Rebecca Waldecker  . . . . . . . . . . . 6--9
                William Gasarch   Review of: \booktitleThe Joy of
                                  Factoring by Samuel Wagstaff . . . . . . 10--11
                William Gasarch   Review of: \booktitleAsymptopia by Joel
                                  Spencer and Laura Florescu . . . . . . . 12--13
                William Gasarch   Review of: \booktitleRamsey Theory over
                                  the Integers (Second Edition) by Bruce
                                  M. Landman and Aaron Robertson . . . . . 14--17
                 Jalaj Upadhyay   Review of: \booktitleDistributed
                                  Computing Through Combinatorial Topology
                                  by Maurice Herlihy and Dmitry Kozlov and
                                  Sergio Rajsbaum  . . . . . . . . . . . . 18--20
                    Dean Kelley   Technical Report Column  . . . . . . . . 21--33
                 Rolf Klein and   
                Elmar Langetepe   Computational Geometry Column 63 . . . . 34--39
                   Rob van Stee   SIGACT News Online Algorithms Column 28:
                                  Online Matching on the Line, Part 2  . . 40--51
              Jennifer L. Welch   Distributed Computing Column 62:
                                  Decidability in Parameterized
                                  Verification . . . . . . . . . . . . . . 52--52
             Roderick Bloem and   
                Swen Jacobs and   
             Ayrat Khalimov and   
                Igor Konnov and   
                Sasha Rubin and   
               Helmut Veith and   
                   Josef Widder   Decidability in Parameterized
                                  Verification . . . . . . . . . . . . . . 53--64
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 91  65--65
             Alexander Razborov   Guest Column: Proof Complexity and
                                  Beyond . . . . . . . . . . . . . . . . . 66--86

ACM SIGACT News
Volume 47, Number 3, September, 2016

                 Frederic Green   The Book Review Column . . . . . . . . . 5--6
                 Frederic Green   Review of: \booktitleQuantum Algorithms
                                  via Linear Algebra by Richard J. Lipton
                                  and Kenneth W. Regan . . . . . . . . . . 7--11
           Subhayan Roy Moulick   Review of: \booktitleQuantum Information
                                  Theory by Mark M. Wilde  . . . . . . . . 12--14
                    Steven Kelk   Review of: \booktitleGenome-Scale
                                  Algorithm Design (Biological sequence
                                  analysis in the era of high-throughput
                                  sequencing) by Veli Mäkinen, Djamal
                                  Belazzougui, Fabio Cunial and Alexandru
                                  I. Tomescu . . . . . . . . . . . . . . . 15--18
              George Ledin, Jr.   Review of: \booktitleThe Mathematics of
                                  Encryption: An Elementary Introduction
                                  by Margaret Cozzens and Steven J. Miller 19--21
                  S. V. Nagaraj   Review of: \booktitleMathematics
                                  Everywhere by Martin Aigner and Ehrhard
                                  Behrends (Eds.)  . . . . . . . . . . . . 22--24
                    Dean Kelley   Technical Report Column  . . . . . . . . 25--38
                William Gasarch   Open Problems About Grid Coloring and
                                  The Complexity of Grid Colorings . . . . 39--43
           Lane A. Hemaspaandra   \booktitleSIGACT News Complexity Theory
                                  Column 93  . . . . . . . . . . . . . . . 44--45
           Swastik Kopparty and   
                Shubhangi Saraf   Guest Column: Local Testing and Decoding
                                  of High-Rate Error-Correcting Codes  . . 46--66
                 Wang-Chiew Tan   Database Theory Column: Report on PODS
                                  2016 . . . . . . . . . . . . . . . . . . 67--68
              Jennifer L. Welch   Distributed Computing Column 63: a Note
                                  on Fault-tolerant Consensus in Directed
                                  Networks . . . . . . . . . . . . . . . . 69--69
                Lewis Tseng and   
                Nitin H. Vaidya   A Note on Fault-tolerant Consensus in
                                  Directed Networks  . . . . . . . . . . . 70--91
                   Rob van Stee   \booktitleSIGACT News Online Algorithms
                                  Column 29  . . . . . . . . . . . . . . . 92--92
                 Joan Boyar and   
          Lene M. Favrholdt and   
           Christian Kudahl and   
              Kim S. Larsen and   
            Jesper W. Mikkelsen   Online Algorithms with Advice: a Survey  93--129

ACM SIGACT News
Volume 47, Number 4, December, 2016

                 Frederic Green   The Book Review Column . . . . . . . . . 4--5
                William Gasarch   Review of: \booktitleTuring
                                  Computability: Theory and Applications
                                  by Robert Soare  . . . . . . . . . . . . 6--8
                    Daniel Apon   Review of: \booktitleAnalysis of Boolean
                                  Functions by Ryan O'Donnell  . . . . . . 9--12
             Ramon de Vera, Jr.   Review of: \booktitleDistributed
                                  Systems: an Algorithmic Approach (2nd
                                  Edition) by Sukumar Ghosh  . . . . . . . 13--14
          Michaël Cadilhac   Review of: \booktitleThe Golden Ratio
                                  and Fibonacci Numbers by Richard A.
                                  Dunlap . . . . . . . . . . . . . . . . . 15--17
                 Frederic Green   Review of: \booktitleThe Fascinating
                                  World of Graph Theory by Arthur
                                  Benjamin, Gary Chartrand and Ping Zhang  18--21
                    Dean Kelley   Technical Report Column  . . . . . . . . 22--32
              Jennifer L. Welch   Distributed Computing Column 64: Annual
                                  Review 2016  . . . . . . . . . . . . . . 33--34
             Gregory Schwarzman   PODC 2016 Review . . . . . . . . . . . . 35--38
                        Lili Su   DISC 2016 Review . . . . . . . . . . . . 39--43
              Adrian Dumitrescu   Computational Geometry Column 64 . . . . 44--47


ACM SIGACT News
Volume 48, Number 1, March, 2017

                 Frederic Green   The Book Review Column . . . . . . . . . 8--9
                 Frederic Green   Review of \booktitleArt in the Life of
                                  Mathematicians by Anna Kepes Szemerédi    10--17
                Allan M. Miller   Review of \booktitlePractical Data
                                  Science with R by Nina Zumel and John
                                  Mount  . . . . . . . . . . . . . . . . . 18--22
                  S. V. Nagaraj   Review of \booktitleAlgebraic Coding
                                  Theory Revised Edition by Elwyn
                                  Berlekamp  . . . . . . . . . . . . . . . 23--26
                    Dean Kelley   Technical Report Column  . . . . . . . . 27--37
                William Gasarch   Open Problems Column . . . . . . . . . . 38--38
                 Emanuele Viola   Selected challenges in computational
                                  lower bounds . . . . . . . . . . . . . . 39--45
                   Rob van Stee   \booktitleSIGACT News Online Algorithms
                                  Column 30: 2016 in review  . . . . . . . 46--53
              Jennifer L. Welch   Distributed Computing Column 65:
                                  Automatic Synthesis of Distributed
                                  Protocols and SIROCCO 2016 Review  . . . 54--54
                Rajeev Alur and   
               Stavros Tripakis   Automatic Synthesis of Distributed
                                  Protocols  . . . . . . . . . . . . . . . 55--90
                    Lewis Tseng   SIROCCO 2016 Review  . . . . . . . . . . 91--100
           Lane A. Hemaspaandra   \booktitleSIGACT News Complexity Theory
                                  Column 93  . . . . . . . . . . . . . . . 101--101
             Stephen Fenner and   
               Rohit Gurjar and   
                Thomas Thierauf   Guest Column: Parallel Algorithms for
                                  Perfect Matching . . . . . . . . . . . . 102--109

ACM SIGACT News
Volume 48, Number 2, June, 2017

                 Frederic Green   The Book Review Column . . . . . . . . . 4--6
               Robin Belton and   
           Brittany Terese Fasy   Review of \booktitleThe Structure and
                                  Stability of Persistence Modules by
                                  Frédéric Chazal, Vin de Silva, Marc
                                  Glisse, and Steve Oudot  . . . . . . . . 7--11
                 Frederic Green   Review of \booktitleQuantum Walks and
                                  Search Algorithms by Renato Portugal . . 12--15
                 Frederic Green   Joint Review of \booktitleThe Magic of
                                  Math by Arthur Benjamin and
                                  \booktitleHow to Bake by Eugenia Cheng   16--20
                    Dean Kelley   Technical Report Column  . . . . . . . . 21--33
                William Gasarch   Open Problems Column . . . . . . . . . . 34--39
           Lane A. Hemaspaandra   \booktitleSIGACT News Complexity Theory
                                  Column 94  . . . . . . . . . . . . . . . 40--40
     Srinivasan Arunachalam and   
                 Ronald de Wolf   Guest Column: a Survey of Quantum
                                  Learning Theory  . . . . . . . . . . . . 41--67
                   Micha Sharir   Computational Geometry Column 65 . . . . 68--85
              Jennifer L. Welch   Distributed Computing Column 66:
                                  Algorithmic Foundations of Programmable
                                  Matter Dagstuhl Seminar 16271  . . . . . 86--86
    Sándor P. Fekete and   
        Andréa Richa and   
             Kay Römer and   
           Christian Scheideler   Algorithmic Foundations of Programmable
                                  Matter Dagstuhl Seminar 16271  . . . . . 87--94

ACM SIGACT News
Volume 48, Number 3, September, 2017

                 Frederic Green   The Book Review Column . . . . . . . . . 4--6
                 Frederic Green   Review of \booktitleSet Theory: a First
                                  Course by Daniel W. Cunningham . . . . . 7--9
                    Steve Homer   Review of \booktitleCrypto School by
                                  Joachim von zur Gathen . . . . . . . . . 10--13
                Allan M. Miller   Review of \booktitleR for Data Science:
                                  Import, Tidy, Transform, Visualize, and
                                  Model Data by Hadley Wickham and Garrett
                                  Grolemund  . . . . . . . . . . . . . . . 14--19
                    Dean Kelley   Technical Report Column  . . . . . . . . 20--31
            William Gasarch and   
       Brittany Terese Fasy and   
                       Bei Wang   Open Problems in Computational Topology  32--36
             Ryan O'Donnell and   
                    John Wright   Guest Column: a Primer on the Statistics
                                  of Longest Increasing Subsequences and
                                  Quantum States (Shortened Version) . . . 37--59
              Jennifer L. Welch   Distributed Computing Column 67: Review
                                  of 2016 BIRS CMO Workshop on Complexity
                                  and Analysis of Distributed Algorithms   60--67
          Christoph Ambühl   \booktitleSIGACT News Online Algorithms
                                  Column 31  . . . . . . . . . . . . . . . 68--82
               Artur Czumaj and   
               Stefano Leonardi   HALG: Highlights of Algorithms . . . . . 83--86

ACM SIGACT News
Volume 48, Number 4, December, 2017

                 Frederic Green   The Book Review Column . . . . . . . . . 4--6
            Vincenzo Liberatore   Review of \booktitleCommunication
                                  Networks: an Optimization, Control, and
                                  Stochastic Networks Perspective, R.
                                  Srikant and L. Ying  . . . . . . . . . . 7--12
                  S. V. Nagaraj   Review of \booktitleHandbook of
                                  Computational Social Choice Edited by
                                  Felix Brandt, Vincent Conitzer, Ulle
                                  Endriss, Jérôme Lang, and Ariel D.
                                  Procaccia  . . . . . . . . . . . . . . . 13--17
                William Gasarch   Review of \booktitleRamsey Theory for
                                  Discrete Structures by Hans Jürgen Prömel  18--21
                    Dean Kelley   Technical Report Column  . . . . . . . . 22--34
                William Gasarch   Open Problems Column . . . . . . . . . . 35--41
              Lane Hemaspaandra   SIGACT News Complexity Theory Column 96  42--42
                  D. Baumeister   Guest Column: Complexity of Verification
                                  in Abstract Argumentation Frameworks . . 43--56
          Khaled Elbassioni and   
              Adrian Dumitrescu   Computational Geometry Column 66 . . . . 57--74
                  Floris Geerts   Database Theory Column Report on PODS
                                  2017 . . . . . . . . . . . . . . . . . . 75--77
              Jennifer L. Welch   Distributed Computing Column 68  . . . . 78--79
               Christian Konrad   SIROCCO 2017 Review  . . . . . . . . . . 80--86
                  Sepehr Assadi   SPAA 2017 Review . . . . . . . . . . . . 87--90
                   Peter Davies   PODC 2017 Review . . . . . . . . . . . . 91--93
            Manuela Fischer and   
                    Yannic Maus   DISC 2017 Review . . . . . . . . . . . . 94--99
                   Rob van Stee   SIGACT News Online Algorithms Column 32:
                                  2017 in review . . . . . . . . . . . . . 100--109


ACM SIGACT News
Volume 49, Number 1, March, 2018

                 Frederic Green   The Book Review Column . . . . . . . . . 9--11
                 John D. Rogers   Review of \booktitleThe Art of Computer
                                  Programming Fascicle 6 `Satisfiability'
                                  by Donald E. Knuth . . . . . . . . . . . 12--15
              Ramon de Vera Jr.   Review of \booktitleReal-World
                                  Algorithms: a Beginner's Guide by Panos
                                  Louridas . . . . . . . . . . . . . . . . 16--19
                 Frederic Green   Joint Review of \booktitleQuadratic
                                  Residues and Non-Residues by Steve
                                  Wright and \booktitleThe Quadratic
                                  Reciprocity Law by Oswald Baumgart.
                                  Edited and translated by Franz
                                  Lemmermeyer  . . . . . . . . . . . . . . 20--28
                    Dean Kelley   Technical Report Column  . . . . . . . . 29--39
                William Gasarch   Open Problems Column . . . . . . . . . . 40--54
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 97  54--54
                   Neeraj Kayal   Guest Column: a Paradigm for Arithmetic
                                  Circuit Lower Bounds . . . . . . . . . . 55--65
                   Rob van Stee   SIGACT News Online Algorithms Column 33  66--66
               Matthias Englert   The reordering buffer problem on the
                                  line revisited . . . . . . . . . . . . . 67--72
              Jennifer L. Welch   Distributed Computing Column 69 Proving
                                  PACELC and Concurrent Computing Summer
                                  School . . . . . . . . . . . . . . . . . 72--72
                 Wojciech Golab   Proving PACELC . . . . . . . . . . . . . 73--81
                 Petr Kuznetsov   The First Summer School on Practice and
                                  Theory of Concurrent Computing SPTCC
                                  2017 . . . . . . . . . . . . . . . . . . 81--90

ACM SIGACT News
Volume 49, Number 2, June, 2018

                 Frederic Green   The Book Review Column . . . . . . . . . 4--6
                 James V. Rauff   Review of \booktitleWords and Graphs by
                                  Sergey Kitaev and Vadim Lozin  . . . . . 7--9
                 Panos Louridas   Review of \booktitleNetwork Science by
                                  Albert-L\`aaszl\`o Barab\`aasi . . . . . 10--13
                  S. V. Nagaraj   Review of \booktitleTrends in
                                  Computational Social Choice Edited by
                                  Ulle Endriss . . . . . . . . . . . . . . 14--17
                    Dean Kelley   Technical Report Column  . . . . . . . . 18--28
                William Gasarch   Open Problems Column . . . . . . . . . . 29--31
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 98  32--32
          Joshua A. Grochow and   
               David H. Wolpert   Beyond Number of Bit Erasures: New
                                  Complexity Questions Raised by Recently
                                  Discovered Thermodynamic Costs of
                                  Computation  . . . . . . . . . . . . . . 33--56
              Jennifer L. Welch   Distributed Computing Column 70:
                                  Formalizing and Implementing Distributed
                                  Ledger Objects . . . . . . . . . . . . . 57--57
Antonio Fernández Anta and   
             Kishori Konwar and   
          Chryssis Georgiou and   
               Nicolas Nicolaou   Formalizing and Implementing Distributed
                                  Ledger Objects . . . . . . . . . . . . . 58--76
         Bahareh Banyassady and   
              Matias Korman and   
                Wolfgang Mulzer   Computational Geometry Column 67 . . . . 77--94

ACM SIGACT News
Volume 49, Number 3, September, 2018

                 Frederic Green   The Book Review Column . . . . . . . . . 6--8
     László Kozma   Review of \booktitleCompact Data
                                  Structures --- a practical approach by
                                  Gonzalo Navarro  . . . . . . . . . . . . 9--13
                  S. V. Nagaraj   Review of \booktitlePower Up:: Unlocking
                                  the hidden mathematics in video games    14--19
             Aravind Srinivasan   Probability and Computing  . . . . . . . 20--22
                    Dean Kelley   Technical Report Column  . . . . . . . . 23--33
                William Gasarch   Open Problems Column . . . . . . . . . . 34--34
             Stephen Fenner and   
             Frederic Green and   
                   Steven Homer   Fixed-Parameter Extrapolation and
                                  Aperiodic Order: Open Problems . . . . . 35--47
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 99  48--50
       Lane A. Hemaspaandra and   
               Holger Spakowski   Column: Team Diagonalization . . . . . . 51--61
              Jennifer L. Welch   Distributed Computing Column 71: Recent
                                  Algorithmic Advances in Population
                                  Protocols  . . . . . . . . . . . . . . . 62--62
               Dan Alistarh and   
                Rati Gelashvili   Recent Algorithmic Advances in
                                  Population Protocols . . . . . . . . . . 63--73
               Artur Czumaj and   
             Robert Krauthgamer   3rd Highlights of Algorithms (HALG 2018) 74--77
                 Sheng-Hua Teng   2018 Knuth Prize is Awarded to Johan
                                  Håstad  . . . . . . . . . . . . . . . . . 78--79

ACM SIGACT News
Volume 49, Number 4, December, 2018

                 Frederic Green   The Book Review Column . . . . . . . . . 4--6
                 Panos Louridas   Joint Review of \booktitleThe Power of
                                  Networks: Six Principles that Connect
                                  our Lives  . . . . . . . . . . . . . . . 7--10
              Amir Babak Aazami   Review of \booktitleGame Theory, Alive   11--12
                Allan M. Miller   Review of \booktitleModern Data Science  13--16
                    Dean Kelley   Technical Report Column  . . . . . . . . 17--27
                William Gasarch   Open Problems Column . . . . . . . . . . 28--28
  Virginia Vassilevska Williams   Some Open Problems in Fine-Grained
                                  Complexity . . . . . . . . . . . . . . . 29--35
                   Rob van Stee   SIGACT News Online Algorithms Column 34:
                                  2018 in review . . . . . . . . . . . . . 36--45
              Adrian Dumitrescu   Computational Geometry Column 68 . . . . 46--54
                 Marcelo Arenas   Database Theory Column Report on PODS
                                  2018 . . . . . . . . . . . . . . . . . . 55--57
              Jennifer L. Welch   Distributed Computing Column 72: Annual
                                  Review 2018  . . . . . . . . . . . . . . 58--59
                 Fred Schneider   History and Context for Defining
                                  Liveness: Winner 2018 Edsger W. Dijkstra
                                  Prize  . . . . . . . . . . . . . . . . . 60--63
                   Bowen Alpern   Edsger W. Dijkstra: The Man Behind the
                                  Prize  . . . . . . . . . . . . . . . . . 64--65
                   Avery Miller   SIROCCO 2018 Review  . . . . . . . . . . 66--82
                Naama Ben-David   PODC 2018 Review . . . . . . . . . . . . 83--88
          Aditya Biradavolu and   
               Saptaparni Kumar   DISC 2018 Review . . . . . . . . . . . . 89--95


ACM SIGACT News
Volume 50, Number 1, March, 2019

                 Frederic Green   The Book Review Column . . . . . . . . . 7--8
                 Frederic Green   Review of \booktitleNumber Theory: an
                                  Introduction via the Density of Primes,
                                  second edition . . . . . . . . . . . . . 9--13
                  S. V. Nagaraj   Review of \booktitleCodes, Cryptology
                                  and Curves with Computer Algebra . . . . 14--16
                    Dean Kelley   Technical Report Column  . . . . . . . . 17--27
                William Gasarch   Open Problems Column . . . . . . . . . . 28--34
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 100 35--37
             William I. Gasarch   Guest Column: The Third P =? NP Poll . . 38--59
              Jennifer L. Welch   Distributed Computing Column 73 SPAA
                                  2018 Review  . . . . . . . . . . . . . . 60--60
                 Laxman Dhulipa   SPAA 2018 Review . . . . . . . . . . . . 61--64
                    Graham Farr   Using Go in teaching the theory of
                                  computation  . . . . . . . . . . . . . . 65--78
                Ding-Zhu Du and   
                       Jie Wang   In Memoriam: Ker-I Ko (1950--2018) . . . 79--79

ACM SIGACT News
Volume 50, Number 2, June, 2019

                 Frederic Green   The Book Review Column . . . . . . . . . 4--5
                William Gasarch   Review of \booktitleQ is for Quantum by
                                  Terry Rudolph  . . . . . . . . . . . . . 6--8
                William Gasarch   Review of \booktitleAn Introduction to
                                  Ramsey Theory: Fast Functions, Infinity,
                                  and Metamathematics by Matthew Katz and
                                  Jan Reimann  . . . . . . . . . . . . . . 9--11
                 Frederic Green   Review of \booktitleModern Cryptography
                                  and Elliptic Curves, A Beginner's Guide
                                  by Thomas R. Shemanske . . . . . . . . . 12--14
                    Dean Kelley   Technical Report Column  . . . . . . . . 15--27
                William Gasarch   Open Problems Column . . . . . . . . . . 28--28
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 101 29--30
            William Gasarch and   
           Scott Huddleston and   
                  Erik Metz and   
                    Jacob Prinz   Guest Column: The Muffin Problem . . . . 31--60
              Jennifer L. Welch   Distributed Computing Column 74 Survey
                                  of Reconfigurable Data Center Networks   61--61
       Klaus-Tycho Foerster and   
                  Stefan Schmid   Survey of Reconfigurable Data Center
                                  Networks: Enablers, Algorithms,
                                  Complexity . . . . . . . . . . . . . . . 62--79

ACM SIGACT News
Volume 50, Number 3, September, 2019

                 Frederic Green   The Book Review Column . . . . . . . . . 4--5
                 Frederic Green   Review of Handbook of Graph Theory,
                                  Combinatorial Optimization, and
                                  Algorithms . . . . . . . . . . . . . . . 6--11
                    Dean Kelley   Technical Report Column  . . . . . . . . 12--23
                William Gasarch   Open Problems Column . . . . . . . . . . 24--24
                Dana Moshkovitz   Sliding Scale Conjectures in PCP . . . . 25--33
              Jennifer L. Welch   Distributed Computing Column 75 The
                                  Splendors and Miseries of Rounds . . . . 34--34
                     Adam Shimi   The Splendors and Miseries of Rounds . . 35--50
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 102 51--51
                 Emanuele Viola   Guest Column: Non-abelian Combinatorics
                                  and Communication Complexity . . . . . . 52--74
          Adrian Dumitrescu and   
                  Minghui Jiang   Computational Geometry Column 69 . . . . 75--90
             Michael W. Mahoney   The Difficulties of Addressing
                                  Interdisciplinary Challenges at the
                                  Foundations of Data Science  . . . . . . 91--95

SIGACT
Volume 50, Number 4, December, 2019

                 Frederic Green   The Book Review Column . . . . . . . . . 4--6
                William Gasarch   Review of \booktitleFactor Man by Matt
                                  Ginsberg . . . . . . . . . . . . . . . . 7--8
                    Hadi Shafei   Review of \booktitleKolmogorov
                                  Complexity and Algorithmic Randomness by
                                  A. Shen, V. A. Uspensky, and N.
                                  Vereshchagin . . . . . . . . . . . . . . 9--13
                    Dean Kelley   Technical Report Column  . . . . . . . . 14--25
                William Gasarch   Open Problems Column . . . . . . . . . . 26--30
                   Dan Alistarh   Distributed Computing Column 76: Annual
                                  Review 2019  . . . . . . . . . . . . . . 31--32
            Naama Ben-David and   
               Yi-Jun Chang and   
                Michal Dory and   
               Dean Leitersdorf   PODC 2019 Review . . . . . . . . . . . . 33--45
           Sebastian Brandt and   
            Manuela Fischer and   
                     Jara Uitto   SIROCCO 2019 Review  . . . . . . . . . . 46--47
                 Petr Kuznetsov   Review of the Second Sankt Petersburg
                                  Summer School on Practice and Theory of
                                  Distributed Computing (SPTDC 2019) . . . 48--55
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 103 56--56
           Aviad Rubinstein and   
  Virginia Vassilevska Williams   SETH vs Approximation  . . . . . . . . . 57--76
           Felix Höhne and   
         Sören Schmitt and   
                   Rob van Stee   SIGACT News Online Algorithms Column 35:
                                  2019 in review . . . . . . . . . . . . . 77--92
                 Christoph Koch   Database Theory Column Report on PODS
                                  2019 . . . . . . . . . . . . . . . . . . 93--94


ACM SIGACT News
Volume 51, Number 1, March, 2020

                 Frederic Green   The Book Review Column . . . . . . . . . 7--8
                William Gasarch   Review of \booktitleWhat Can Be
                                  Computed: a Practical Guide to the
                                  Theory of Computation by John MacCormick 9--11
                John MacCormick   Review of Problems with a Point:
                                  Exploring Math and Computer Science  . . 12--14
                    Dean Kelley   Technical Report Column  . . . . . . . . 15--26
            William Gasarch and   
                    Aarav Bajaj   Open Problems Column . . . . . . . . . . 27--36
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 104 37--37
               Sabine Broda and   
         Antonio Machiavelo and   
              Nelma Moreira and   
                   Rogerio Reis   Guest Column: Analytic Combinatorics and
                                  Descriptional Complexity of Regular
                                  Languages on Average . . . . . . . . . . 38--56
                   Dan Alistarh   Distributed Computing Column 77
                                  Consensus Dynamics: an Overview  . . . . 57--57
             Luca Becchetti and   
            Andrea Clementi and   
                Emanuele Natale   Consensus Dynamics: an Overview  . . . . 58--104
                     Binhai Zhu   Computational Geometry Column 70:
                                  Processing Persistence Diagrams as
                                  Purely Geometric Objects . . . . . . . . 105--117
                        Li Chen   How to Write a Good Project Report . . . 118--119

ACM SIGACT News
Volume 51, Number 2, June, 2020

                 Frederic Green   The Book Review Column . . . . . . . . . 4--5
                William Gasarch   Review of \booktitleEssential Discrete
                                  Mathematics for Computer Science by
                                  Harry Lewis and Rachel Zax . . . . . . . 6--8
                    Song Y. Yan   Review of \booktitleApplied Number
                                  Theory . . . . . . . . . . . . . . . . . 9--10
                  S. V. Nagaraj   Review of \booktitleMarket Design: a
                                  Linear Programming Approach to Auctions
                                  and Matching . . . . . . . . . . . . . . 11--14
                    Dean Kelley   Technical Report Column  . . . . . . . . 15--26
                William Gasarch   Open Problems Column . . . . . . . . . . 27--35
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 105 36--37
            Eshan Chattopadhyay   Guest Column: a Recipe for Constructing
                                  Two-Source Extractors  . . . . . . . . . 38--57
                   Dan Alistarh   Distributed Computing Column 78: 60
                                  Years of Mastering Concurrent Computing
                                  through Sequential Thinking  . . . . . . 58--58
            Sergio Rajsbaum and   
                  Michel Raynal   60 Years of Mastering Concurrent
                                  Computing through Sequential Thinking    59--88

ACM SIGACT News
Volume 51, Number 3, September, 2020

                 Frederic Green   The Book Review Column . . . . . . . . . 5--6
                Shoshana Marcus   Review of \booktitleThe Problem With
                                  Software: Why Smart Engineers Write Bad
                                  Code . . . . . . . . . . . . . . . . . . 7--9
               Michele Amoretti   Review of \booktitleElements of Parallel
                                  Computing  . . . . . . . . . . . . . . . 10--13
                William Gasarch   Review of \booktitleTheorems of the 21st
                                  Century: Volume I  . . . . . . . . . . . 14--19
                    Dean Kelley   Technical Report Column  . . . . . . . . 20--30
                William Gasarch   Open Problems Column . . . . . . . . . . 31--31
                 Scott Aaronson   The Busy Beaver Frontier . . . . . . . . 32--54
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column
                                  106: Teaching Models, Computability, and
                                  Complexity in Time of COVID-19 . . . . . 55--58
                      Yufei Tao   Database Theory Column . . . . . . . . . 59--61
                   Dan Alistarh   Distributed Computing Column 79: Using
                                  Round Elimination to Understand Locality 62--62
                  Jukka Suomela   Using Round Elimination to Understand
                                  Locality . . . . . . . . . . . . . . . . 63--81

ACM SIGACT News
Volume 51, Number 4, December, 2020

                 Frederic Green   The Book Review Column1  . . . . . . . . 4--5
              Sarvagya Upadhyay   Review of \booktitleIntroduction To
                                  Property Testing by Oded Goldreich . . . 6--10
                Tim Jackman and   
                    Steve Homer   Review of \booktitleKernelization:
                                  Theory of Parameterized Preprocessing by
                                  Fedor V. Fomin, Daniel Lokshtanov, Saket
                                  Saurabh, and Meirav Zehavi . . . . . . . 11--14
                 Frederic Green   Review of \booktitleForbidden
                                  Configurations in Discrete Geometry by
                                  David Eppstein . . . . . . . . . . . . . 15--17
                    Dean Kelley   Technical Report Column  . . . . . . . . 18--29
                William Gasarch   Open Problems Column Edited by William
                                  Gasarch. This Issue's Column!  . . . . . 30--46
           Lane A. Hemaspaandra   SIGACT News Complexity Theory Column 107 47--47
                   Mark Bun and   
                  Justin Thaler   Guest Column: Approximate Degree in
                                  Classical and Quantum Computing  . . . . 48--72
                   Dan Alistarh   Distributed Computing Column 80: Annual
                                  Review 2020  . . . . . . . . . . . . . . 73--74
            Ahad Mirza Baig and   
              Alkida Balliu and   
               Peter Davies and   
                    Michal Dory   PODC 2020 Review . . . . . . . . . . . . 75--81
             Vitaly Aksenov and   
                 Petr Kuznetsov   Review of the \booktitleThird Summer
                                  School on the Practice and Theory of
                                  Distributed Computing SPTDC 2020 . . . . 82--84
             Vitaly Aksenov and   
                Alexey Fyodorov   Review of the \booktitleHydra Conference
                                  on Concurrent and Distributed Computing
                                  Hydra 2020 . . . . . . . . . . . . . . . 85--88
           Felix Höhne and   
         Sören Schmitt and   
                   Rob van Stee   SIGACT News Online Algorithms Column 36:
                                  2020 in review . . . . . . . . . . . . . 89--107


ACM SIGACT News
Volume 52, Number 1, March, 2021

                 Frederic Green   The Book Review Column . . . . . . . . . 7--8
              Sarvagya Upadhyay   Review of \booktitleAlgorithmic Aspects
                                  of Machine Learning By Ankur Moitra  . . 9--11
                  S. V. Nagaraj   Review of \booktitleNetwork Flow
                                  Algorithms, David P. Williamson  . . . . 12--15
              Stephen A. Fenner   Review of \booktitleThe Theory of
                                  Quantum Information, John Watrous  . . . 16--24
                    Dean Kelley   Technical Report Column  . . . . . . . . 25--35
            William Gasarch and   
                      Erik Metz   Open Problems Column . . . . . . . . . . 36--40
           Lane A. Hemaspaandra   \booktitleSIGACT News Complexity Theory
                                  Column 108 . . . . . . . . . . . . . . . 41--46
                    R. Pass and   
          M. Venkitasubramaniam   Guest Column: Average-case Complexity
                                  Through the Lens of Interactive Puzzles  47--69
                   Dan Alistarh   Distributed Computing Column 81:
                                  Byzantine Agreement with Less
                                  Communication: Recent Advances . . . . . 70--70
                 Shir Cohen and   
                Idit Keidar and   
                      Oded Naor   Byzantine Agreement with Less
                                  Communication: Recent Advances . . . . . 71--80
                        Li Chen   Iteration vs. Recursion: Two Basic
                                  Algorithm Design Methodologies . . . . . 81--86
                 Stephen Fenner   Remembrances of Alan . . . . . . . . . . 87--93

ACM SIGACT News
Volume 52, Number 2, June, 2021

                 Frederic Green   The Book Review Column . . . . . . . . . 4--6
                 Erick Galinkin   Review of \booktitleThe Foundations of
                                  Computability Theory (Second Edition) by
                                  Borut Robic  . . . . . . . . . . . . . . 7--9
                William Gasarch   Review of \booktitleIdeas that Created
                                  the Future: Classic Papers of Computer
                                  Science, Edited by Harry Lewis . . . . . 10--17
                William Gasarch   Review of \booktitleBlown to Bits: Your
                                  Life, Liberty, and Happiness after the
                                  Digital Explosion by Hal Abelson, Ken
                                  Ledeen, Harry Lewis, and Wendy Seltzer   18--23
                    Dean Kelley   Technical Report Column  . . . . . . . . 24--35
                William Gasarch   Hilbert's Tenth Problem: Refinements and
                                  Variants . . . . . . . . . . . . . . . . 36--44
           Lane A. Hemaspaandra   \booktitleSIGACT News Complexity Theory
                                  Column 109 . . . . . . . . . . . . . . . 45--45
                    A. Knop and   
                  S. Lovett and   
                 S. McGuire and   
                        W. Yuan   Guest Column: Models of computation
                                  between decision trees and communication 46--70
                   Rob van Stee   \booktitleSIGACT News Online Algorithms
                                  Column 37  . . . . . . . . . . . . . . . 71--71
            Pavel Veselý   Packet Scheduling: Plans, Monotonicity,
                                  and the Golden Ratio . . . . . . . . . . 72--84
                  Dana Richards   Teaching Nondeterminism  . . . . . . . . 85--90
                   Dan Alistarh   Distributed Computing Column 82
                                  Distributed Computability: a Few Results
                                  Masters Students Should Know . . . . . . 91--91
                  Michel Raynal   Distributed Computability: a Few Results
                                  Masters Students Should Know . . . . . . 92--110

ACM SIGACT News
Volume 52, Number 3, September, 2021

                 Frederic Green   The Book Review Column . . . . . . . . . 3--5
                 Frederic Green   Review of \booktitleMathematics and
                                  Computation by Avi Wigderson . . . . . . 6--10
               Michael Cadilhac   Review of \booktitleCommunication
                                  Complexity and Applications by Anup Rao
                                  and Amir Yehudayoff  . . . . . . . . . . 11--13
                    Dean Kelley   Technical Report Column  . . . . . . . . 14--24
                William Gasarch   Open Problems Column . . . . . . . . . . 25--25
                  Lance Fortnow   Worlds to Die Harder For Open Oracle
                                  Questions for the 21st Century . . . . . 26--36
           Lane A. Hemaspaandra   \booktitleSIGACT News Complexity Theory
                                  Column 110 . . . . . . . . . . . . . . . 37--37
           Carlo Mereghetti and   
                Beatrice Palano   Guest Column: Quantum Finite Automata:
                                  From Theory to Practice  . . . . . . . . 38--59
                   Dan Alistarh   Distributed Computing Column 83 Five
                                  Ways Not To Fool Yourself: Designing
                                  Experiments for Understanding
                                  Performance  . . . . . . . . . . . . . . 60--60
                     Tim Harris   Five Ways Not To Fool Yourself:
                                  Designing Experiments for Understanding
                                  Performance  . . . . . . . . . . . . . . 61--68
               Reinhard Pichler   Database Theory Column Report on PODS
                                  2021 . . . . . . . . . . . . . . . . . . 69--72

ACM SIGACT News
Volume 52, Number 4, December, 2021

                 Frederic Green   The Book Review Column . . . . . . . . . 3--5
                 Frederic Green   Review of \booktitleThree Lectures on
                                  Complexity and Black Holes by Leonard
                                  Susskind . . . . . . . . . . . . . . . . 6--10
            Abdulai Gassama and   
                 Frederic Green   Review of \booktitleA Short Course in
                                  Computational Geometry and Topology by
                                  Herbert Edelsbrunner . . . . . . . . . . 11--14
                  S. V. Nagaraj   Review of \booktitleThe Age of
                                  Algorithms by Serge Abiteboul and Gilles
                                  Dowek  . . . . . . . . . . . . . . . . . 15--17
                    Dean Kelley   Technical Report Column  . . . . . . . . 18--30
        Andrei Romashchenko and   
             Alexander Shen and   
                  Marius Zimand   27 Open Problems in Kolmogorov
                                  Complexity . . . . . . . . . . . . . . . 31--54
           Lane A. Hemaspaandra   \booktitleSIGACT News Complexity Theory
                                  Column 111 . . . . . . . . . . . . . . . 55--55
                   Ben Lee Volk   Guest Column: Algebraic Natural Proofs
                                  Ben Lee Volk . . . . . . . . . . . . . . 56--73
                   Dan Alistarh   Distributed Computing Column 84:
                                  Perspectives on the Paper ``CCS
                                  Expressions, Finite State Processes, and
                                  Three Problems of Equivalence''  . . . . 74--75
              Ezio Bartocci and   
              Michael A. Bender   A Perspective on ``CCS Expressions,
                                  Finite State Processes, and Three
                                  Problems of Equivalence''  . . . . . . . 76--77
                Scott A. Smolka   Kanellakis--Smolka 1983: a Convolution
                                  of Circumstances . . . . . . . . . . . . 78--79
                Felix Hohne and   
              Soren Schmitt and   
                   Rob van Stee   \booktitleSIGACT News Online Algorithms
                                  Column 38: 2021 in review  . . . . . . . 80--96


ACM SIGACT News
Volume 53, Number 1, March, 2022

                 Frederic Green   The Book Review Column . . . . . . . . . 6--8
                William Gasarch   Review of \booktitleTales of
                                  Impossibility: The 2000-Year Quest to
                                  Solve the Mathematical Problems of
                                  Antiquity Author: David Richeson . . . . 9--12
                William Gasarch   Review of \booktitleA Map that Reflects
                                  the Territory: Essays by the LessWrong
                                  Community Author: LessWrong  . . . . . . 13--24
                    Dean Kelley   Technical Report Column  . . . . . . . . 25--35
                Bogdsan Grechuk   On the smallest open Diophantine
                                  equations  . . . . . . . . . . . . . . . 36--57
           Lane A. Hemaspaandra   \booktitleSIGACT News Complexity Theory
                                  Column 112 . . . . . . . . . . . . . . . 58--58
           S. F. de Rezende and   
          M. Göös and   
                      R. Robere   Guest Column: Proofs, Circuits, and
                                  Communication  . . . . . . . . . . . . . 59--82


Communications of the ACM
Volume 27, Number 6, June, 1984

                Donald E. Knuth   Corrigendum: ``The complexity of songs'' 593--593

Communications of the ACM
Volume 27, Number 4, April, 1984

                Donald E. Knuth   The complexity of songs  . . . . . . . . 344--346


SIAM Journal on Computing
Volume 20, Number 1, February, 1991

         Edward M. Reingold and   
                  Xiao Jun Shen   More Nearly Optimal Algorithms for
                                  Unbounded Searching, Part I: The Finite
                                  Case . . . . . . . . . . . . . . . . . . 156--183
         Edward M. Reingold and   
                  Xiao Jun Shen   More nearly optimal algorithms for
                                  unbounded searching. II. The transfinite
                                  case . . . . . . . . . . . . . . . . . . 184--208


SIAM Journal on Computing
Volume 3, Number 2, 1974

                 John E. Savage   An Algorithm for the Computation of
                                  Linear Forms . . . . . . . . . . . . . . 150--158


Computer Physics Communications
Volume 163, Number 1, October 15, 2004

                  Lorenza Viola   Book Review: \booktitleQuantum
                                  Computing: Mika Hirvensalo, (2001)
                                  Springer-Verlag, Berlin ISBN
                                  3-540-66783-0  . . . . . . . . . . . . . 65--66