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-10-01 to 2024-10-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	31
Competitive Caching with Machine Learned Advice	29
Twin-width I: Tractable FO Model Checking	27
A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem	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
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time	12
A Correctness and Incorrectness Program Logic	11
The Art Gallery Problem is ∃ℝ-complete	11
Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time	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
A Unified Translation of Linear Temporal Logic to ω-Automata	9

Chasing Convex Bodies with Linear Competitive Ratio	9
Near-linear Time Approximation Schemes for Clustering in Doubling Metrics	9
The Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization	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
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
Locally-iterative Distributed (Δ + 1)-coloring and Applications	7
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
The Reachability Problem for Two-Dimensional Vector Addition Systems with States	6
Bernoulli Factories and Black-box Reductions in Mechanism Design	6
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
On the Need for Large Quantum Depth	5
Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime	5
Edge-Weighted Online Bipartite Matching	5
Adversarial Bandits with Knapsacks	5
Decentralized Asynchronous Crash-resilient Runtime Verification	5
Beyond Natural Proofs: Hardness Magnification and Locality	4
Nearly Optimal Pseudorandomness from Hardness	4
How to Construct Quantum Random Functions	4
Semantic Optimization of Conjunctive Queries	4
How to Delegate Computations: The Power of No-Signaling Proofs	4
On Small-depth Frege Proofs for Tseitin for Grids	4
Adversarially Robust Streaming Algorithms via Differential Privacy	4
Counting Subgraphs in Degenerate Graphs	4
#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes	4
Separating Rank Logic from Polynomial Time	4
Convex Hulls of Random Order Types	4
Enumeration for FO Queries over Nowhere Dense Graphs	4
Identity-based Encryption from the Diffie-Hellman Assumption	4
Co-lexicographically Ordering Automata and Regular Languages - Part I	4
Oracle Separation of BQP and PH	3
Private and Online Learnability Are Equivalent	3
Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks	3
Near-optimal Sample Complexity Bounds for Robust Learning of Gaussian Mixtures via Compression Schemes	3
Exponentially Faster Shortest Paths in the Congested Clique	3
Proximity Gaps for Reed–Solomon Codes	3
Simple Uncoupled No-regret Learning Dynamics for Extensive-form Correlated Equilibrium	3
Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes	3
Anonymous Shared Memory	3
A Logical Approach to Type Soundness	2

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