Journal of the ACM, Volume 71

Volume 71, Number 1, February 2024

Invited Article: Distributed Computing

• 
  Sean Ovens:
  The Space Complexity of Consensus from Swap. 1:1-1:26

Invited Article: Programming Languages

• 
  Dario Stein, Sam Staton:
  Probabilistic Programming with Exact Conditions. 2:1-2:53

Formal Verification

• 
  Aïna Linn Georges, Armaël Guéneau, Thomas Van Strydonck, Amin Timany, Alix Trieu, Dominique Devriese, Lars Birkedal:
  Cerise: Program Verification on a Capability Machine in the Presence of Untrusted Code. 3:1-3:59

Algorithmic Game Theory

• 
  Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn:
  EFX Exists for Three Agents. 4:1-4:27

Economics and Computation

• 
  Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David C. Parkes, Sai Srivatsa Ravindranath:
  Optimal Auctions through Deep Learning: Advances in Differentiable Economics. 5:1-5:53

Database Theory

• 
  Xiao Hu, Yufei Tao:
  Parallel Acyclic Joins: Optimal Algorithms and Cyclicity Separation. 6:1-6:44

Volume 71, Number 2, April 2024

INVITED ARTICLE: Logic and Computation

• 
  Moritz Lichter, Pascal Schweitzer:
  Choiceless Polynomial Time with Witnessed Symmetric Choice. 7:1-7:70

INVITED ARTICLE: Database Theory

• 
  Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu, Yisu Remy Wang:
  Convergence of datalog over (Pre-) Semirings. 8:1-8:55

Algorithmic Game Theory

• 
  Yuqing Kong:
  Dominantly Truthful Peer Prediction Mechanisms with a Finite Number of Tasks. 9:1-9:49

Algorithms and Combinatorial Optimization

• 
  Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup:
  Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. 10:1-10:41

Algebraic Complexity Theory

• 
  Vincent Neiger, Bruno Salvy, Éric Schost, Gilles Villard:
  Faster Modular Composition. 11:1-11:79

Distributed Computing

• 
  Shang-En Huang, Seth Pettie, Leqi Zhu:
  Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection. 12:1-12:37

Artificial Intelligence

• 
  Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, Ellen Vitercik:
  Learning to Branch: Generalization Guarantees and Limits of Data-Independent Discretization. 13:1-13:73

Programming Languages and Logic

• 
  Arthur Oliveira Vale, Zhong Shao, Yixuan Chen:
  A Compositional Theory of Linearizability. 14:1-14:107

Sketching and Streaming Algorithms

• 
  Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy:
  Sketching Approximability of All Finite CSPs. 15:1-15:74

Logic and Computation

• 
  Javier Esparza, Rubén Rubio, Salomon Sickert:
  Efficient Normalization of Linear Temporal Logic. 16:1-16:42

Volume 71, Number 3, June 2024

INVITED ARTICLE: Distributed Computing

• 
  Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, Calvin Newport:
  Smoothed Analysis of Information Spreading in Dynamic Networks. 17

Complexity Theory

• 
  Noga Ron-Zewi, Ron Rothblum:
  Local Proofs Approaching the Witness Length. 18

Sequential Decision Making

• 
  Nika Haghtalab, Tim Roughgarden, Abhishek Shetty:
  Smoothed Analysis with Adaptive Adversaries. 19

Quantum Complexity and Quantum Cryptography

• 
  Takashi Yamakawa, Mark Zhandry:
  Verifiable Quantum Advantage without Structure. 20

Structural Graph Theory

• 
  Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, Szymon Torunczyk:
  Twin-Width IV: Ordered Graphs and Matrices. 21

Algebraic Complexity

• 
  Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans:
  Fast Multivariate Multipoint Evaluation over All Finite Fields. 22

Cryptography, Cryptoanalysis

• 
  Itai Dinur, Nathan Keller, Ohad Klein:
  Fine-grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR. 23

Algorithms

• 
  Jason M. Altschuler, Sinho Chewi:
  Faster High-accuracy Log-concave Sampling via Algorithmic Warm Starts. 24

Volume 71, Number 4, August 2024

Cryptography, blockchains, bitcoin

• 
  Juan A. Garay, Aggelos Kiayias, Nikos Leonardos:
  The Bitcoin Backbone Protocol: Analysis and Applications. 25:1-25:49

Logic and Complexity

• 
  Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao:
  Separations in Proof Complexity and TFNP. 26:1-26:45

Algorithmic Graph Theory

• 
  Dimitrios M. Thilikos, Sebastian Wiederrecht:
  Killing a Vortex. 27:1-27:56

Computational Topology

• 
  Mickaël Buchet, Bianca B. Dornelas, Michael Kerber:
  Sparse Higher Order Čech Filtrations. 28:1-28:23

Algorithms

• 
  Sinho Chewi, Jaume de Dios Pont, Jerry Li, Chen Lu, Shyam Narayanan:
  Query Lower Bounds for Log-concave Sampling. 29:1-29:42

Mechanism design, Blockchains

• 
  Tim Roughgarden:
  Transaction Fee Mechanism Design. 30:1-30:25

Volume 71, Number 5, October 2024

Algorithmic Game Theory

• 
  Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos:
  Pure-Circuit: Tight Inapproximability for PPAD. 31:1-31:48

Data-Driven Algorithms

• 
  Maria-Florina Balcan, Dan F. DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, Ellen Vitercik:
  How Much Data Is Sufficient to Learn High-Performing Algorithms? 32:1-32:58

Dynamic Graph Algorithms

• 
  Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc:
  Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time. 33:1-33:32

Computational linear algebra

• 
  Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva:
  Fast Algorithms for ℓ_p-Regression. 34:1-34:45

Compressed Sensing

• 
  Namiko Matsumoto, Arya Mazumdar:
  Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing. 35:1-35:64

Logic and Algorithms

• 
  Antoine Mottet, Michael Pinsker:
  Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structures. 36:1-36:47

Volume 71, Number 6, December 2024

Proof Complexity

• 
  Mladen Miksa, Jakob Nordström:
  A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds. 37:1-37:43

Graph Algorithms

• 
  Yifan Jing, Bojan Mohar:
  Efficient polynomial-time approximation scheme for the genus of dense graphs. 38:1-38:33

Distributed Computing

• 
  Thomas Nowak, Ulrich Schmid, Kyrill Winkler:
  Topological Characterization of Consensus in Distributed Systems. 39:1-39:48

Programming Languages

• 
  Amin Timany, Robbert Krebbers, Derek Dreyer, Lars Birkedal:
  A Logical Approach to Type Soundness. 40:1-40:75

Learning Theory

• 
  Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant:
  Efficient Convex Optimization Requires Superlinear Memory. 41:1-41:37

Computational Social Choice Theory

• 
  Moses Charikar, Prasanna Ramakrishnan, Kangning Wang, Hongxun Wu:
  Breaking the Metric Voting Distortion Barrier. 42:1-42:33