OOIR: Observatory of International Research

Papers

(The TQCC of SIAM Journal on Computing 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-04-01 to 2025-04-01.)

Article	Citations
Optimal (Euclidean) Metric Compression	13
Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier	11
Special Section on the Forty-Ninth Annual ACM Symposium on the Theory of Computing (STOC 2017)	10
Agreement Tests on Graphs and Hypergraphs	9
Fast Generalized DFTs for All Finite Groups	8
Parallel Repetition for the GHZ Game: Exponential Decay	7
Caching with Time Windows and Delays	7
Shortest Paths Without a Map, but with an Entropic Regularizer	6
Metric Embedding via Shortest Path Decompositions	6
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	6
An Approximate Generalization of the Okamura–Seymour Theorem	6
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions	5
Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions	5
Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model	4
Why Extension-Based Proofs Fail	4
Fitting Metrics and Ultrametrics with Minimum Disagreements	4
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao	4
A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane	4
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for $\textsf{ACC}$ Circuits	4
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side	4
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion	4
Clustering Mixtures with Almost Optimal Separation in Polynomial Time	4
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering	3
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	3
Tree-Depth and the Formula Complexity of Subgraph Isomorphism	3

On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness	3
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes	3
Polynomial Data Structure Lower Bounds in the Group Model	3
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	3
Tight Revenue Gaps among Multiunit Mechanisms	3
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	3
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths	3
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization	3
Induced Subgraphs of Bounded Treewidth and the Container Method	3
Optimal Resizable Arrays	2
Sorting Short Keys in Circuits of Size ${o(n \log n)}$	2
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough	2
Special Section on the Fifty-First Annual ACM Sympositum on the Theory of Computing (STOC 2019)	2
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs	2
Competitively Chasing Convex Bodies	2
Approximation Algorithms for LCS and LIS with Truly Improved Running Times	2
Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time	2
Weak Zero-Knowledge beyond the Black-Box Barrier	2
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	2
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments	2
Optimal Algorithms for Geometric Centers and Depth	2
Geodesic Walks in Polytopes	2
Almost Optimal SuperConstant-Pass Streaming Lower Bounds for Reachability	2
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs	2
Discrepancy Minimization via a Self-Balancing Walk	2
Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number	1
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches	1
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs	1
Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier	1
Circuits Resilient to Short-Circuit Errors	1
A Single-Exponential Time 2-Approximation Algorithm for Treewidth	1
An Improved Parameterized Algorithm for Treewidth	1
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems	1
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
Four-Coloring $P_6$-Free Graphs. I. Extending an Excellent Precoloring	1
On Matrix Multiplication and Polynomial Identity Testing	1
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification	1
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing	1
Economical Convex Coverings and Applications	1
Traversing Combinatorial 0/1-Polytopes via Optimization	1
Revisionist Simulations: A New Approach to Proving Space Lower Bounds	1
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model	1
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification	1
Hop-Constrained Oblivious Routing	1
Two Variable Logic with Ultimately Periodic Counting	1
CLAP: A New Algorithm for Promise CSPs	1
Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs	1
Differentially Private Learning of Geometric Concepts	1
Truly Optimal Euclidean Spanners	1

Contextual Search via Intrinsic Volumes	1
On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization	1
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems	1
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem	1
Derandomization from Algebraic Hardness	1
Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling	1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring	1
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing	1
Minimum Cuts in Surface Graphs	1
Online List Labeling: Breaking the ${\log^2 n}$ Barrier	1
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	1
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random	1
Isomorphism Testing for Graphs Excluding Small Minors	1
Flow Time Scheduling and Prefix Beck–Fiala	1
Tracing Isomanifolds in $\mathbb{R}$ ^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	1
Consensus-Halving: Does It Ever Get Easier?	1