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 2020-11-01 to 2024-11-01.)

Article	Citations
Solving Linear Programs in the Current Matrix Multiplication Time	65
On Nonconvex Optimization for Machine Learning	38
Distribution-free, Risk-controlling Prediction Sets	34
Competitive Caching with Machine Learned Advice	29
A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem	27
Twin-width I: Tractable FO Model Checking	27
Algebraic Approach to Promise Constraint Satisfaction	26
Polynomial Multiplication over Finite Fields in Time \( O(n \log n \)	19
A Universal Law of Robustness via Isoperimetry	18
The Reachability Problem for Petri Nets Is Not Elementary	18
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device	17
String Diagram Rewrite Theory I: Rewriting with Frobenius Structure	16
Near-optimal Distributed Triangle Enumeration via Expander Decompositions	15
Adjacency Labelling for Planar Graphs (and Beyond)	15
Balancing Straight-line Programs	13
Lower Bounds for Maximal Matchings and Maximal Independent Sets	12
Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce	12
The Art Gallery Problem is ∃ℝ-complete	11
Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time	11
A Correctness and Incorrectness Program Logic	11
Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound	10
OptORAMa: Optimal Oblivious RAM	10
The Marriage of Univalence and Parametricity	9
The Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization	9
Near-linear Time Approximation Schemes for Clustering in Doubling Metrics	9

Chasing Convex Bodies with Linear Competitive Ratio	9
Tight Bounds for Asymptotic and Approximate Consensus	9
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS	8
A Framework for Adversarially Robust Streaming Algorithms	8
Optimal Auctions through Deep Learning: Advances in Differentiable Economics	8
Kernel-based Methods for Bandit Convex Optimization	8
Logical Relations as Types: Proof-Relevant Parametricity for Program Modules	8
Locally-iterative Distributed (Δ + 1)-coloring and Applications	7
Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election	7
Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning	7
Atomic Embeddability, Clustered Planarity, and Thickenability	7
The Reachability Problem for Two-Dimensional Vector Addition Systems with States	6
Bernoulli Factories and Black-box Reductions in Mechanism Design	6
On Strongest Algebraic Program Invariants	6
Polynomiality for Bin Packing with a Constant Number of Item Types	6
Parameterized Intractability of Even Set and Shortest Vector Problem	6
Edge-Weighted Online Bipartite Matching	5
On the Need for Large Quantum Depth	5
Decentralized Asynchronous Crash-resilient Runtime Verification	5
Iceberg Hashing: Optimizing Many Hash-Table Criteria at Once	5
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs	5
Complexity Analysis of Generalized and Fractional Hypertree Decompositions	5
Adversarial Bandits with Knapsacks	5
Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime	5
On Small-depth Frege Proofs for Tseitin for Grids	4
Enumeration for FO Queries over Nowhere Dense Graphs	4
Counting Subgraphs in Degenerate Graphs	4
How to Delegate Computations: The Power of No-Signaling Proofs	4
Beyond Natural Proofs: Hardness Magnification and Locality	4
Convex Hulls of Random Order Types	4
How to Construct Quantum Random Functions	4
Identity-based Encryption from the Diffie-Hellman Assumption	4
Separating Rank Logic from Polynomial Time	4
Adversarially Robust Streaming Algorithms via Differential Privacy	4
Nearly Optimal Pseudorandomness from Hardness	4
#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes	4
Co-lexicographically Ordering Automata and Regular Languages - Part I	4
Oracle Separation of BQP and PH	3
Exponentially Faster Shortest Paths in the Congested Clique	3
Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks	3
Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes	3
Anonymous Shared Memory	3
Simple Uncoupled No-regret Learning Dynamics for Extensive-form Correlated Equilibrium	3
Private and Online Learnability Are Equivalent	3
Proximity Gaps for Reed–Solomon Codes	3
On the Zeros of Exponential Polynomials	2
Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors	2
Rate-independent Computation in Continuous Chemical Reaction Networks	2
Minimizing Convex Functions with Rational Minimizers	2
Spatial Isolation Implies Zero Knowledge Even in a Quantum World	2

Balanced Allocations with the Choice of Noise	2
Optimal Bounds for the k -cut Problem	2
Two-round Multiparty Secure Computation from Minimal Assumptions	2
Cerise: Program Verification on a Capability Machine in the Presence of Untrusted Code	2
General Strong Polarization	2
Whole-grain Petri Nets and Processes	2
A Domain-theoretic Approach to Statistical Programming Languages	2
On the Descriptive Complexity of Temporal Constraint Satisfaction Problems	2
Properly Learning Decision Trees in almost Polynomial Time	2
A New Algorithm for Euclidean Shortest Paths in the Plane	2
Game Semantics for Interface Middleweight Java	2
A Logical Approach to Type Soundness	2
Uniform, Integral, and Feasible Proofs for the Determinant Identities	2
Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring	1
Smooth Approximation of Lipschitz Maps and Their Subgradients	1
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems	1
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs	1
Sketching Approximability of All Finite CSPs	1
Faster Modular Composition	1
Lower Bounds on Implementing Mediators in Asynchronous Systems with Rational and Malicious Agents	1
Verifiable Quantum Advantage without Structure	1
First Price Auction is 1-1/ e ² Efficient	1
Response Time Distribution in a Tandem Pair of Queues with Batch Processing	1
Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes	1
Exponentially Faster Massively Parallel Maximal Matching	1
Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and Complexity	1
Learning to Branch: Generalization Guarantees and Limits of Data-Independent Discretization	1
Clique Is Hard on Average for Regular Resolution	1
On the Power of Symmetric Linear Programs	1
Faster High-accuracy Log-concave Sampling via Algorithmic Warm Starts	1
The Frobenius and Factor Universality Problems of the Kleene Star of a Finite Set of Words	1
Foundations of Differentially Oblivious Algorithms	1
Generative Datalog with Continuous Distributions	1
Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications	1
EFX Exists for Three Agents	1
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs	1
Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit	1
Learning Equilibria in Matching Markets with Bandit Feedback	1
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler–Leman Refinement Steps	1
QCSP Monsters and the Demise of the Chen Conjecture	1
The Bitcoin Backbone Protocol: Analysis and Applications	1
The Price of Anarchy of Strategic Queuing Systems	1