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

Article	Citations
Complexity Analysis of Generalized and Fractional Hypertree Decompositions	38
Balancing Straight-line Programs	34
Intermediate Value Linearizability: A Quantitative Correctness Criterion	34
Almost Optimal Exact Distance Oracles for Planar Graphs	29
A Compositional Theory of Linearizability	26
General Strong Polarization	19
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor	19
Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime	17
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device	16
Fine-grained Cryptanalysis: Tight Conditional Bounds for Dense k -SUM and k -XOR	15
Parallel Acyclic Joins: Optimal Algorithms and Cyclicity Separation	15
Minimizing Convex Functions with Rational Minimizers	13
Invited Article Foreword	12
Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning	12
The Complexity and Expressive Power of Limit Datalog	12
Decision List Compression by Mild Random Restrictions	11
Toward a Better Understanding of Randomized Greedy Matching	11
Faster High-accuracy Log-concave Sampling via Algorithmic Warm Starts	10
Query Lower Bounds for Log-concave Sampling	9
Decentralized Asynchronous Crash-resilient Runtime Verification	9
Lower Bounds on Implementing Mediators in Asynchronous Systems with Rational and Malicious Agents	9
Algebraic Approach to Promise Constraint Satisfaction	9
Separating Rank Logic from Polynomial Time	8
QCSP Monsters and the Demise of the Chen Conjecture	8
On Nonconvex Optimization for Machine Learning	8

Acceleration by Stepsize Hedging: Multi-Step Descent and the Silver Stepsize Schedule	8
Separations in Proof Complexity and TFNP	8
Cerise: Program Verification on a Capability Machine in the Presence of Untrusted Code	7
Adjacency Labelling for Planar Graphs (and Beyond)	7
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time	7
String Diagram Rewrite Theory I: Rewriting with Frobenius Structure	6
Fast Algorithms for ℓ _p -Regression	6
Pliability and Approximating Max-CSPs	6
Parameterized Intractability of Even Set and Shortest Vector Problem	5
Independence in Infinite Probabilistic Databases	5
Rate-independent Computation in Continuous Chemical Reaction Networks	5
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler–Leman Refinement Steps	5
On the Need for Large Quantum Depth	5
On the Power of Symmetric Linear Programs	5
Robustly Learning General Mixtures of Gaussians	5
Invited Articles Foreword	4
An Efficient Quantum Factoring Algorithm	4
Fast Multivariate Multipoint Evaluation over All Finite Fields	4
Adversarial Bandits with Knapsacks	4
Information Acquisition Under Resource Limitations in a Noisy Environment	4
Proximity Gaps for Reed–Solomon Codes	4
Anonymous Shared Memory	4
Near-optimal Distributed Triangle Enumeration via Expander Decompositions	4
How to Delegate Computations: The Power of No-Signaling Proofs	4
A New Algorithm for Euclidean Shortest Paths in the Plane	4
OptORAMa: Optimal Oblivious RAM	4
Two-round Multiparty Secure Computation from Minimal Assumptions	4
Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors	3
Faster Modular Composition	3
On Strongest Algebraic Program Invariants	3
Tight Bounds for Asymptotic and Approximate Consensus	3
Learning Equilibria in Matching Markets with Bandit Feedback	3
Topological Characterization of Consensus in Distributed Systems	3
Co-lexicographically Ordering Automata and Regular Languages - Part I	3
A Framework for Adversarially Robust Streaming Algorithms	3
#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes	2
Clique Is Hard on Average for Regular Resolution	2
Local Proofs Approaching the Witness Length	2
Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and Complexity	2
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems	2
An Improved Bound for Weak Epsilon-nets in the Plane	2
Optimal Bounds for the k -cut Problem	2
Properly Learning Decision Trees in almost Polynomial Time	2
Killing a Vortex	2
Parallelize Single-Site Dynamics up to Dobrushin Criterion	2
On the Zeros of Exponential Polynomials	2
The Reachability Problem for Two-Dimensional Vector Addition Systems with States	2
The Topological Mu-Calculus: Completeness and Decidability	2
Universal almost Optimal Compression and Slepian-wolf Coding in Probabilistic Polynomial Time	2
Learning to Branch: Generalization Guarantees and Limits of Data-Independent Discretization	2

Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit	2
Directed Shortest Paths via Approximate Cost Balancing	2
Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing	1
Counting Subgraphs in Degenerate Graphs	1
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs	1
Exponentially Faster Shortest Paths in the Congested Clique	1
Hardness of Approximate Diameter: Now for Undirected Graphs	1
Optimal Auctions through Deep Learning: Advances in Differentiable Economics	1
Distribution-free, Risk-controlling Prediction Sets	1
EFX Exists for Three Agents	1
Efficient Convex Optimization Requires Superlinear Memory	1
On the Descriptive Complexity of Temporal Constraint Satisfaction Problems	1
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs	1
Smoothed Analysis of Information Spreading in Dynamic Networks	1
Integer programs with bounded subdeterminants and two nonzeros per row	1
The Limitations of Optimization from Samples	1
Private and Online Learnability Are Equivalent	1
Logical Relations as Types: Proof-Relevant Parametricity for Program Modules	1
On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds	1
Near-linear Time Approximation Schemes for Clustering in Doubling Metrics	1
On the Monniaux Problem in Abstract Interpretation	1
Sketching Approximability of All Finite CSPs	1
Locally-iterative Distributed (Δ + 1)-coloring and Applications	1
Identity-based Encryption from the Diffie-Hellman Assumption	1
Flow-augmentation I: Directed graphs	1
Orbit-finite Linear Programming	1
Probabilistic Programming with Exact Conditions	1
Invited Article Foreword	1
Exponentially Faster Massively Parallel Maximal Matching	1
Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications	1
Gradual System F	1
Breaking the Metric Voting Distortion Barrier	1