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 2022-05-01 to 2026-05-01.)

Article	Citations
Vertex Connectivity in Poly-logarithmic Max-Flows	44
Minimizing Convex Functions with Rational Minimizers	39
Lower Bounds on Implementing Mediators in Asynchronous Systems with Rational and Malicious Agents	32
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time	30
Almost Optimal Exact Distance Oracles for Planar Graphs	27
Near-Linear Runtime for a Classical Matrix Preconditioning Algorithm	26
Ribbon: Fast Succinct Static Retrieval and Approximate Membership	24
A New Algorithm for Euclidean Shortest Paths in the Plane	23
Settling the Sample Complexity of Online Reinforcement Learning	20
Proximity Gaps for Reed–Solomon Codes	19
Rate-independent Computation in Continuous Chemical Reaction Networks	19
On the Descriptive Complexity of Temporal Constraint Satisfaction Problems	18
Parallelize Single-Site Dynamics up to Dobrushin Criterion	18
Universal almost Optimal Compression and Slepian-wolf Coding in Probabilistic Polynomial Time	16
Learning to Branch: Generalization Guarantees and Limits of Data-Independent Discretization	15
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits	14
Generative Social Choice	14
The Limitations of Optimization from Samples	13
Stochastic Games with Synchronization Objectives	13
A New Minimax Theorem for Randomized Algorithms	12
EFX Exists for Three Agents	11
Towards P≠NP from Extended Frege lower bounds	10
How Much Data Is Sufficient to Learn High-Performing Algorithms?	10
A Universal Law of Robustness via Isoperimetry	10
Correct and Complete Type Checking and Certified Erasure for Coq , in Coq	9

Relative Error Streaming Quantiles	9
Indistinguishability Obfuscation from Well-Founded Assumptions	9
Choiceless Polynomial Time with Witnessed Symmetric Choice	9
Computing a Fixed Point of Contraction Maps in Polynomial Queries	9
Equivalence and Conditional Independence in Atomic Sheaf Logic	8
Toward a Better Understanding of Randomized Greedy Matching	8
The Complexity of Computing KKT Solutions of Quadratic Programs	8
Optimal Multi-Distribution Learning	8
Cerise: Program Verification on a Capability Machine in the Presence of Untrusted Code	8
A Compositional Theory of Linearizability	8
Topological Characterization of Consensus in Distributed Systems	7
Vizing’s Theorem in Near-Linear Time	7
On the Need for Large Quantum Depth	6
Smoothed Analysis of Information Spreading in Dynamic Networks	6
Faster Modular Composition	6
An Efficient Quantum Factoring Algorithm	6
On Strongest Algebraic Program Invariants	6
On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds	5
Efficient Normalization of Linear Temporal Logic	5
Memory Checking Requires Logarithmic Overhead	5
On the Zeros of Exponential Polynomials	5
Negative-Weight Single-Source Shortest Paths in Near-linear Time	4
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP	4
Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring	4
Simple Uncoupled No-regret Learning Dynamics for Extensive-form Correlated Equilibrium	4
Gradual System F	4
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection	4
Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes	4
Robustly Learning Mixtures of k Arbitrary Gaussians	4
Coverability in VASS Revisited: Improving Rackoff’s Bounds to Obtain Conditional Optimality	4
Axiomatization of Compact Initial Value Problems: Open Properties	4
Transaction Fee Mechanism Design	4
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS	3
Separations in Proof Complexity and TFNP	3
2-Approximation for Prize-Collecting Steiner Forest	3
Pliability and Approximating Max-CSPs	3
Whole-grain Petri Nets and Processes	3
Adaptive and Fair Transformation for Recoverable Mutual Exclusion	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
Approximating Nash Social Welfare by Matching and Local Search	3
Fine-grained Cryptanalysis: Tight Conditional Bounds for Dense k -SUM and k -XOR	3
Deterministic Minimum Cut in Poly-logarithmic Maximum Flows	3
QCSP Monsters and the Demise of the Chen Conjecture	3
Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing	2
Orbit-finite Linear Programming	2
Minimizing Weighted Flow Time	2
Polynomial-Time Pseudodeterministic Construction of Primes	2
Oracle Separation of BQP and PH	2
SPARKs: Succinct Parallelizable Arguments of Knowledge	2

Anonymous Shared Memory	2
Consistency of Relations over Monoids	2
Exponentially Faster Shortest Paths in the Congested Clique	2
Hardness of Approximate Diameter: Now for Undirected Graphs	2
Multi-Agent Contracts	2
The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness	2
An Algorithmic Framework for Black-Box Reductions from Bayesian Mechanism Design to Algorithm Design	2
Killing a Vortex	2
Breaking the Metric Voting Distortion Barrier	2
Parameterized Inapproximability Hypothesis under ETH	2
Subsampling Suffices for Adaptive Data Analysis	2
Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead	2
The Space Complexity of Consensus from Swap	2
Generative Datalog with Continuous Distributions	1
Chains, Koch Chains, and Point Sets with Many Triangulations	1
OptORAMa: Optimal Oblivious RAM	1
Adversarially Robust Streaming Algorithms via Differential Privacy	1
Edge-Weighted Online Bipartite Matching	1
Geometric Embeddability of Complexes is ∃ℝ-complete	1
Survivable Network Design with Group-to-Group Requirement	1
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems	1
Two-round Multiparty Secure Computation from Minimal Assumptions	1
Learning Equilibria in Matching Markets with Bandit Feedback	1
A Correctness and Incorrectness Program Logic	1
The Price of Anarchy of Strategic Queuing Systems	1
Co-lexicographically Ordering Automata and Regular Languages - Part I	1
Convex Hulls of Random Order Types	1
Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structures	1
Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms	1
Flow-augmentation I: Directed graphs	1
Simulating Time with Square-Root Space	1
Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications	1
Better-Than-2 Approximations for Weighted Tree Augmentation and Applications to Steiner Tree	1
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time	1
Symmetric Exponential Time Requires Near-Maximum Circuit Size	1
Dominantly Truthful Peer Prediction Mechanisms with a Finite Number of Tasks	1
Smoothed Analysis with Adaptive Adversaries	1
Efficient Convex Optimization Requires Superlinear Memory	1
Nearly Optimal Pseudorandomness from Hardness	1
A Proof of the Nisan–Ronen Conjecture	1
Exponentially Faster Massively Parallel Maximal Matching	1
The Topological Mu-Calculus: Completeness and Decidability	1
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler–Leman Refinement Steps	1
Acceleration by Stepsize Hedging: Multi-Step Descent and the Silver Stepsize Schedule	1