Journal of the ACM, Volume 68

Volume 68, Number 1, February 2021

Complexity Theory

• 
  Johan Håstad:
  On Small-depth Frege Proofs for Tseitin for Grids. 1:1-1:31

Distributed Algorithms

• 
  Leszek Gasieniec, Grzegorz Stachowiak:
  Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election. 2:1-2:21

Algorithms

• 
  Michael B. Cohen, Yin Tat Lee, Zhao Song:
  Solving Linear Programs in the Current Matrix Multiplication Time. 3:1-3:39

Programming Languages

• 
  Andrzej S. Murawski, Nikos Tzevelekos:
  Game Semantics for Interface Middleweight Java. 4:1-4:51

Programming Languages and Logic

• 
  Nicolas Tabareau, Éric Tanter, Matthieu Sozeau:
  The Marriage of Univalence and Parametricity. 5:1-5:44

Invited Article Foreword

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

Concurrency Theory

• 
  Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jérôme Leroux, Filip Mazowiecki:
  The Reachability Problem for Petri Nets Is Not Elementary. 7:1-7:28

Volume 68, Number 2, March 2021

Algorithms and Cryptography

• 
  Ronald Cramer, Léo Ducas, Benjamin Wesolowski:
  Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time. 8:1-8:26

Computational Geometry

• 
  Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora, Stéphan Thomassé:
  EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs. 9:1-9:38

Economics and Computation

• 
  Shaddin Dughmi, Jason D. Hartline, Robert D. Kleinberg, Rad Niazadeh:
  Bernoulli Factories and Black-box Reductions in Mechanism Design. 10:1-10:30

Machine Learning

• 
  Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, Michael I. Jordan:
  On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points. 11:1-11:29

Invited Articles Foreword

• 
  Éva Tardos:
  Invited Articles Foreword. 12e:1

Logic and Computation

• 
  Iddo Tzameret, Stephen A. Cook:
  Uniform, Integral, and Feasible Proofs for the Determinant Identities. 12:1-12:80

Distributed Algorithms for Radio Networks

• 
  Artur Czumaj, Peter Davies:
  Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks. 13:1-13:22

Volume 68, Number 3, May 2021

Cryptography

• 
  Nico Döttling, Sanjam Garg:
  Identity-based Encryption from the Diffie-Hellman Assumption. 14:1-14:46

Algorithmic Game Theory

• 
  Yannai A. Gonczarowski, S. Matthew Weinberg:
  The Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization. 15:1-15:28

Parameterized Complexity Theory

• 
  Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx:
  Parameterized Intractability of Even Set and Shortest Vector Problem. 16:1-16:40

Networking

• 
  Yun Zeng, Jian Tan, Cathy H. Xia:
  Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit. 17:1-17:30

Logic and Computation

• 
  Maksymilian Mika, Marek Szykula:
  The Frobenius and Factor Universality Problems of the Kleene Star of a Finite Set of Words. 18:1-18:22

Quantum Computing

• 
  Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Saeed Seddighin:
  Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce. 19:1-19:41

Invited Article Foreword

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

Distributed Computing

• 
  Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, Hengjie Zhang:
  Near-optimal Distributed Triangle Enumeration via Expander Decompositions. 21:1-21:36

Volume 68, Number 4, August 2021

Queuing systems

• 
  Peter G. Harrison, Julianna Bor:
  Response Time Distribution in a Tandem Pair of Queues with Batch Processing. 22:1-22:41

Logic and Computation

• 
  Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov:
  Clique Is Hard on Average for Regular Resolution. 23:1-23:26

Algorithms and Data Structures

• 
  Thodoris Lykouris, Sergei Vassilvitskii:
  Competitive Caching with Machine Learned Advice. 24:1-24:25

Machine Learning

• 
  Sébastien Bubeck, Ronen Eldan, Yin Tat Lee:
  Kernel-based Methods for Bandit Convex Optimization. 25:1-25:35

Complexity Theory

• 
  Albert Atserias, Anuj Dawar, Joanna Ochremiak:
  On the Power of Symmetric Linear Programs. 26:1-26:35
• 
  Moses Ganardi, Artur Jez, Markus Lohrey:
  Balancing Straight-line Programs. 27:1-27:40

Computational Complexity

• 
  Libor Barto, Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal:
  Algebraic Approach to Promise Constraint Satisfaction. 28:1-28:66

Invited Article Foreword

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

Computational Geometry

• 
  Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, Arnaud de Mesmay:
  Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. 30:1-30:26

Volume 68, Number 5, October 2021

Computational Complexity and Cryptography

• 
  Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick:
  A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. 31:1-31:47

Algorithms

• 
  C. J. Argue, Anupam Gupta, Ziye Tang, Guru Guruganesh:
  Chasing Convex Bodies with Linear Competitive Ratio. 32:1-32:10

Quantum Cyptography

• 
  Mark Zhandry:
  How to Construct Quantum Random Functions. 33:1-33:43

Concurrence Theory

• 
  Michael Blondin, Matthias Englert, Alain Finkel, Stefan Göller, Christoph Haase, Ranko Lazic, Pierre McKenzie, Patrick Totzke:
  The Reachability Problem for Two-Dimensional Vector Addition Systems with States. 34:1-34:43

Model Semantics

• 
  Georg Gottlob, André Hernich, Clemens Kupke, Thomas Lukasiewicz:
  Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and Complexity. 35:1-35:87

Coding Theory

• 
  Bernhard Haeupler, Amirbehshad Shahrasbi:
  Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound. 36:1-36:39

Invited Articles Foreword

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

Database Theory

• 
  Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon:
  Complexity Analysis of Generalized and Fractional Hypertree Decompositions. 38:1-38:50

Distributed Computing

• 
  Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela:
  Lower Bounds for Maximal Matchings and Maximal Independent Sets. 39:1-39:30

Volume 68, Number 6, December 2021

Algorithms

• 
  Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang:
  Fast Sampling and Counting k-SAT Solutions in the Local Lemma Regime. 40:1-40:42

Programming Languages

• 
  Jonathan Sterling, Robert Harper:
  Logical Relations as Types: Proof-Relevant Parametricity for Program Modules. 41:1-41:47

Algorithms and Data Structures

• 
  Vida Dujmovic, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, Pat Morin:
  Adjacency Labelling for Planar Graphs (and Beyond). 42:1-42:33

Machine Learning

• 
  Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik, Michael I. Jordan:
  Distribution-free, Risk-controlling Prediction Sets. 43:1-43:34

Algorithms and Data Structures

• 
  Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic:
  Near-linear Time Approximation Schemes for Clustering in Doubling Metrics. 44:1-44:34

Complexity Theory

• 
  Shachar Lovett, Kewen Wu, Jiapeng Zhang:
  Decision List Compression by Mild Random Restrictions. 45:1-45:17

Distributed Computing

• 
  Matthias Függer, Thomas Nowak, Manfred Schwarz:
  Tight Bounds for Asymptotic and Approximate Consensus. 46:1-46:35

Invited Article Foreword

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

Database Theory

• 
  Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros:
  #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes. 48:1-48:40