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

Article	Citations
Complexity Analysis of Generalized and Fractional Hypertree Decompositions	37
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device	34
Invited Article Foreword	29
Decision List Compression by Mild Random Restrictions	28
Intermediate Value Linearizability: A Quantitative Correctness Criterion	22
Lower Bounds on Implementing Mediators in Asynchronous Systems with Rational and Malicious Agents	20
Parallel Acyclic Joins: Optimal Algorithms and Cyclicity Separation	19
Algebraic Approach to Promise Constraint Satisfaction	18
Cerise: Program Verification on a Capability Machine in the Presence of Untrusted Code	17
Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning	17
Query Lower Bounds for Log-concave Sampling	17
Separating Rank Logic from Polynomial Time	16
Minimizing Convex Functions with Rational Minimizers	14
General Strong Polarization	12
Adjacency Labelling for Planar Graphs (and Beyond)	12
Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime	12
Decentralized Asynchronous Crash-resilient Runtime Verification	12
Separations in Proof Complexity and TFNP	10
Almost Optimal Exact Distance Oracles for Planar Graphs	10
Faster High-accuracy Log-concave Sampling via Algorithmic Warm Starts	10
QCSP Monsters and the Demise of the Chen Conjecture	10
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time	9
The Complexity and Expressive Power of Limit Datalog	9
Toward a Better Understanding of Randomized Greedy Matching	9
Acceleration by Stepsize Hedging: Multi-Step Descent and the Silver Stepsize Schedule	9

Fine-grained Cryptanalysis: Tight Conditional Bounds for Dense k -SUM and k -XOR	9
Balancing Straight-line Programs	9
A Compositional Theory of Linearizability	9
String Diagram Rewrite Theory I: Rewriting with Frobenius Structure	8
On the Power of Symmetric Linear Programs	8
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor	8
Invited Articles Foreword	7
Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations	7
A New Algorithm for Euclidean Shortest Paths in the Plane	6
On Strongest Algebraic Program Invariants	6
Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors	6
Fast Algorithms for ℓ _p -Regression	6
Parameterized Intractability of Even Set and Shortest Vector Problem	5
Co-lexicographically Ordering Automata and Regular Languages - Part I	5
An Efficient Quantum Factoring Algorithm	5
Pliability and Approximating Max-CSPs	5
Parallelize Single-Site Dynamics up to Dobrushin Criterion	5
Rate-independent Computation in Continuous Chemical Reaction Networks	5
Topological Characterization of Consensus in Distributed Systems	4
Faster Modular Composition	4
On the Need for Large Quantum Depth	4
Proximity Gaps for Reed–Solomon Codes	4
Two-round Multiparty Secure Computation from Minimal Assumptions	4
Information Acquisition Under Resource Limitations in a Noisy Environment	4
Anonymous Shared Memory	4
How to Delegate Computations: The Power of No-Signaling Proofs	4
Near-optimal Distributed Triangle Enumeration via Expander Decompositions	4
Tight Bounds for Asymptotic and Approximate Consensus	4
Fast Multivariate Multipoint Evaluation over All Finite Fields	4
Adversarial Bandits with Knapsacks	4
Independence in Infinite Probabilistic Databases	3
A Framework for Adversarially Robust Streaming Algorithms	3
Learning Equilibria in Matching Markets with Bandit Feedback	3
Identity-based Encryption from the Diffie-Hellman Assumption	3
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler–Leman Refinement Steps	3
OptORAMa: Optimal Oblivious RAM	3
Robustly Learning General Mixtures of Gaussians	3
The Topological Mu-Calculus: Completeness and Decidability	2
The Reachability Problem for Two-Dimensional Vector Addition Systems with States	2
Properly Learning Decision Trees in almost Polynomial Time	2
Counting Subgraphs in Degenerate Graphs	2
#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes	2
Learning to Branch: Generalization Guarantees and Limits of Data-Independent Discretization	2
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs	2
Optimal Bounds for the k -cut Problem	2
Breaking the Metric Voting Distortion Barrier	2
Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit	2
On the Zeros of Exponential Polynomials	2
Smoothed Analysis of Information Spreading in Dynamic Networks	2
An Improved Bound for Weak Epsilon-nets in the Plane	2

Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing	2
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs	2
Integer programs with bounded subdeterminants and two nonzeros per row	2
Clique Is Hard on Average for Regular Resolution	2
Exponentially Faster Shortest Paths in the Congested Clique	2
Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and Complexity	2
Universal almost Optimal Compression and Slepian-wolf Coding in Probabilistic Polynomial Time	2
Flow-augmentation I: Directed graphs	2
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems	2
Orbit-finite Linear Programming	1
Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes	1
Private and Online Learnability Are Equivalent	1
Pure-Circuit: Tight Inapproximability for PPAD	1
Memory Checking Requires Logarithmic Overhead	1
Iceberg Hashing: Optimizing Many Hash-Table Criteria at Once	1
Gradual System F	1
On the Descriptive Complexity of Temporal Constraint Satisfaction Problems	1
Efficient Convex Optimization Requires Superlinear Memory	1
Invited Article Foreword	1
Directed Shortest Paths via Approximate Cost Balancing	1
Near-linear Time Approximation Schemes for Clustering in Doubling Metrics	1
Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications	1
Exponentially Faster Massively Parallel Maximal Matching	1
Local Proofs Approaching the Witness Length	1
Hardness of Approximate Diameter: Now for Undirected Graphs	1
Sketching Approximability of All Finite CSPs	1
On the Monniaux Problem in Abstract Interpretation	1
Distribution-free, Risk-controlling Prediction Sets	1
Subsampling Suffices for Adaptive Data Analysis	1
Balanced Allocations with the Choice of Noise	1
Sparse Higher Order Čech Filtrations	1
Optimal Auctions through Deep Learning: Advances in Differentiable Economics	1
Killing a Vortex	1
Locally-iterative Distributed (Δ + 1)-coloring and Applications	1