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

Article	Citations
A Proof of the CSP Dichotomy Conjecture	51
Universally Composable Security	47
Solving Linear Programs in the Current Matrix Multiplication Time	47
Planar Graphs Have Bounded Queue-Number	33
On Nonconvex Optimization for Machine Learning	29
A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem	22
Distribution-free, Risk-controlling Prediction Sets	19
Twin-width I: Tractable FO Model Checking	17
A Simple and Approximately Optimal Mechanism for an Additive Buyer	15
Fully Online Matching	15
Algebraic Approach to Promise Constraint Satisfaction	15
Competitive Caching with Machine Learned Advice	14
Polynomial Multiplication over Finite Fields in Time \( O(n \log n \)	14
The Reachability Problem for Petri Nets Is Not Elementary	14
Representative Sets and Irrelevant Vertices	13
Automating Resolution is NP-Hard	13
Adjacency Labelling for Planar Graphs (and Beyond)	13
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device	12
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time	11
String Diagram Rewrite Theory I: Rewriting with Frobenius Structure	11
The Power of Shunning	10
A Universal Law of Robustness via Isoperimetry	10
Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time	10
Parallelism in Randomized Incremental Algorithms	10
Balancing Straight-line Programs	10

Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound	8
Forcing and Calculi for Hybrid Logics	8
Logical Relations as Types: Proof-Relevant Parametricity for Program Modules	8
Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce	8
The Log-Approximate-Rank Conjecture Is False	8
Near-optimal Distributed Triangle Enumeration via Expander Decompositions	8
Lower Bounds for Maximal Matchings and Maximal Independent Sets	8
Near-linear Time Approximation Schemes for Clustering in Doubling Metrics	8
OptORAMa: Optimal Oblivious RAM	8
The Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization	7
The Art Gallery Problem is ∃ℝ-complete	7
Atomic Embeddability, Clustered Planarity, and Thickenability	7
A Unified Translation of Linear Temporal Logic to ω-Automata	7
Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election	6
Frege Systems for Quantified Boolean Logic	6
Chasing Convex Bodies with Linear Competitive Ratio	6
The Marriage of Univalence and Parametricity	6
A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization	6
A Correctness and Incorrectness Program Logic	6
Distributed Exact Shortest Paths in Sublinear Time	6
Kernel-based Methods for Bandit Convex Optimization	5
Parameterized Intractability of Even Set and Shortest Vector Problem	5
Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime	5
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS	5
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs	5
The Reachability Problem for Two-Dimensional Vector Addition Systems with States	5
Planar Graph Perfect Matching Is in NC	5
Embeddability in R ³ is NP-hard	4
Enumeration for FO Queries over Nowhere Dense Graphs	4
Locally-iterative Distributed (Δ + 1)-coloring and Applications	4
Tight Bounds for Asymptotic and Approximate Consensus	4
Complexity Analysis of Generalized and Fractional Hypertree Decompositions	4
Polynomiality for Bin Packing with a Constant Number of Item Types	4
Semantic Optimization of Conjunctive Queries	4
A Framework for Adversarially Robust Streaming Algorithms	4
Bernoulli Factories and Black-box Reductions in Mechanism Design	4
On Small-depth Frege Proofs for Tseitin for Grids	4
Optimal Auctions through Deep Learning: Advances in Differentiable Economics	4
Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations	4
Adversarially Robust Streaming Algorithms via Differential Privacy	3
Near-optimal Sample Complexity Bounds for Robust Learning of Gaussian Mixtures via Compression Schemes	3
Oracle-efficient Online Learning and Auction Design	3
Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning	3
Convex Hulls of Random Order Types	3
Identity-based Encryption from the Diffie-Hellman Assumption	3
Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks	3
A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities	3
Edge-Weighted Online Bipartite Matching	3
Counting Subgraphs in Degenerate Graphs	3
Co-lexicographically Ordering Automata and Regular Languages - Part I	3

Beyond Natural Proofs: Hardness Magnification and Locality	2
Private and Online Learnability Are Equivalent	2
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree	2
On Strongest Algebraic Program Invariants	2
Separating Rank Logic from Polynomial Time	2
Iceberg Hashing: Optimizing Many Hash-Table Criteria at Once	2
Optimal Bounds for the k -cut Problem	2
#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes	2
How to Delegate Computations: The Power of No-Signaling Proofs	2
Decentralized Asynchronous Crash-resilient Runtime Verification	2
Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes	2
A Near-linear Time ε-Approximation Algorithm for Geometric Bipartite Matching	2
Properly Learning Decision Trees in almost Polynomial Time	2
On the Need for Large Quantum Depth	2
Minimizing Convex Functions with Rational Minimizers	2
General Strong Polarization	2
Generative Datalog with Continuous Distributions	1
Simple Uncoupled No-regret Learning Dynamics for Extensive-form Correlated Equilibrium	1
Exponentially Faster Massively Parallel Maximal Matching	1
Clique Is Hard on Average for Regular Resolution	1
Two-round Multiparty Secure Computation from Minimal Assumptions	1
Adversarial Bandits with Knapsacks	1
The Price of Anarchy of Strategic Queuing Systems	1
How to Construct Quantum Random Functions	1
Smooth Approximation of Lipschitz Maps and Their Subgradients	1
Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit	1
Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors	1
Game Semantics for Interface Middleweight Java	1
Response Time Distribution in a Tandem Pair of Queues with Batch Processing	1
Uniform, Integral, and Feasible Proofs for the Determinant Identities	1
Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and Complexity	1
On the Descriptive Complexity of Temporal Constraint Satisfaction Problems	1
On the Power of Symmetric Linear Programs	1