Journal of the ACM, Volume 66

Volume 66, Number 1, January 2019

Computer-aided Verification

• 
  Steve Bishop, Matthew Fairbairn, Hannes Mehnert, Michael Norrish, Tom Ridge, Peter Sewell, Michael Smith, Keith Wansbrough:
  Engineering with Logic: Rigorous Test-Oracle Specification and Validation for TCP/IP and the Sockets API. 1:1-1:77

Concurrent Programming

• 
  Victor Bushkov, Dmytro Dziuma, Panagiota Fatourou, Rachid Guerraoui:
  The PCL Theorem: Transactions cannot be Parallel, Consistent, and Live. 2:1-2:66

Complexity theory

• 
  Ran Raz:
  Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. 3:1-3:18

Graph Algorithms

• 
  Ken-ichi Kawarabayashi, Mikkel Thorup:
  Deterministic Edge Connectivity in Near-Linear Time. 4:1-4:50

Computational Geometry

• 
  Peter Bürgisser, Felipe Cucker, Pierre Lairez:
  Computing the Homology of Basic Semialgebraic Sets in Weak Exponential Time. 5:1-5:30

Randomized Algorithms and Probabilistic Analysis

• 
  Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Maxwell Young:
  Scaling Exponential Backoff: Constant Throughput, Polylogarithmic Channel-Access Attempts, and Robustness. 6:1-6:33

Approximation Algorithm

• 
  Nikhil R. Devanur, Kamal Jain, Balasubramanian Sivan, Christopher A. Wilkens:
  Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems. 7:1-7:41

Volume 66, Number 2, April 2019

Exact Algorithms via Monotone Local Search

• 
  Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, Saket Saurabh:
  Exact Algorithms via Monotone Local Search. 8:1-8:23

Randomized Algorithms and Probabilistic Analysis of Algorithms

• 
  Mahdi Cheraghchi:
  Capacity Upper Bounds for Deletion-type Channels. 9:1-9:79

Algorithms

• 
  Ankur Moitra:
  Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models. 10:1-10:25

Pseudorandomness

• 
  Russell Impagliazzo, Raghu Meka, David Zuckerman:
  Pseudorandomness from Shrinkage. 11:1-11:16

Logic and Computation

• 
  Thomas Place, Marc Zeitoun:
  Going Higher in First-Order Quantifier Alternation Hierarchies on Words. 12:1-12:65
• 
  Vincent Rahli, Mark Bickford, Liron Cohen, Robert L. Constable:
  Bar Induction is Compatible with Constructive Type Theory. 13:1-13:35

Approximation Algorithm

• 
  Vera Traub, Jens Vygen:
  Approaching 3/2 for the s-t-path TSP. 14:1-14:17

Volume 66, Number 3, June 2019

Theory of Computation

• 
  Joël Ouaknine, Amaury Pouly, João Sousa Pinto, James Worrell:
  On the Decidability of Membership in Matrix-exponential Semigroups. 15:1-15:24

Algorithms and Data Structures

• 
  Daniel M. Kane, Shachar Lovett, Shay Moran:
  Near-optimal Linear Decision Trees for k-SUM and Related Problems. 16:1-16:18

Distributed Computing

• 
  Pierre Fraigniaud, Amos Korman, Yoav Rodeh:
  Parallel Bayesian Search with No Coordination. 17:1-17:28

Randomized Algorithm

• 
  Heng Guo, Mark Jerrum, Jingcheng Liu:
  Uniform Sampling Through the Lovász Local Lemma. 18:1-18:31

Computer-aided Verification

• 
  Thomas Ferrère, Oded Maler, Dejan Nickovic, Amir Pnueli:
  From Real-time Logic to Timed Automata. 19:1-19:31

Invited Articles Foreword

• 
  Éva Tardos:
  Invited Articles Foreword. 20:1

Computational Geometry

• 
  Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, Uli Wagner:
  Shellability is NP-complete. 21:1-21:18

Computer-aided Verification

• 
  Paul Beame, Vincent Liew:
  Toward Verifying Nonlinear Integer Arithmetic. 22:1-22:30

Computational Logic

• 
  Nathanael L. Ackerman, Cameron E. Freer, Daniel M. Roy:
  On the Computability of Conditional Probability. 23:1-23:40

Volume 66, Number 4, August 2019

Networking

• 
  Fabian R. Wirth, Sonja Stüdli, Jia Yuan Yu, Martin Corless, Robert Shorten:
  Nonhomogeneous Place-dependent Markov Chains, Unsynchronised AIMD, and Optimisation. 24:1-24:37

Computational Complexity

• 
  Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, Karteek Sreenivasaiah:
  On the Complexity of Hazard-free Circuits. 25:1-25:20

Design and Analysis of Algorithms

• 
  Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, Claire Mathieu:
  Hierarchical Clustering: Objective Functions and Algorithms. 26:1-26:42

Real Computation

• 
  Gregorio Malajovich, Mike Shub:
  A Theory of NP-completeness and Ill-conditioning for Approximate Real Computations. 27:1-27:38

Algorithms

• 
  András Sebö, Anke van Zuylen:
  The Salesman's Improved Paths through Forests. 28:1-28:16
• 
  Anna Adamaszek, Sariel Har-Peled, Andreas Wiese:
  Approximation Schemes for Independent Set and Sparse Subsets of Polygons. 29:1-29:40

Online Algorithms

• 
  Robert Kleinberg, Aleksandrs Slivkins, Eli Upfal:
  Bandits and Experts in Metric Spaces. 30:1-30:77

Computer-aided Verification

• 
  Guy Avni, Thomas A. Henzinger, Ventsislav Chonev:
  Infinite-duration Bidding Games. 31:1-31:29

Volume 66, Number 5, September 2019

Distributed Computing

• 
  Christoph Lenzen, Joel Rybicki:
  Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as Consensus. 32:1-32:56

Algorithms and Data Structures

• 
  Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi:
  On the Parameterized Complexity of Approximating Dominating Set. 33:1-33:38

Algorithms

• 
  Ilan Komargodski, Moni Naor, Eylon Yogev:
  White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing. 34:1-34:28

Scientific Computing

• 
  Satoru Iwata, Taihei Oki, Mizuyo Takamatsu:
  Index Reduction for Differential-algebraic Equations with Mixed Matrices. 35:1-35:34

Derandomizing Algorithms

• 
  David G. Harris, Aravind Srinivasan:
  The Moser-Tardos Framework with Partial Resampling. 36:1-36:45

Online Algorithms

• 
  Aaron Bernstein, Jacob Holm, Eva Rotenberg:
  Online Bipartite Matching with Amortized O(log ² n) Replacements. 37:1-37:23

Algorithmic Information Theory

• 
  Andrei E. Romashchenko, Marius Zimand:
  An Operational Characterization of Mutual Information in Algorithmic Information Theory. 38:1-38:42

Volume 66, Number 6, December 2019

Computational Logic

• 
  Artur Jez:
  Deciding Context Unification. 39:1-39:45

Graph Exploration

• 
  Yann Disser, Jan Hackfeld, Max Klimm:
  Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents. 40:1-40:41

Complexity Theory, Verification

• 
  David Monniaux, Valentin Touzeau:
  On the Complexity of Cache Analysis for Different Replacement Policies. 41:1-41:22

Machine Learning Theory

• 
  Shahar Mendelson:
  An Unrestricted Learning Procedure. 42:1-42:42

Invited Articles Foreword

• 
  Éva Tardos:
  Invited Articles Foreword. 43:1

Logic and Computation

• 
  Sandra Kiefer, Ilia Ponomarenko, Pascal Schweitzer:
  The Weisfeiler-Leman Dimension of Planar Graphs Is at Most 3. 44:1-44:31

Computational Geometry

• 
  Vincent Despré, Francis Lazarus:
  Computing the Geometric Intersection Number of Curves. 45:1-45:49