OOIR: Observatory of International Research

Papers

(The TQCC of SIAM Journal on Computing is 2. 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 2022-01-01 to 2026-01-01.)

Article	Citations
Tight Revenue Gaps among Multiunit Mechanisms	20
Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier	15
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths	15
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion	11
Flow-Augmentation III: Complexity Dichotomy for Boolean CSPs Parameterized by the Number of Unsatisfied Constraints	11
Metric Embedding via Shortest Path Decompositions	11
Induced Subgraphs of Bounded Treewidth and the Container Method	10
Testing Graph Properties with the Container Method	10
Competitively Chasing Convex Bodies	9
A Single-Exponential Time 2-Approximation Algorithm for Treewidth	9
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem	8
Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number	8
Minimum Cuts in Surface Graphs	8
Revisionist Simulations: A New Approach to Proving Space Lower Bounds	8
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments	8
Circuits Resilient to Short-Circuit Errors	7
Parameterized Complexity of Untangling Knots	7
Dynamic Geometric Set Cover, Revisited	7
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification	7
Further Collapses in $\boldsymbol{\mathsf{TFNP}}$	6
One-Way Functions and (Im)perfect Obfuscation	6
Toward Derandomizing Markov Chain Monte Carlo	6
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance	6
An Improved Upper Bound for the Universal TSP on the Grid	5
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes	5

Non-Black-Box Worst-Case to Average-Case Reductions Within $\mathsf{NP}$	5
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	5
On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization	5
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	5
Ghost Value Augmentation for ${k}$-Edge-Connectivity	5
On the Complexity of Equilibrium Computation in First-Price Auctions	5
The Approximate Degree of DNF and CNF Formulas	5
Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius	5
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	5
Nearly Optimal Static Las Vegas Succinct Dictionary	4
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	4
Balanced Allocation: Patience Is Not a Virtue	4
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	4
Improved Optimal Testing Results from Global Hypercontractivity	4
Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians	4
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More	4
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions	4
Almost-Optimal Sublinear Additive Spanners	4
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	4
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	4
On Ray Shooting for Triangles in 3-Space and Related Problems	3
Sorting Short Keys in Circuits of Size ${o(n \log n)}$	3
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	3
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	3
Online Edge Coloring Is (Nearly) as Easy as Offline	3
Isomorphism Testing for Graphs Excluding Small Minors	3
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing	3
Exact Algorithms and Lower Bounds for Stable Instances of Euclidean $\boldsymbol{k}$- means	3
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer	3
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for $\textsf{ACC}$ Circuits	3
Caching with Time Windows and Delays	3
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	3
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs	3
Spectral Methods from Tensor Networks	3
Truly Optimal Euclidean Spanners	3
PTAS for Minimum Cost MultiCovering with Disks	3
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	3
Semidefinite Programming and Linear Equations vs. Homomorphism Problems	3
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	3
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	3
Fast Metric Embedding into the Hamming Cube	2
Want to Gather? No Need to Chatter!	2
Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model	2
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding	2
Inapproximability of Matrix $\boldsymbol{p \rightarrow q}$ Norms	2
Constant Inapproximability for PPA	2
$\boldsymbol{\Pi_2^P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem	2
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019)	2
Deterministic Massively Parallel Connectivity	2
Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering	2

Approximate Graph Coloring and the Crystal with a Hollow Shadow	2
Agreement Tests on Graphs and Hypergraphs	2
Fitting Metrics and Ultrametrics with Minimum Disagreements	2
Relaxed Local Correctability from Local Testing	2
Erratum: A Full Dichotomy for $\textsf{Holant}^\mathbf{c}$, Inspired by Quantum Computation	2
Tracing Isomanifolds in $\mathbb{R}$ ^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	2
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	2
A Short List of Equalities Induces Large Sign-Rank	2
Sublinear Time Approximation of the Cost of a Metric ${k}$-Nearest Neighbor Graph	2
Corrigendum: Metric Embedding via Shortest Path Decompositions	2
A Unified Framework of Light Spanners I: Fast (Yet Optimal) Constructions	2
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	2
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $\boldsymbol{H}$-Free Graphs	2
Satisfiability in MultiValued Circuits	2
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited	2
Semialgebraic Proofs, IPS Lower Bounds, and the $\boldsymbol{\tau}$-Conjecture: Can a Natural Number be Negative?	2