Journal of the ACM, Volume 72

Volume 72, Number 1, February 2025

INVITED PAPER: Formal Methods

• 
  Arka Ghosh, Piotr Hofman, Slawomir Lasota:
  Orbit-finite Linear Programming. 1:1-1:39

Machine Learning Theory

• 
  Guy Blanc:
  Subsampling Suffices for Adaptive Data Analysis. 2:1-2:45

Discrete Optimization

• 
  Samuel Fiorini, Gwenaël Joret, Stefan Weltge, Yelena Yuditsky:
  Integer programs with bounded subdeterminants and two nonzeros per row. 3:1-3:50

Complexity of Real Analysis

• 
  Donghyun Lim, Martin Ziegler:
  Quantitative Coding and Complexity Theory of Continuous Data: Part I: Motivation, Definition, Consequences. 4:1-4:39

Fixed Parameter Rractability

• 
  Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
  Flow-augmentation I: Directed graphs. 5:1-5:38

Fine-Grained Complexity

• 
  Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams:
  Hardness of Approximate Diameter: Now for Undirected Graphs. 6:1-6:32

Algorithms

• 
  Hongyang Liu, Yitong Yin:
  Parallelize Single-Site Dynamics up to Dobrushin Criterion. 7:1-7:33

Programming Languages and Verification

• 
  Matthieu Sozeau, Yannick Forster, Meven Lennon-Bertrand, Jakob Botsch Nielsen, Nicolas Tabareau, Théo Winterhalter:
  Correct and Complete Type Checking and Certified Erasure for Coq, in Coq. 8:1-8:74

Computational Geometry

• 
  Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow:
  Geometric Embeddability of Complexes is ∃ℝ-complete. 9:1-9:26

Quantum Algorithms

• 
  Oded Regev:
  An Efficient Quantum Factoring Algorithm. 10:1-10:13

Volume 72, Number 2, April 2025

Formal Verification

• 
  Nathanaël Fijalkow, Engel Lefaucheux, Pierre Ohlmann, Joël Ouaknine, Amaury Pouly, James Worrell:
  On the Monniaux Problem in Abstract Interpretation. 11:1-11:51

Convex Optimization

• 
  Jason M. Altschuler, Pablo A. Parrilo:
  Acceleration by Stepsize Hedging: Multi-Step Descent and the Silver Stepsize Schedule. 12:1-12:38

Computational Complexity and Cryptography

• 
  Elette Boyle, Ilan Komargodski, Neekon Vafa:
  Memory Checking Requires Logarithmic Overhead. 13:1-13:43

Algorithms; Machine Learning

• 
  Oren Mangoubi, Nisheeth K. Vishnoi:
  Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations. 14:1-14:88

Computational Complexity and Cryptography

• 
  Noga Ron-Zewi, Ron Rothblum:
  Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead. 15:1-15:54

Approximation Algorithms

• 
  Vera Traub, Rico Zenklusen:
  Better-Than-2 Approximations for Weighted Tree Augmentation and Applications to Steiner Tree. 16:1-16:40
• 
  Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi:
  2-Approximation for Prize-Collecting Steiner Forest. 17:1-17:27

Volume 72, Number 3, June 2025

INVITED ARTICLES: Database Systems and Theory

• 
  Albert Atserias, Phokion G. Kolaitis:
  Consistency of Relations over Monoids. 18:1-18:47

INVITED ARTICLES: Design and Analysis of Algorithms

• 
  Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva:
  Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. 19:1-19:103

INVITED ARTICLES: Quantum program analysis

• 
  Junyi Liu, Li Zhou, Gilles Barthe, Mingsheng Ying:
  Quantum Weakest Preconditions for Reasoning about Expected Runtimes of Quantum Programs. 20:1-20:51

Logic and Algorithms

• 
  Martin Grohe, Moritz Lichter, Daniel Neuen, Pascal Schweitzer:
  Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements. 21:1-21:27

Learning Theory

• 
  Zihan Zhang, Yuxin Chen, Jason D. Lee, Simon S. Du:
  Settling the Sample Complexity of Online Reinforcement Learning. 22:1-22:63

Volume 72, Number 4, August 2025

INVITED ARTICLE: Graph Algorithms

• 
  Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen:
  Negative-Weight Single-Source Shortest Paths in Near-linear Time. 23:1-23:34

Distributed Computing

• 
  Sahil Dhoked, Neeraj Mittal:
  Adaptive and Fair Transformation for Recoverable Mutual Exclusion. 24:1-24:61
• 
  Jun Wan, Hanshen Xiao, Elaine Shi, Srinivas Devadas:
  Expected Constant Round Byzantine Broadcast under Dishonest Majority. 30:1-30:39

Algorithms and Complexity

• 
  Xi Chen, Yuhao Li, Mihalis Yannakakis:
  Computing a Fixed Point of Contraction Maps in Polynomial Queries. 25:1-25:20

Algebraic complexity theory

• 
  Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas:
  Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. 26:1-26:35

Fast Graph Algorithms

• 
  Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Sushant Sachdeva, Richard Peng, Guanghao Ye:
  Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time. 27:1-27:75

Graph Algorithms

• 
  Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai:
  Vertex Connectivity in Poly-logarithmic Max-Flows. 28:1-28:34
• 
  Jason Li, Debmalya Panigrahi:
  Deterministic Minimum Cut in Poly-logarithmic Maximum Flows. 29:1-29:18

Volume 72, Number 5, October 2025

Complexity Theory

• 
  John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani:
  The Complexity of Computing KKT Solutions of Quadratic Programs. 31:1-31:48

Computational Complexity

• 
  Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu:
  Parameterized Inapproximability Hypothesis under ETH. 32:1-32:40

Theory of computation, Models of computation, Formal methods

• 
  Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, Karol Wegrzycki:
  Coverability in VASS Revisited: Improving Rackoff's Bounds to Obtain Conditional Optimality. 33:1-33:27

Economics and Computation

• 
  Alexandros Hollender, Aviad Rubinstein:
  Envy-Free Cake-Cutting for Four Agents. 34:1-34:54

Computational Complexity and Algorithms

• 
  Alexander S. Wein, Ahmed El Alaoui, Cristopher Moore:
  The Kikuchi Hierarchy and Tensor PCA. 35:1-35:40

Learning Theory

• 
  Zihan Zhang, Wenhao Zhan, Yuxin Chen, Simon S. Du, Jason D. Lee:
  Optimal Multi-Distribution Learning. 36:1-36:71
• 
  Yunbei Xu, Assaf Zeevi:
  Bayesian Design Principles for Frequentist Sequential Learning. 37:1-37:65