Last update: Wed Aug 28 10:03:03 MDT 2024
Volume 1, Number 1, 1969D. E. Muller Universal Boolean functions . . . . . . 8--11
Dennis F. Cudia The degree diagram of undecidable problems of formal grammars . . . . . . 7--8
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
Clarence A. Ellis Non-context-free probabilistic languages 9--14 Edward L. Robertson A corrected definition of ``local speed-up'' . . . . . . . . . . . . . . . 15--16
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
Ivan M. Havel Weak complexity measures . . . . . . . . 21--30
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
Giuseppe Longo Axioms for time dependence of resource consumption in computing recursive functions . . . . . . . . . . . . . . . 14--24
L. Reeker A note on a Badly Nondeterministic automaton . . . . . . . . . . . . . . . 22--24
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
A. L. Rosenburg On the Time Required to Recognize Properties of Graphs: a Problem . . . . 15--16
David B. Benson Another comment on the null word definition problem . . . . . . . . . . . 14--17 SIGACT News Staff Recent technical reports . . . . . . . . 21--24
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
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
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
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
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
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
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
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
Peter Kugel Trees . . . . . . . . . . . . . . . . . 19--19 SIGACT News Staff Technical reports . . . . . . . . . . . 20--24
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
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
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
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
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
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
Donald E. Knuth The Samson--Mueller Algorithm . . . . . ??
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
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
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
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
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
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
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
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
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
SIGACT News Staff Technical reports . . . . . . . . . . . 2--135
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
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
SIGACT News Staff Technical reports . . . . . . . . . . . 16--65
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
SIGACT News Staff Technical reports . . . . . . . . . . . 20--41
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
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
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
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
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
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
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
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
Charles B. Dunham A sequence of uncomputable functions . . 48--48 Andrei Broder and Jorge Stolfi Pessimal algorithms and simplexity analysis . . . . . . . . . . . . . . . . 49--53
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
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
Harold M. Hastings Maps of the interval, polynomial time, and polynomial space . . . . . . . . . . 44--51 Harold M. Hastings Convergence of simulated annealing . . . 52--63
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
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
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
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
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
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
B. Simmons and J. Yudken Federal funding in computer science: a preliminary report . . . . . . . . . . . 54--63
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
Maria Klawe SIGACT salary survey . . . . . . . . . . 11--17 Joseph O'Rourke Computational geometry column . . . . . 21--26 Joachim Ciesinger Neural nets . . . . . . . . . . . . . . 46--47
Ronald L. Graham and Donald E. Knuth and Oren Patashnik Textbook Announcement: \booktitleConcrete Mathematics: a Foundation for Computer Science . . . . ??
P. Kanellakis and S. Abiteboul Deciding bounded recursion in database logic programs . . . . . . . . . . . . .
T. Zeugmann Book Review: Baase, \booktitleComputer Algorithms: Introduction to Design and Analysis (2nd ed.) (1988) . . . . . . .
L. Ramshaw Suitening our nomenclature . . . . . . . 60--61 M. Tompa Figures of merit . . . . . . . . . . . . 62--71
Joseph O'Rourke Computational geometry column . . . . . 10--11
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
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
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
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
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 . . . . . . . . . . . . . . . ??
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
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
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
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
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
Rajeev Alur and Thomas A. Henzinger Sigact News Logic Column 1: Time for Logic . . . . . . . . . . . . . . . . . ??
T. Zeugmann Book Review: Reingold and Shen, \booktitleMore Nearly Optimal Algorithms for Unbounded Searching (1991) . . . . . ??
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
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
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
J. Shallit Randomized Algorithms in ``Primitive Cultures'' . . . . . . . . . . . . . . . 77--80
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Pankaj K. Agarwal and Joseph O'Rourke Computational geometry . . . . . . . . . 27--32
Eric Allender Book Review: \booktitleComplexity Theory Retrospective II. Edited by: Lane A. Hemaspaandra and Alan L. Selman (Springer Verlag) . . . . . . . . . . . 2--5
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
Randeep Bhatia and Yoram J. Sussmann Book review: \booktitleApproximation Algorithms for NP-hard Problems. Edited by Dorit S. Hochbaum (PWS, 1997) . . . . 17--20
Avrim Blum and Prabhakar Raghavan On a theory of computing symposia . . . 104--111
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
William Gasarch The Book Review Column . . . . . . . . . 2
William Gasarch The Book Review Column . . . . . . . . . 17
William Gasarch The Book Review Column . . . . . . . . . 43
William Gasarch The Book Review Column . . . . . . . . . 2--4
William Gasarch The Book Review Column . . . . . . . . . 2
Sanjay Gupta Book Review: \booktitleTheories of Computability, by Nicholas Pippenger (Cambridge University Press 1997) . . . 5--10
Lane A. Hemaspaandra Take-home complexity . . . . . . . . . . 9--13
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
Lane A. Hemaspaandra and Alan L. Selman Writing and editing complexity theory: tales and tools . . . . . . . . . . . . 20--27
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
Samir Khuller Book Review: \booktitleSelected Papers on Computer Science, by Donald E. Knuth 21--26
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
Alexander E. Kostin and Svetlana A. Tchoudaikina Yet another reachability algorithm for Petri nets . . . . . . . . . . . . . . . 98--110
Harry R. Lewis and Christos H. Papadimitriou Elements of the Theory of Computation 62--78 Luc Longpré Report on Complexity 1998 . . . . . . . 92--93
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
Peter W. O'Hearn Polymorphism, objects and abstract types 39--50
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
Jan Paredaens Database theory column: report on PODs '98 . . . . . . . . . . . . . . . . . . 23--26
Brian Postow Book Review: \booktitleBasic Simple Type Theory, by J. Roger Hindley (Cambridge University Press 1997) . . . . . . . . . 5--8
Brian Postow Book Review: \booktitleA Theory of Objects, by Martin Abadi and Luca Cardelli (Springer-Verlag, 1996): Series--Monographs in Computer Science 9--11
Kirk Pruhs How to design dynamic programming algorithms sans recursion . . . . . . . 32--35 Rocky Ross Education Forum: Reflections on Turning Fifty . . . . . . . . . . . . . . . . . 21--31
Rocky Ross Education forum: Web Enhanced Textbooks 51--57
Rocky Ross Graduate degrees on the Web . . . . . . 56--57
Rocky Ross Mathematics on the Web . . . . . . . . . 33--41
John E. Savage A new approach to the first theory course . . . . . . . . . . . . . . . . . 58--62
Joel Seiferas Reprints from \booktitleComputing Reviews . . . . . . . . . . . . . . . . 13--14
Joel Seiferas Reprints from \booktitleComputing Reviews . . . . . . . . . . . . . . . . 27--28
Joel Seiferas Reprints from \booktitleComputing Reviews . . . . . . . . . . . . . . . . 53--54
Joel Seiferas Reprints from \booktitleComputing Reviews . . . . . . . . . . . . . . . . 15--16
Joel Seiferas Reprints from \booktitleComputing Reviews . . . . . . . . . . . . . . . . 12--13
Rakesh K. Sinha Technical report column . . . . . . . . 30--32
Dan Suciu An overview of semistructured data . . . 28--38
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
Dennis Volpano and Geoffrey Smith Confinement properties for programming languages . . . . . . . . . . . . . . . 33--42
Mark Allen Weiss Data structures and problem solving using Java . . . . . . . . . . . . . . . 42--49
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Frederic Green The Book Review Column . . . . . . . . . 3--5 Frederic Green Review of \booktitleComplexity Dichotomies for Counting Problems Volume 1: Boolean Domain by Jin-Yi Cai and Xi Chen . . . . . . . . . . . . . . . . . . 6--10 Erick Galinkin Review of \booktitleThe Geometry of Uncertainty by Fabio Cuzzolin . . . . . 11--14 Dean Kelley Technical Report Column . . . . . . . . 15--25 William Gasarch Open Problems Column . . . . . . . . . . 26 William Gasarch and Nathan Hayes and Anthony Ostuni and Davin Park The Complexity of Chromatic Number When Restricted to graphs with Bounded Genus or Bounded Crossing Number . . . . . . . 27--38 Lane A. Hemaspaandra SIGACT News Complexity Theory Column 113 39 N. Limaye and S. Srinivasan and S. Tavenas Guest Column: Lower Bounds Against Constant-Depth Algebraic Circuits . . . 40--62 Dan Alistarh Distributed Computing Column 85: Elastic Consistency: a Consistency Criterion for Distributed Optimization . . . . . . . . 63 Dan Alistarh and Ilia Markov and Giorgi Nadiradze Elastic Consistency: a Consistency Criterion for Distributed Optimization 64--82 Rob van Stee SIGACT News Online Algorithms Column 39 83 Debasis Dwibedy and Rakesh Mohanty Online List Scheduling for Makespan Minimization: a Review of the State-of-the-art Results, Research Challenges and Open Problems . . . . . . 84--105
Frederic Green The Book Review Column . . . . . . . . . 3--5 William Gasarch Review of ``\booktitleThe Engines of Cognition: Essays by the Less Wrong Community by Less Wrong Less Wrong Press, 720 pages, Year: 2019 \$30.00''} 6--16 Frederic Green Review of ``\booktitleMathematical Muffin Morsels --- Nobody wants a small piece by William Gasarch, Erik Metz, Jacob Prinz, and Daniel Smolyak World Scientific, 2021, 210 pages, Softcover, \$59.99''} . . . . . . . . . . . . . . . 17--20 Nicholas Tran Review of ``\booktitleThe Algorithm Design Manual, 3rd ed. by Steven S. Skiena, Springer, 2020 793 pages, Hardcover, \$99.99''} . . . . . . . . . 21--23 Dean Kelley Technical report column . . . . . . . . 24--35 William Gasarch Open problems column . . . . . . . . . . 36--40 Lane A. Hemaspaandra SIGACT news complexity theory column 114 41--45 Eleni Bakali and Aggeliki Chalki and Andreas Göbel and Aris Pagourtzis and Stathis Zachos Guest column: a panorama of counting problems the decision version of which is in $ P^3 $ . . . . . . . . . . . . . 46--68
Frederic Green The Book Review Column . . . . . . . . . 6 Frederic Green Review of \booktitleFeasible Computations and Provable Complexity Properties by Juris Hartmanis . . . . . 7--10 William Gasarch Open Problems Column . . . . . . . . . . 11--31 Dexter Kozen Reminiscences of Juris . . . . . . . . . 32--34 Lane A. Hemaspaandra SIGACT News Complexity Theory Column 115: Juris Hartmanis and Two Golden Rules . . . . . . . . . . . . . . . . . 35--40 Janos Simon Remembering Juris . . . . . . . . . . . 41--47
Nicholas Tran The Book Review Column . . . . . . . . . 6--8 William Gasarch Joint Review of \booktitleThe Mathematics of Various Entertaining Subjects: Research in Recreational Math and \booktitleThe Mathematics of Various Entertaining Subjects: Vol. 2. Research in Games, Graphs, Counting, and Complexity and \booktitleThe Mathematics of Various Entertaining Subjects Vol. 3. The Magic of Mathematics . . . . . . . . 9--14 Peter Ross Review of \booktitle1 The Discrete Mathematical Charms of Paul Erd\Hos: A Simple Introduction by Vasek Chvatal . . 15--17 S. V. Nagaraj Review of \booktitleProgramming for the Puzzled: Learn to Program While Solving Puzzles, Srini Devadas . . . . . . . . . 18--21 Dean Kelley Technical Report Column . . . . . . . . 22--36 Huck Bennett The Complexity of the Shortest Vector Problem . . . . . . . . . . . . . . . . 37--61 Lane A. Hemaspaandra SIGACT News Complexity Theory Column 116 62 Eric Allender Guest Column: Parting Thoughts and Parting Shots (Read On for Details on How to Win Valuable Prizes!) . . . . . . 63--81 Lane A. Hemaspaandra SIGACT News Complexity Theory Column 117: Thirty Years of Complexity Theory (Columns) . . . . . . . . . . . . . . . 82--89 Aflatoun Amouzandeh and Soren Schmitt and Rob van Stee SIGACT News Online Algorithms Column 40: 2022 in review . . . . . . . . . . . . . 90--104 Dan Alistarh Distributed Computing Column 86: a Summary of PODC 2022 . . . . . . . . . . 105 Dan Alistarh and Alkida Balliu and Dimitrios Los and Sean Ovens A Brief Summary of PODC 2022 . . . . . . 106--112
Nicholas Tran The Book Review Column . . . . . . . . . 3--14 Dean Kelley Technical Report Column . . . . . . . . 15--25 William Gasarch Open Problems Column . . . . . . . . . . 26--42 Ben Lee Volk SIGACT News Complexity Theory Column 118 43 Lijie Chen and Roei Tell Guest Column: New ways of studying the BPP = P conjecture . . . . . . . . . . . 44--69
Nicholas Tran The Book Review Column . . . . . . . . . 3--21 Dean Kelley Technical Report Column . . . . . . . . 22--32 William Gasarch Open Problems Column . . . . . . . . . . 33--41 Hung Q. Ngo Database Theory Column . . . . . . . . . 42--45 Dan Alistarh Distributed Computing Column 87: Recent Advances in Multi-Pass Graph Streaming Lower Bounds . . . . . . . . . . . . . . 46--47 Sepehr Assadi Recent Advances in Multi-Pass Graph Streaming Lower Bounds . . . . . . . . . 48--75
Nicholas Tran The Book Review Column . . . . . . . . . 7--26 Dean Kelley Technical Report Column . . . . . . . . 27--40 William Gasarch Open Problems Column . . . . . . . . . . 41--52 Ben Lee Volk SIGACT News Complexity Theory Column 119 53 Sevag Gharibian Guest Column: The 7 faces of quantum NP 54--91 Dan Alistarh Distributed Computing Column 86: The Environmental Cost of Our Conferences 92--93 Laurent Feuilloley and Tijn de Vos The Environmental Cost of Our Conferences: The CO$_2$ Emissions due to Travel at PODC and DISC . . . . . . . . 94--107 Aflatoun Amouzandeh and Sören Schmitt and Rob van Stee SIGACT News Online Algorithms Column 41: 2023 in review . . . . . . . . . . . . . 108--125
Nicholas Tran The Book Review Column . . . . . . . . . 6--19 Dean Kelley Technical Report Column . . . . . . . . 20--31 William Gasarch Open Problems Column . . . . . . . . . . 32--51 Li Chen Brief Introduction to Quantum Computing for Undergraduate Students: Lecture One 52--65 Ben Lee Volk SIGACT News Complexity Theory Column 120 66 Hamed Hatami and Pooya Hatami Guest Column: Structure in Communication Complexity and Constant-Cost Complexity Classes . . . . . . . . . . . . . . . . 67--93
Donald E. Knuth Corrigendum: ``The complexity of songs'' 593--593
Donald E. Knuth The complexity of songs . . . . . . . . 344--346
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
John E. Savage An Algorithm for the Computation of Linear Forms . . . . . . . . . . . . . . 150--158
Lorenza Viola Book Review: \booktitleQuantum Computing: Mika Hirvensalo, (2001) Springer-Verlag, Berlin ISBN 3-540-66783-0 . . . . . . . . . . . . . 65--66