OOIR: Observatory of International Research

Papers

(The median citation count of Journal of the ACM is 2. 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 2022-08-01 to 2026-08-01.)

Article	Citations
Near-Linear Runtime for a Classical Matrix Preconditioning Algorithm	54
Ribbon: Fast Succinct Static Retrieval and Approximate Membership	42
Lower Bounds on Implementing Mediators in Asynchronous Systems with Rational and Malicious Agents	36
Minimizing Convex Functions with Rational Minimizers	33
Almost Optimal Exact Distance Oracles for Planar Graphs	32
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time	30
Vertex Connectivity in Poly-logarithmic Max-Flows	29
On the Node-Averaged Complexity of Locally Checkable Problems on Trees	27
Untangling Graphs on Surfaces	24
A New Algorithm for Euclidean Shortest Paths in the Plane	23
Settling the Sample Complexity of Online Reinforcement Learning	23
Parallelize Single-Site Dynamics up to Dobrushin Criterion	22
Proximity Gaps for Reed–Solomon Codes	21
Rate-independent Computation in Continuous Chemical Reaction Networks	20
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams	20
Optimal Computation in Anonymous Dynamic Networks	16
Generative Social Choice	15
Universal almost Optimal Compression and Slepian-wolf Coding in Probabilistic Polynomial Time	15
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits	15
On the Descriptive Complexity of Temporal Constraint Satisfaction Problems	15
Learning to Branch: Generalization Guarantees and Limits of Data-Independent Discretization	14
Stochastic Games with Synchronization Objectives	14
A New Minimax Theorem for Randomized Algorithms	13
Towards P≠NP from Extended Frege lower bounds	12
EFX Exists for Three Agents	11

Indistinguishability Obfuscation from Well-Founded Assumptions	11
A Universal Law of Robustness via Isoperimetry	11
Choiceless Polynomial Time with Witnessed Symmetric Choice	10
How Much Data Is Sufficient to Learn High-Performing Algorithms?	10
Correct and Complete Type Checking and Certified Erasure for Coq , in Coq	10
Relative Error Streaming Quantiles	9
Computing a Fixed Point of Contraction Maps in Polynomial Queries	9
The Complexity of Computing KKT Solutions of Quadratic Programs	9
A Compositional Theory of Linearizability	9
Optimal Multi-Distribution Learning	9
Cerise: Program Verification on a Capability Machine in the Presence of Untrusted Code	8
Toward a Better Understanding of Randomized Greedy Matching	8
Vizing’s Theorem in Near-Linear Time	7
Equivalence and Conditional Independence in Atomic Sheaf Logic	7
Topological Characterization of Consensus in Distributed Systems	7
An Efficient Quantum Factoring Algorithm	6
On the Need for Large Quantum Depth	6
Distributed \Delta -Coloring Plays Hide-and-Seek	6
Faster Modular Composition	6
On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds	6
Smoothed Analysis of Information Spreading in Dynamic Networks	6
On Strongest Algebraic Program Invariants	6
On the Zeros of Exponential Polynomials	6
Memory Checking Requires Logarithmic Overhead	5
A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip	5
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP	5
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection	5
Negative-Weight Single-Source Shortest Paths in Near-linear Time	5
Coverability in VASS Revisited: Improving Rackoff’s Bounds to Obtain Conditional Optimality	5
QCSP Monsters and the Demise of the Chen Conjecture	4
Efficient Normalization of Linear Temporal Logic	4
Transaction Fee Mechanism Design	4
Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning	4
Fine-grained Cryptanalysis: Tight Conditional Bounds for Dense k -SUM and k -XOR	4
Deterministic Minimum Cut in Poly-logarithmic Maximum Flows	4
Approximating Nash Social Welfare by Matching and Local Search	4
Robustly Learning Mixtures of k Arbitrary Gaussians	4
Simple Uncoupled No-regret Learning Dynamics for Extensive-form Correlated Equilibrium	4
Separations in Proof Complexity and TFNP	4
2-Approximation for Prize-Collecting Steiner Forest	4
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS	4
Gradual System F	4
Axiomatization of Compact Initial Value Problems: Open Properties	4
Whole-grain Petri Nets and Processes	4
Adaptive and Fair Transformation for Recoverable Mutual Exclusion	4
Pliability and Approximating Max-CSPs	3
Breaking the Metric Voting Distortion Barrier	3
Exponentially Faster Shortest Paths in the Congested Clique	3
Minimizing Weighted Flow Time	3
Orbit-finite Linear Programming	3

Anonymous Shared Memory	3
Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing	3
Consistency of Relations over Monoids	3
Subsampling Suffices for Adaptive Data Analysis	3
Killing a Vortex	3
Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors	3
Hardness of Approximate Diameter: Now for Undirected Graphs	3
Parameterized Inapproximability Hypothesis under ETH	3
Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time	3
Dominantly Truthful Peer Prediction Mechanisms with a Finite Number of Tasks	2
A Correctness and Incorrectness Program Logic	2
Oracle Separation of BQP and PH	2
The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness	2
Polynomial-Time Pseudodeterministic Construction of Primes	2
Generative Datalog with Continuous Distributions	2
Acceleration by Stepsize Hedging: Multi-Step Descent and the Silver Stepsize Schedule	2
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time	2
The Price of Anarchy of Strategic Queuing Systems	2
Chains, Koch Chains, and Point Sets with Many Triangulations	2
SPARKs: Succinct Parallelizable Arguments of Knowledge	2
Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead	2
Near Optimal Alphabet-Soundness Tradeoff PCPs	2
Convex Hulls of Random Order Types	2
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler–Leman Refinement Steps	2
Better-Than-2 Approximations for Weighted Tree Augmentation and Applications to Steiner Tree	2
Smoothed Analysis with Adaptive Adversaries	2
The Space Complexity of Consensus from Swap	2
An Algorithmic Framework for Black-Box Reductions from Bayesian Mechanism Design to Algorithm Design	2
Symmetric Exponential Time Requires Near-Maximum Circuit Size	2
Multi-Agent Contracts	2
Learning Equilibria in Matching Markets with Bandit Feedback	2
Quantitative Equational Logic	2