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-08-01 to 2026-08-01.)

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

A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification	5
Toward Derandomizing Markov Chain Monte Carlo	5
The Approximate Degree of DNF and CNF Formulas	5
Separating MAX 2-AND, MAX DI-CUT, and MAX CUT	5
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	4
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	4
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	4
Ghost Value Augmentation for ${k}$-Edge-Connectivity	4
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	4
Non-Black-Box Worst-Case to Average-Case Reductions Within $\mathsf{NP}$	4
On the Complexity of Equilibrium Computation in First-Price Auctions	4
Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time	4
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	3
PTAS for Minimum Cost MultiCovering with Disks	3
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions	3
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	3
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	3
Distributed Edge Coloring in Time Polylogarithmic in ${\Delta }$	3
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for $\textsf{ACC}$ Circuits	3
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	3
Almost-Optimal Sublinear Additive Spanners	3
Improved Optimal Testing Results from Global Hypercontractivity	3
Quantum Eigenvalue Processing	3
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More	3
Semidefinite Programming and Linear Equations vs. Homomorphism Problems	3
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	3
Balanced Allocation: Patience Is Not a Virtue	3
Settling the Complexity of Nash Equilibrium in Congestion Games	3
Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians	3
Doubly Efficient Private Information Retrieval and Fully Homomorphic Ram Computation from Ring LWE	3
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination	3
Inapproximability of Matrix $\boldsymbol{p \rightarrow q}$ Norms	2
Constant-Depth Arithmetic Circuits for Linear Algebra Problems	2
Agreement Tests on Graphs and Hypergraphs	2
Want to Gather? No Need to Chatter!	2
Relaxed Local Correctability from Local Testing	2
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $\boldsymbol{H}$-Free Graphs	2
Erratum: A Full Dichotomy for $\textsf{Holant}^\mathbf{c}$, Inspired by Quantum Computation	2
Quantum Speedups for Linear Programming via Interior Point Methods	2
Exact Algorithms and Lower Bounds for Stable Instances of Euclidean $\boldsymbol{k}$- means	2
Spectral Methods from Tensor Networks	2
Tracing Isomanifolds in $\mathbb{R}$ ^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	2
Corrigendum: Metric Embedding via Shortest Path Decompositions	2
A Logarithmic Lower Bound for Oblivious RAM (For All Parameters)	2
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding	2
Fitting Metrics and Ultrametrics with Minimum Disagreements	2
Approximate Graph Coloring and the Crystal with a Hollow Shadow	2
A Unified Framework of Light Spanners I: Fast (Yet Optimal) Constructions	2
Deterministic Massively Parallel Connectivity	2

Laplace Transform–Based Quantum Eigenvalue Transformation via Linear Combination of Hamiltonian Simulation	2
$\boldsymbol{\Pi_2^P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem	2
Isomorphism Testing for Graphs Excluding Small Minors	2
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited	2
Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares	2
Sublinear Time Approximation of the Cost of a Metric ${k}$-Nearest Neighbor Graph	2
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019)	2
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	2
Constant Inapproximability for PPA	2
Space Complexity of Vertex Connectivity Oracles	2
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	2
Semialgebraic Proofs, IPS Lower Bounds, and the $\boldsymbol{\tau}$-Conjecture: Can a Natural Number be Negative?	2
Online Edge Coloring Is (Nearly) as Easy as Offline	2
Quantum Time-Space Tradeoffs for Matrix Problems	2
Fast Metric Embedding into the Hamming Cube	2

Laplace Transform–Based Quantum Eigenvalue Transformation via Linear Combination of Hamiltonian Simulation	2
\(\boldsymbol{\Pi_2^P}\) vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem	2
Isomorphism Testing for Graphs Excluding Small Minors	2
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited	2
Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares	2
Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph	2
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019)	2
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	2
Constant Inapproximability for PPA	2
Space Complexity of Vertex Connectivity Oracles	2
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	2
Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?	2
Online Edge Coloring Is (Nearly) as Easy as Offline	2
Quantum Time-Space Tradeoffs for Matrix Problems	2
Fast Metric Embedding into the Hamming Cube	2