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

Article	Citations
Minimizing Convex Functions with Rational Minimizers	54
Lower Bounds on Implementing Mediators in Asynchronous Systems with Rational and Malicious Agents	37
Almost Optimal Exact Distance Oracles for Planar Graphs	34
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time	27
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device	24
Vertex Connectivity in Poly-logarithmic Max-Flows	22
Proximity Gaps for Reed–Solomon Codes	22
A Framework for Adversarially Robust Streaming Algorithms	21
Parallelize Single-Site Dynamics up to Dobrushin Criterion	20
Rate-independent Computation in Continuous Chemical Reaction Networks	20
Settling the Sample Complexity of Online Reinforcement Learning	18
A New Algorithm for Euclidean Shortest Paths in the Plane	16
The Reachability Problem for Two-Dimensional Vector Addition Systems with States	15
Learning to Branch: Generalization Guarantees and Limits of Data-Independent Discretization	15
Universal almost Optimal Compression and Slepian-wolf Coding in Probabilistic Polynomial Time	14
On the Descriptive Complexity of Temporal Constraint Satisfaction Problems	14
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits	13
The Limitations of Optimization from Samples	13
Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and Complexity	13
Stochastic Games with Synchronization Objectives	13
A New Minimax Theorem for Randomized Algorithms	12
EFX Exists for Three Agents	12
A Universal Law of Robustness via Isoperimetry	12
How Much Data Is Sufficient to Learn High-Performing Algorithms?	12
Relative Error Streaming Quantiles	11

Correct and Complete Type Checking and Certified Erasure for Coq , in Coq	11
Chasing Convex Bodies with Linear Competitive Ratio	10
Twin-width I: Tractable FO Model Checking	10
Adjacency Labelling for Planar Graphs (and Beyond)	10
Choiceless Polynomial Time with Witnessed Symmetric Choice	10
Computing a Fixed Point of Contraction Maps in Polynomial Queries	10
Cerise: Program Verification on a Capability Machine in the Presence of Untrusted Code	9
A Compositional Theory of Linearizability	9
Toward a Better Understanding of Randomized Greedy Matching	9
Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime	9
Faster Modular Composition	8
The Complexity of Computing KKT Solutions of Quadratic Programs	8
On Strongest Algebraic Program Invariants	7
On the Need for Large Quantum Depth	7
An Efficient Quantum Factoring Algorithm	7
Topological Characterization of Consensus in Distributed Systems	7
On the Zeros of Exponential Polynomials	7
The Art Gallery Problem is ∃ℝ-complete	6
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection	6
On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds	6
Efficient Normalization of Linear Temporal Logic	6
Gradual System F	6
Smoothed Analysis of Information Spreading in Dynamic Networks	6
Memory Checking Requires Logarithmic Overhead	6
Invited Article Foreword	6
Simple Uncoupled No-regret Learning Dynamics for Extensive-form Correlated Equilibrium	5
Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes	5
Whole-grain Petri Nets and Processes	5
Negative-Weight Single-Source Shortest Paths in Near-linear Time	5
Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring	5
Lower Bounds for Maximal Matchings and Maximal Independent Sets	5
Transaction Fee Mechanism Design	5
QCSP Monsters and the Demise of the Chen Conjecture	4
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS	4
Separations in Proof Complexity and TFNP	4
Decision List Compression by Mild Random Restrictions	4
General Strong Polarization	4
Fine-grained Cryptanalysis: Tight Conditional Bounds for Dense k -SUM and k -XOR	4
2-Approximation for Prize-Collecting Steiner Forest	3
Adaptive and Fair Transformation for Recoverable Mutual Exclusion	3
Anonymous Shared Memory	3
Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning	3
Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors	3
Deterministic Minimum Cut in Poly-logarithmic Maximum Flows	3
Invited Articles Foreword	3
Hardness of Approximate Diameter: Now for Undirected Graphs	2
Exponentially Faster Shortest Paths in the Congested Clique	2
Parameterized Inapproximability Hypothesis under ETH	2
The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness	2
The Price of Anarchy of Strategic Queuing Systems	2

Breaking the Metric Voting Distortion Barrier	2
Orbit-finite Linear Programming	2
Subsampling Suffices for Adaptive Data Analysis	2
Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead	2
Oracle Separation of BQP and PH	2
Convex Hulls of Random Order Types	2
Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing	2
Killing a Vortex	2
Consistency of Relations over Monoids	2
Locally-iterative Distributed (Δ + 1)-coloring and Applications	2
Spatial Isolation Implies Zero Knowledge Even in a Quantum World	2
Chains, Koch Chains, and Point Sets with Many Triangulations	2
Logical Relations as Types: Proof-Relevant Parametricity for Program Modules	2
Pliability and Approximating Max-CSPs	2
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler–Leman Refinement Steps	1
Co-lexicographically Ordering Automata and Regular Languages - Part I	1
The Space Complexity of Consensus from Swap	1
Generative Datalog with Continuous Distributions	1
Smoothed Analysis with Adaptive Adversaries	1
The Topological Mu-Calculus: Completeness and Decidability	1
Edge-Weighted Online Bipartite Matching	1
Exponentially Faster Massively Parallel Maximal Matching	1
Flow-augmentation I: Directed graphs	1
Geometric Embeddability of Complexes is ∃ℝ-complete	1
Better-Than-2 Approximations for Weighted Tree Augmentation and Applications to Steiner Tree	1
Learning Equilibria in Matching Markets with Bandit Feedback	1
A Correctness and Incorrectness Program Logic	1
Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound	1
OptORAMa: Optimal Oblivious RAM	1
Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structures	1
Distribution-free, Risk-controlling Prediction Sets	1
Nearly Optimal Pseudorandomness from Hardness	1
Efficient Convex Optimization Requires Superlinear Memory	1
How to Delegate Computations: The Power of No-Signaling Proofs	1
Acceleration by Stepsize Hedging: Multi-Step Descent and the Silver Stepsize Schedule	1
Dominantly Truthful Peer Prediction Mechanisms with a Finite Number of Tasks	1
Two-round Multiparty Secure Computation from Minimal Assumptions	1
SPARKs: Succinct Parallelizable Arguments of Knowledge	1
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time	1
Near-linear Time Approximation Schemes for Clustering in Doubling Metrics	1
Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications	1
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems	1