OOIR: Observatory of International Research

Papers

(The median citation count of Journal of the ACM is 1. The table below lists those papers that are above that threshold based on CrossRef citation counts [max. 250 papers]. The publications cover those that have been published in the past four years, i.e., from 2021-04-01 to 2025-04-01.)

Article	Citations
Complexity Analysis of Generalized and Fractional Hypertree Decompositions	45
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device	37
Invited Article Foreword	34
Decision List Compression by Mild Random Restrictions	32
Intermediate Value Linearizability: A Quantitative Correctness Criterion	23
Lower Bounds on Implementing Mediators in Asynchronous Systems with Rational and Malicious Agents	20
Parallel Acyclic Joins: Optimal Algorithms and Cyclicity Separation	19
Cerise: Program Verification on a Capability Machine in the Presence of Untrusted Code	18
Minimizing Convex Functions with Rational Minimizers	17
Query Lower Bounds for Log-concave Sampling	17
Separating Rank Logic from Polynomial Time	17
Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning	17
Adjacency Labelling for Planar Graphs (and Beyond)	14
Decentralized Asynchronous Crash-resilient Runtime Verification	14
QCSP Monsters and the Demise of the Chen Conjecture	12
Separations in Proof Complexity and TFNP	12
General Strong Polarization	12
Almost Optimal Exact Distance Oracles for Planar Graphs	12
Faster High-accuracy Log-concave Sampling via Algorithmic Warm Starts	10
Balancing Straight-line Programs	10
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time	10
Toward a Better Understanding of Randomized Greedy Matching	9
String Diagram Rewrite Theory I: Rewriting with Frobenius Structure	9
A Compositional Theory of Linearizability	9
The Complexity and Expressive Power of Limit Datalog	9

Fine-grained Cryptanalysis: Tight Conditional Bounds for Dense k -SUM and k -XOR	9
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor	9
Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime	8
Better-Than-2 Approximations for Weighted Tree Augmentation and Applications to Steiner Tree	8
Algebraic Approach to Promise Constraint Satisfaction	8
2-Approximation for Prize-Collecting Steiner Forest	8
On the Power of Symmetric Linear Programs	7
Acceleration by Stepsize Hedging: Multi-Step Descent and the Silver Stepsize Schedule	7
Invited Articles Foreword	6
On Strongest Algebraic Program Invariants	6
Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors	6
Near-optimal Distributed Triangle Enumeration via Expander Decompositions	5
Parallelize Single-Site Dynamics up to Dobrushin Criterion	5
Two-round Multiparty Secure Computation from Minimal Assumptions	5
Pliability and Approximating Max-CSPs	5
A Framework for Adversarially Robust Streaming Algorithms	5
Topological Characterization of Consensus in Distributed Systems	5
Rate-independent Computation in Continuous Chemical Reaction Networks	5
Anonymous Shared Memory	4
Faster Modular Composition	4
Proximity Gaps for Reed–Solomon Codes	4
Adversarial Bandits with Knapsacks	4
Information Acquisition Under Resource Limitations in a Noisy Environment	4
How to Delegate Computations: The Power of No-Signaling Proofs	4
Co-lexicographically Ordering Automata and Regular Languages - Part I	4
Fast Multivariate Multipoint Evaluation over All Finite Fields	4
On the Need for Large Quantum Depth	4
Tight Bounds for Asymptotic and Approximate Consensus	4
Robustly Learning General Mixtures of Gaussians	4
An Efficient Quantum Factoring Algorithm	3
Fast Algorithms for ℓ _p -Regression	3
Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations	3
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler–Leman Refinement Steps	3
Learning Equilibria in Matching Markets with Bandit Feedback	3
OptORAMa: Optimal Oblivious RAM	3
Independence in Infinite Probabilistic Databases	3
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs	2
Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing	2
#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes	2
An Improved Bound for Weak Epsilon-nets in the Plane	2
Smoothed Analysis of Information Spreading in Dynamic Networks	2
Exponentially Faster Shortest Paths in the Congested Clique	2
Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and Complexity	2
Sketching Approximability of All Finite CSPs	2
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs	2
Universal almost Optimal Compression and Slepian-wolf Coding in Probabilistic Polynomial Time	2
Optimal Bounds for the k -cut Problem	2
Integer programs with bounded subdeterminants and two nonzeros per row	2
Breaking the Metric Voting Distortion Barrier	2
Properly Learning Decision Trees in almost Polynomial Time	2

Counting Subgraphs in Degenerate Graphs	2
Flow-augmentation I: Directed graphs	2
A New Algorithm for Euclidean Shortest Paths in the Plane	2
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems	2
The Topological Mu-Calculus: Completeness and Decidability	2
Clique Is Hard on Average for Regular Resolution	2
On the Zeros of Exponential Polynomials	2
Orbit-finite Linear Programming	2
Geometric Embeddability of Complexes is ∃ℝ-complete	1
A New Minimax Theorem for Randomized Algorithms	1
Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit	1
Efficient Convex Optimization Requires Superlinear Memory	1
The Reachability Problem for Two-Dimensional Vector Addition Systems with States	1
Killing a Vortex	1
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection	1
Probabilistic Programming with Exact Conditions	1
Efficient Normalization of Linear Temporal Logic	1
On the Monniaux Problem in Abstract Interpretation	1
Local Proofs Approaching the Witness Length	1
Hardness of Approximate Diameter: Now for Undirected Graphs	1
Directed Shortest Paths via Approximate Cost Balancing	1
On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds	1
Stochastic Games with Synchronization Objectives	1
The Limitations of Optimization from Samples	1
Smooth Approximation of Lipschitz Maps and Their Subgradients	1
Learning to Branch: Generalization Guarantees and Limits of Data-Independent Discretization	1
On the Descriptive Complexity of Temporal Constraint Satisfaction Problems	1
Locally-iterative Distributed (Δ + 1)-coloring and Applications	1
Convergence of datalog over (Pre-) Semirings	1
Logical Relations as Types: Proof-Relevant Parametricity for Program Modules	1