JOLACM - volume 68 - 2021 论文列表 |
| 点击这里查看 Journal of the ACM 的JCR分区、影响因子等信息 |
Volume 68, Number 6, December 2021
Marcelo Arenas Luis Alberto Croquevielle Rajesh Jayaram Cristian Riveros
Invited Article Foreword. 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. Fast Sampling and Counting k-SAT Solutions in the Local Lemma Regime.Volume 68, Number 5, October 2021
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. 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. 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 4, August 2021
Vincent Cohen-Addad Éric Colin de Verdière Dániel Marx Arnaud de Mesmay
Invited Article Foreword. Algebraic Approach to Promise Constraint Satisfaction.Libor Barto Jakub Bulín Andrei A. Krokhin Jakub Oprsal
Balancing Straight-line Programs.Moses Ganardi Artur Jez Markus Lohrey
On the Power of Symmetric Linear Programs.Albert Atserias Anuj Dawar Joanna Ochremiak
Kernel-based Methods for Bandit Convex Optimization.Sébastien Bubeck Ronen Eldan Yin Tat Lee
Competitive Caching with Machine Learned Advice.Thodoris Lykouris Sergei Vassilvitskii
Clique Is Hard on Average for Regular Resolution.Albert Atserias Ilario Bonacina Susanna F. de Rezende Massimo Lauria Jakob Nordström Alexander A. Razborov
Response Time Distribution in a Tandem Pair of Queues with Batch Processing.Volume 68, Number 3, May 2021
Yi-Jun Chang Seth Pettie Thatchaphol Saranurak Hengjie Zhang
Invited Article Foreword. 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. Identity-based Encryption from the Diffie-Hellman Assumption.Volume 68, Number 2, March 2021
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.Volume 68, Number 1, February 2021
Wojciech Czerwinski Slawomir Lasota Ranko Lazic Jérôme Leroux Filip Mazowiecki
Invited Article Foreword. 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. On Small-depth Frege Proofs for Tseitin for Grids.