Volume 68, Number 6, December 2021
#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes.

Marcelo Arenas Luis Alberto Croquevielle Rajesh Jayaram Cristian Riveros

Invited Article Foreword.

Éva Tardos

Tight Bounds for Asymptotic and Approximate Consensus.

Matthias Függer Thomas Nowak Manfred Schwarz

Decision List Compression by Mild Random Restrictions.

Shachar Lovett Kewen Wu Jiapeng Zhang

Near-linear Time Approximation Schemes for Clustering in Doubling Metrics.

Vincent Cohen-Addad Andreas Emil Feldmann David Saulpic

Distribution-free, Risk-controlling Prediction Sets.

Stephen Bates Anastasios Angelopoulos Lihua Lei Jitendra Malik Michael I. Jordan

Adjacency Labelling for Planar Graphs (and Beyond).

Vida Dujmovic Louis Esperet Cyril Gavoille Gwenaël Joret Piotr Micek Pat Morin

Logical Relations as Types: Proof-Relevant Parametricity for Program Modules.

Jonathan Sterling Robert Harper

Fast Sampling and Counting k-SAT Solutions in the Local Lemma Regime.

Weiming Feng Heng Guo Yitong Yin Chihao Zhang

Volume 68, Number 5, October 2021
Lower Bounds for Maximal Matchings and Maximal Independent Sets.

Alkida Balliu Sebastian Brandt Juho Hirvonen Dennis Olivetti Mikaël Rabie Jukka Suomela

Complexity Analysis of Generalized and Fractional Hypertree Decompositions.

Georg Gottlob Matthias Lanzinger Reinhard Pichler Igor Razgon

Invited Articles Foreword.

Éva Tardos

Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound.

Bernhard Haeupler Amirbehshad Shahrasbi

Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and Complexity.

Georg Gottlob André Hernich Clemens Kupke Thomas Lukasiewicz

The Reachability Problem for Two-Dimensional Vector Addition Systems with States.

Michael Blondin Matthias Englert Alain Finkel Stefan Göller Christoph Haase Ranko Lazic Pierre McKenzie Patrick Totzke

How to Construct Quantum Random Functions.

Mark Zhandry

Chasing Convex Bodies with Linear Competitive Ratio.

C. J. Argue Anupam Gupta Ziye Tang Guru Guruganesh

A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device.

Zvika Brakerski Paul F. Christiano Urmila Mahadev Umesh V. Vazirani Thomas Vidick

Volume 68, Number 3, May 2021
Near-optimal Distributed Triangle Enumeration via Expander Decompositions.

Yi-Jun Chang Seth Pettie Thatchaphol Saranurak Hengjie Zhang

Invited Article Foreword.

Éva Tardos

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce.

Mahdi Boroujeni Soheil Ehsani Mohammad Ghodsi MohammadTaghi Hajiaghayi Saeed Seddighin

The Frobenius and Factor Universality Problems of the Kleene Star of a Finite Set of Words.

Maksymilian Mika Marek Szykula

Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit.

Yun Zeng Jian Tan Cathy H. Xia

Parameterized Intractability of Even Set and Shortest Vector Problem.

Arnab Bhattacharyya Édouard Bonnet László Egri Suprovat Ghoshal Karthik C. S. Bingkai Lin Pasin Manurangsi Dániel Marx

The Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization.

Yannai A. Gonczarowski S. Matthew Weinberg

Identity-based Encryption from the Diffie-Hellman Assumption.

Nico Döttling Sanjam Garg

Volume 68, Number 2, March 2021
Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks.

Artur Czumaj Peter Davies

Uniform, Integral, and Feasible Proofs for the Determinant Identities.

Iddo Tzameret Stephen A. Cook

Invited Articles Foreword.

Éva Tardos

On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points.

Chi Jin Praneeth Netrapalli Rong Ge Sham M. Kakade Michael I. Jordan

Bernoulli Factories and Black-box Reductions in Mechanism Design.

Shaddin Dughmi Jason D. Hartline Robert D. Kleinberg Rad Niazadeh

EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs.

Marthe Bonamy Édouard Bonnet Nicolas Bousquet Pierre Charbit Panos Giannopoulos Eun Jung Kim Pawel Rzazewski Florian Sikora Stéphan Thomassé

Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time.

Ronald Cramer Léo Ducas Benjamin Wesolowski

Volume 68, Number 1, February 2021
The Reachability Problem for Petri Nets Is Not Elementary.

Wojciech Czerwinski Slawomir Lasota Ranko Lazic Jérôme Leroux Filip Mazowiecki

Invited Article Foreword.

Éva Tardos

The Marriage of Univalence and Parametricity.

Nicolas Tabareau Éric Tanter Matthieu Sozeau

Game Semantics for Interface Middleweight Java.

Andrzej S. Murawski Nikos Tzevelekos

Solving Linear Programs in the Current Matrix Multiplication Time.

Michael B. Cohen Yin Tat Lee Zhao Song

Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election.

Leszek Gasieniec Grzegorz Stachowiak

On Small-depth Frege Proofs for Tseitin for Grids.

Johan Håstad