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

电商所评分:7

Invited Article Foreword.

Éva Tardos

电商所评分:6

Tight Bounds for Asymptotic and Approximate Consensus.

Matthias Függer Thomas Nowak Manfred Schwarz

电商所评分:8

Decision List Compression by Mild Random Restrictions.

Shachar Lovett Kewen Wu Jiapeng Zhang

电商所评分:2

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

Vincent Cohen-Addad Andreas Emil Feldmann David Saulpic

电商所评分:9

Distribution-free, Risk-controlling Prediction Sets.

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

电商所评分:5

Adjacency Labelling for Planar Graphs (and Beyond).

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

电商所评分:9

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

Jonathan Sterling Robert Harper

电商所评分:8

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

Weiming Feng Heng Guo Yitong Yin Chihao Zhang

电商所评分:7


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

电商所评分:9

Complexity Analysis of Generalized and Fractional Hypertree Decompositions.

Georg Gottlob Matthias Lanzinger Reinhard Pichler Igor Razgon

电商所评分:7

Invited Articles Foreword.

Éva Tardos

电商所评分:5

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

Bernhard Haeupler Amirbehshad Shahrasbi

电商所评分:3

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

Georg Gottlob André Hernich Clemens Kupke Thomas Lukasiewicz

电商所评分:4

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

电商所评分:9

How to Construct Quantum Random Functions.

Mark Zhandry

电商所评分:4

Chasing Convex Bodies with Linear Competitive Ratio.

C. J. Argue Anupam Gupta Ziye Tang Guru Guruganesh

电商所评分:5

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

电商所评分:10


Volume 68, Number 4, August 2021
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs.

Vincent Cohen-Addad Éric Colin de Verdière Dániel Marx Arnaud de Mesmay

电商所评分:1

Invited Article Foreword.

Éva Tardos

电商所评分:6

Algebraic Approach to Promise Constraint Satisfaction.

Libor Barto Jakub Bulín Andrei A. Krokhin Jakub Oprsal

电商所评分:9

Balancing Straight-line Programs.

Moses Ganardi Artur Jez Markus Lohrey

电商所评分:6

On the Power of Symmetric Linear Programs.

Albert Atserias Anuj Dawar Joanna Ochremiak

电商所评分:4

Kernel-based Methods for Bandit Convex Optimization.

Sébastien Bubeck Ronen Eldan Yin Tat Lee

电商所评分:6

Competitive Caching with Machine Learned Advice.

Thodoris Lykouris Sergei Vassilvitskii

电商所评分:4

Clique Is Hard on Average for Regular Resolution.

Albert Atserias Ilario Bonacina Susanna F. de Rezende Massimo Lauria Jakob Nordström Alexander A. Razborov

电商所评分:10

Response Time Distribution in a Tandem Pair of Queues with Batch Processing.

Peter G. Harrison Julianna Bor

电商所评分:1


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

Yi-Jun Chang Seth Pettie Thatchaphol Saranurak Hengjie Zhang

电商所评分:1

Invited Article Foreword.

Éva Tardos

电商所评分:7

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

Mahdi Boroujeni Soheil Ehsani Mohammad Ghodsi MohammadTaghi Hajiaghayi Saeed Seddighin

电商所评分:8

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

Maksymilian Mika Marek Szykula

电商所评分:1

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

Yun Zeng Jian Tan Cathy H. Xia

电商所评分:8

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

电商所评分:3

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

Yannai A. Gonczarowski S. Matthew Weinberg

电商所评分:1

Identity-based Encryption from the Diffie-Hellman Assumption.

Nico Döttling Sanjam Garg

电商所评分:1


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

Artur Czumaj Peter Davies

电商所评分:4

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

Iddo Tzameret Stephen A. Cook

电商所评分:8

Invited Articles Foreword.

Éva Tardos

电商所评分:1

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

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

电商所评分:5

Bernoulli Factories and Black-box Reductions in Mechanism Design.

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

电商所评分:2

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é

电商所评分:2

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

Ronald Cramer Léo Ducas Benjamin Wesolowski

电商所评分:5


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

电商所评分:5

Invited Article Foreword.

Éva Tardos

电商所评分:6

The Marriage of Univalence and Parametricity.

Nicolas Tabareau Éric Tanter Matthieu Sozeau

电商所评分:5

Game Semantics for Interface Middleweight Java.

Andrzej S. Murawski Nikos Tzevelekos

电商所评分:5

Solving Linear Programs in the Current Matrix Multiplication Time.

Michael B. Cohen Yin Tat Lee Zhao Song

电商所评分:5

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

Leszek Gasieniec Grzegorz Stachowiak

电商所评分:6

On Small-depth Frege Proofs for Tseitin for Grids.

Johan Håstad

电商所评分:10