Journal of the ACM, Volume 65

Volume 65, Number 1, January 2018

Programming Languages, Security

• 
  Martín Abadi, Bruno Blanchet, Cédric Fournet:
  The Applied Pi Calculus: Mobile Values, New Names, and Secure Communication. 1:1-1:41

Distributed Computing

• 
  Hagit Attiya, Alexey Gotsman, Sandeep Hans, Noam Rinetzky:
  Characterizing Transactional Memory Consistency Conditions Using Observational Refinement. 2:1-2:44

Online Algorithms

• 
  Sungjin Im, Janardhan Kulkarni, Kamesh Munagala:
  Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints. 3:1-3:33

Complexity Theory

• 
  Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler:
  Constant-Rate Coding for Multiparty Interactive Communication Is Impossible. 4:1-4:41

Invited Article Foreword

• 
  Éva Tardos:
  Invited Article Foreword.

Computational Geometry

• 
  Jirí Matousek, Eric Sedgwick, Martin Tancer, Uli Wagner:
  Embeddability in the 3-Sphere Is Decidable. 5:1-5:49

Volume 65, Number 2, March 2018

Social Choice

• 
  Florian Brandl, Felix Brandt, Manuel Eberl, Christian Geist:
  Proving the Incompatibility of Efficiency and Strategyproofness via SMT Solving. 6:1-6:28

Randomized Algorithms & Probabilistic Analysis

• 
  Michael Molloy:
  The Freezing Threshold for k-Colourings of a Random Graph. 7:1-7:62

Social Choice, Fair Division

• 
  David Kurokawa, Ariel D. Procaccia, Junxing Wang:
  Fair Enough: Guaranteeing Approximate Maximin Shares. 8:1-8:27

Database Systems & Theory

• 
  Manuel Bodirsky, Barnaby Martin, Antoine Mottet:
  Discrete Temporal Constraint Satisfaction Problems. 9:1-9:41
• 
  Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh:
  Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes. 10:1-10:44

Invited Article Foreword

• 
  Éva Tardos:
  Invited Article Foreword. 11e:1

Distributed Computing

• 
  Andrea Cerone, Alexey Gotsman:
  Analysing Snapshot Isolation. 11:1-11:41

Volume 65, Number 3, March 2018

Graph Algorithms

• 
  Marek Cygan, Stefan Kratsch, Jesper Nederlof:
  Fast Hamiltonicity Checking Via Bases of Perfect Matchings. 12:1-12:46

Online Algorithms

• 
  Ashwinkumar Badanidiyuru, Robert Kleinberg, Aleksandrs Slivkins:
  Bandits with Knapsacks. 13:1-13:55

Cryptography

• 
  Itay Berman, Iftach Haitner, Aris Tentes:
  Coin Flipping of Any Constant Bias Implies One-Way Functions. 14:1-14:95

Approximation Algorithms

• 
  T.-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang, Chenzi Zhang:
  Spectral Properties of Hypergraph Laplacian and Approximation Algorithms. 15:1-15:48

Invited Article Foreword

• 
  Éva Tardos:
  Invited Article Foreword.

Database Systems and Theory

• 
  Hung Q. Ngo, Ely Porat, Christopher Ré, Atri Rudra:
  Worst-case Optimal Join Algorithms. 16:1-16:40

Volume 65, Number 4, August 2018

Distributed Computing

• 
  Flavio Chierichetti, George Giakkoupis, Silvio Lattanzi, Alessandro Panconesi:
  Rumor Spreading and Conductance. 17:1-17:21

Cryptography

• 
  Emil Stefanov, Marten van Dijk, Elaine Shi, T.-H. Hubert Chan, Christopher W. Fletcher, Ling Ren, Xiangyao Yu, Srinivas Devadas:
  Path ORAM: An Extremely Simple Oblivious RAM Protocol. 18:1-18:26

Distributed Computing

• 
  David G. Harris, Johannes Schneider, Hsin-Hao Su:
  Distributed (Δ +1)-Coloring in Sublogarithmic Rounds. 19:1-19:21

Cryptography, Coding Theory

• 
  Stefan Dziembowski, Krzysztof Pietrzak, Daniel Wichs:
  Non-Malleable Codes. 20:1-20:32

Automata Theory

• 
  Helmut Seidl, Sebastian Maneth, Gregor Kemper:
  Equivalence of Deterministic Top-Down Tree-to-String Transducers Is Decidable. 21:1-21:30

Complexity Theory

• 
  Allan Grønlund, Seth Pettie:
  Threesomes, Degenerates, and Love Triangles. 22:1-22:25

Programming Languages

• 
  Thomas Ehrhard, Michele Pagani, Christine Tasson:
  Full Abstraction for Probabilistic PCF. 23:1-23:44

Algorithms

• 
  Ethan L. Schreiber, Richard E. Korf, Michael D. Moffitt:
  Optimal Multi-Way Number Partitioning. 24:1-24:61

Invited Paper Foreword

• 
  Éva Tardos:
  Invited Article Foreword. 25:1-25:61

Databases

• 
  Wojciech Czerwinski, Wim Martens, Matthias Niewerth, Pawel Parys:
  Minimization of Tree Patterns. 26:1-26:46

Volume 65, Number 5, September 2018

Complexity

• 
  Virginia Vassilevska Williams, R. Ryan Williams:
  Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 27:1-27:38

Query Languages

• 
  Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev:
  Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity. 28:1-28:51

Artificial Intelligence

• 
  James P. Delgrande, Pavlos Peppas, Stefan Woltran:
  General Belief Revision. 29:1-29:34

Programming Languages, Verification

• 
  Benjamin Lucien Kaminski, Joost-Pieter Katoen, Christoph Matheja, Federico Olmedo:
  Weakest Precondition Reasoning for Expected Runtimes of Randomized Algorithms. 30:1-30:68

Distributed Computing

• 
  Haifeng Yu, Yuda Zhao, Irvan Jahja:
  The Cost of Unknown Diameter in Dynamic Networks. 31:1-31:34

Algebraic Complexity

• 
  Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam:
  On Algebraic Branching Programs of Small Width. 32:1-32:29

Descriptive Complexity

• 
  Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, Thomas Zeume:
  Reachability Is in DynFO. 33:1-33:24

Parametrized Complexity Theory

• 
  Bingkai Lin:
  The Parameterized Complexity of the k-Biclique Problem. 34:1-34:23

Volume 65, Number 6, November 2018

Economic and Computation

• 
  Moshe Babaioff, Nicole Immorlica, David Kempe, Robert Kleinberg:
  Matroid Secretary Problems. 35:1-35:26

Dynamic Graph Algorithms

• 
  Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai:
  Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. 36:1-36:40

Proof Complexitiy

• 
  Joshua A. Grochow, Toniann Pitassi:
  Circuit Complexity, Proof Complexity, and Polynomial Identity Testing: The Ideal Proof System. 37:1-37:59

Distributed Computing

• 
  James Aspnes, Hagit Attiya, Keren Censor-Hillel, Faith Ellen:
  Erratum: Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity. 38:1-38:2

Cryptography

• 
  Nir Bitansky, Vinod Vaikuntanathan:
  Indistinguishability Obfuscation from Functional Encryption. 39:1-39:37

Property Testing

• 
  Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie:
  Settling the Query Complexity of Non-adaptive Junta Testing. 40:1-40:18

Parallel Computing

• 
  Tim Roughgarden, Sergei Vassilvitskii, Joshua R. Wang:
  Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation). 41:1-41:24

Optimization

• 
  Konstantin Makarychev, Maxim Sviridenko:
  Solving Optimization Problems with Diseconomies of Scale via Decoupling. 42:1-42:27

Parallel Algorithms

• 
  Stephan Friedrichs, Christoph Lenzen:
  Parallel Metric Tree Embedding Based on an Algebraic View on Moore-Bellman-Ford. 43:1-43:55

Invited Article Foreword

• 
  Éva Tardos:
  Invited Article Foreword. 44:1

Distributed Algorithms

• 
  Armando Castañeda, Sergio Rajsbaum, Michel Raynal:
  Unifying Concurrent Objects and Distributed Tasks: Interval-Linearizability. 45:1-45:42