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-06-01 to 2025-06-01.)

Article	Citations
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time	53
Almost Optimal Exact Distance Oracles for Planar Graphs	48
Minimizing Convex Functions with Rational Minimizers	36
Lower Bounds on Implementing Mediators in Asynchronous Systems with Rational and Malicious Agents	32
On the Power of Symmetric Linear Programs	27
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device	27
A New Algorithm for Euclidean Shortest Paths in the Plane	23
Parallelize Single-Site Dynamics up to Dobrushin Criterion	21
Rate-independent Computation in Continuous Chemical Reaction Networks	21
Proximity Gaps for Reed–Solomon Codes	20
Settling the Sample Complexity of Online Reinforcement Learning	19
A Framework for Adversarially Robust Streaming Algorithms	18
Learning to Branch: Generalization Guarantees and Limits of Data-Independent Discretization	15
The Reachability Problem for Two-Dimensional Vector Addition Systems with States	15
Universal almost Optimal Compression and Slepian-wolf Coding in Probabilistic Polynomial Time	14
Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and Complexity	13
On the Descriptive Complexity of Temporal Constraint Satisfaction Problems	13
Stochastic Games with Synchronization Objectives	12
A New Minimax Theorem for Randomized Algorithms	12
EFX Exists for Three Agents	12
The Limitations of Optimization from Samples	11
A Universal Law of Robustness via Isoperimetry	11
Correct and Complete Type Checking and Certified Erasure for Coq , in Coq	11
How Much Data Is Sufficient to Learn High-Performing Algorithms?	10
A Compositional Theory of Linearizability	9

Relative Error Streaming Quantiles	9
Toward a Better Understanding of Randomized Greedy Matching	9
Twin-width I: Tractable FO Model Checking	9
Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime	9
Choiceless Polynomial Time with Witnessed Symmetric Choice	9
Chasing Convex Bodies with Linear Competitive Ratio	9
Adjacency Labelling for Planar Graphs (and Beyond)	8
Cerise: Program Verification on a Capability Machine in the Presence of Untrusted Code	8
Faster Modular Composition	7
Topological Characterization of Consensus in Distributed Systems	7
On Strongest Algebraic Program Invariants	7
On the Need for Large Quantum Depth	7
Smoothed Analysis of Information Spreading in Dynamic Networks	6
An Efficient Quantum Factoring Algorithm	6
On the Zeros of Exponential Polynomials	5
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection	5
The Art Gallery Problem is ∃ℝ-complete	5
Memory Checking Requires Logarithmic Overhead	5
Gradual System F	5
Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes	5
Invited Article Foreword	5
On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds	5
Efficient Normalization of Linear Temporal Logic	5
Whole-grain Petri Nets and Processes	4
Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring	4
2-Approximation for Prize-Collecting Steiner Forest	4
Transaction Fee Mechanism Design	4
Simple Uncoupled No-regret Learning Dynamics for Extensive-form Correlated Equilibrium	4
General Strong Polarization	4
QCSP Monsters and the Demise of the Chen Conjecture	4
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS	4
Competitive Caching with Machine Learned Advice	4
Separations in Proof Complexity and TFNP	4
Lower Bounds for Maximal Matchings and Maximal Independent Sets	4
Kernel-based Methods for Bandit Convex Optimization	4
Fine-grained Cryptanalysis: Tight Conditional Bounds for Dense k -SUM and k -XOR	3
Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors	3
Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning	3
Decision List Compression by Mild Random Restrictions	3
Algebraic Approach to Promise Constraint Satisfaction	3
Pliability and Approximating Max-CSPs	3
Invited Articles Foreword	2
Killing a Vortex	2
Consistency of Relations over Monoids	2
Logical Relations as Types: Proof-Relevant Parametricity for Program Modules	2
Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead	2
Dominantly Truthful Peer Prediction Mechanisms with a Finite Number of Tasks	2
Hardness of Approximate Diameter: Now for Undirected Graphs	2
Breaking the Metric Voting Distortion Barrier	2
Locally-iterative Distributed (Δ + 1)-coloring and Applications	2

Exponentially Faster Shortest Paths in the Congested Clique	2
Spatial Isolation Implies Zero Knowledge Even in a Quantum World	2
Oracle Separation of BQP and PH	2
The Price of Anarchy of Strategic Queuing Systems	2
Anonymous Shared Memory	2
Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing	2
Orbit-finite Linear Programming	2
Subsampling Suffices for Adaptive Data Analysis	2
The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness	2
Convex Hulls of Random Order Types	2
Flow-augmentation I: Directed graphs	1
Acceleration by Stepsize Hedging: Multi-Step Descent and the Silver Stepsize Schedule	1
Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound	1
The Space Complexity of Consensus from Swap	1
Chains, Koch Chains, and Point Sets with Many Triangulations	1
Co-lexicographically Ordering Automata and Regular Languages - Part I	1
The Topological Mu-Calculus: Completeness and Decidability	1
Clique Is Hard on Average for Regular Resolution	1
Two-round Multiparty Secure Computation from Minimal Assumptions	1
Invited Article Foreword	1
SPARKs: Succinct Parallelizable Arguments of Knowledge	1
Smoothed Analysis with Adaptive Adversaries	1
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler–Leman Refinement Steps	1
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems	1
Learning Equilibria in Matching Markets with Bandit Feedback	1
OptORAMa: Optimal Oblivious RAM	1
How to Delegate Computations: The Power of No-Signaling Proofs	1
Better-Than-2 Approximations for Weighted Tree Augmentation and Applications to Steiner Tree	1
A Correctness and Incorrectness Program Logic	1
Generative Datalog with Continuous Distributions	1
Balancing Straight-line Programs	1
Response Time Distribution in a Tandem Pair of Queues with Batch Processing	1
Efficient Convex Optimization Requires Superlinear Memory	1
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs	1