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

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

Optimal Multi-Distribution Learning	10
Adjacency Labelling for Planar Graphs (and Beyond)	10
Computing a Fixed Point of Contraction Maps in Polynomial Queries	10
Twin-width I: Tractable FO Model Checking	10
Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime	9
Cerise: Program Verification on a Capability Machine in the Presence of Untrusted Code	9
Toward a Better Understanding of Randomized Greedy Matching	9
A Compositional Theory of Linearizability	9
The Complexity of Computing KKT Solutions of Quadratic Programs	8
Faster Modular Composition	7
On Strongest Algebraic Program Invariants	7
An Efficient Quantum Factoring Algorithm	7
Topological Characterization of Consensus in Distributed Systems	7
Smoothed Analysis of Information Spreading in Dynamic Networks	7
On the Need for Large Quantum Depth	7
On the Zeros of Exponential Polynomials	7
Efficient Normalization of Linear Temporal Logic	6
Gradual System F	6
Negative-Weight Single-Source Shortest Paths in Near-linear Time	6
Memory Checking Requires Logarithmic Overhead	6
Invited Article Foreword	6
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
Coverability in VASS Revisited: Improving Rackoff’s Bounds to Obtain Conditional Optimality	5
Transaction Fee Mechanism Design	5
Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring	5
Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes	5
Axiomatization of Compact Initial Value Problems: Open Properties	5
Fine-grained Cryptanalysis: Tight Conditional Bounds for Dense k -SUM and k -XOR	4
Simple Uncoupled No-regret Learning Dynamics for Extensive-form Correlated Equilibrium	4
Whole-grain Petri Nets and Processes	4
Lower Bounds for Maximal Matchings and Maximal Independent Sets	4
Decision List Compression by Mild Random Restrictions	4
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS	4
Deterministic Minimum Cut in Poly-logarithmic Maximum Flows	3
Invited Articles Foreword	3
Separations in Proof Complexity and TFNP	3
Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning	3
Adaptive and Fair Transformation for Recoverable Mutual Exclusion	3
QCSP Monsters and the Demise of the Chen Conjecture	3
2-Approximation for Prize-Collecting Steiner Forest	3
Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors	3
General Strong Polarization	3
Anonymous Shared Memory	2
Hardness of Approximate Diameter: Now for Undirected Graphs	2
Locally-iterative Distributed (Δ + 1)-coloring and Applications	2
Parameterized Inapproximability Hypothesis under ETH	2
The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness	2
Subsampling Suffices for Adaptive Data Analysis	2

Pliability and Approximating Max-CSPs	2
Breaking the Metric Voting Distortion Barrier	2
Orbit-finite Linear Programming	2
Exponentially Faster Shortest Paths in the Congested Clique	2
Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead	2
Oracle Separation of BQP and PH	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
Logical Relations as Types: Proof-Relevant Parametricity for Program Modules	2
Spatial Isolation Implies Zero Knowledge Even in a Quantum World	2
Chains, Koch Chains, and Point Sets with Many Triangulations	2
Convex Hulls of Random Order Types	1
Co-lexicographically Ordering Automata and Regular Languages - Part I	1
How to Delegate Computations: The Power of No-Signaling Proofs	1
Geometric Embeddability of Complexes is ∃ℝ-complete	1
Efficient Convex Optimization Requires Superlinear Memory	1
Near-linear Time Approximation Schemes for Clustering in Doubling Metrics	1
OptORAMa: Optimal Oblivious RAM	1
Better-Than-2 Approximations for Weighted Tree Augmentation and Applications to Steiner Tree	1
Dominantly Truthful Peer Prediction Mechanisms with a Finite Number of Tasks	1
SPARKs: Succinct Parallelizable Arguments of Knowledge	1
Learning Equilibria in Matching Markets with Bandit Feedback	1
Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound	1
Distribution-free, Risk-controlling Prediction Sets	1
Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications	1
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems	1
Two-round Multiparty Secure Computation from Minimal Assumptions	1
Acceleration by Stepsize Hedging: Multi-Step Descent and the Silver Stepsize Schedule	1
Smoothed Analysis with Adaptive Adversaries	1
The Space Complexity of Consensus from Swap	1
A Correctness and Incorrectness Program Logic	1
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler–Leman Refinement Steps	1
Exponentially Faster Massively Parallel Maximal Matching	1
Flow-augmentation I: Directed graphs	1
The Topological Mu-Calculus: Completeness and Decidability	1
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time	1
The Price of Anarchy of Strategic Queuing Systems	1
Generative Datalog with Continuous Distributions	1