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 2021-09-01 to 2025-09-01.)

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

Further Collapses in $\boldsymbol{\mathsf{TFNP}}$	4
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	4
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	4
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	4
Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius	4
On the Complexity of Equilibrium Computation in First-Price Auctions	4
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	4
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes	4
Non-Black-Box Worst-Case to Average-Case Reductions Within $\mathsf{NP}$	4
Nearly Optimal Static Las Vegas Succinct Dictionary	4
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	3
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria	3
Balanced Allocation: Patience Is Not a Virtue	3
PTAS for Minimum Cost MultiCovering with Disks	3
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	3
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer	3
Almost-Optimal Sublinear Additive Spanners	3
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	3
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	3
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	3
Semidefinite Programming and Linear Equations vs. Homomorphism Problems	3
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions	3
Improved Optimal Testing Results from Global Hypercontractivity	3
A Tight Analysis of Bethe Approximation for Permanent	3
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More	3
Caching with Time Windows and Delays	3
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	3
Sublinear Time Approximation of the Cost of a Metric ${k}$-Nearest Neighbor Graph	2
On Ray Shooting for Triangles in 3-Space and Related Problems	2
Tracing Isomanifolds in $\mathbb{R}$ ^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	2
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs	2
Sorting Short Keys in Circuits of Size ${o(n \log n)}$	2
Semialgebraic Proofs, IPS Lower Bounds, and the $\boldsymbol{\tau}$-Conjecture: Can a Natural Number be Negative?	2
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	2
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	2
Inapproximability of Matrix $\boldsymbol{p \rightarrow q}$ Norms	2
Want to Gather? No Need to Chatter!	2
Satisfiability in MultiValued Circuits	2
A Short List of Equalities Induces Large Sign-Rank	2
Spectral Methods from Tensor Networks	2
Isomorphism Testing for Graphs Excluding Small Minors	2
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	2
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	2
Fast Metric Embedding into the Hamming Cube	2
Truly Optimal Euclidean Spanners	2
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $\boldsymbol{H}$-Free Graphs	2
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019)	2
Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering	2
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing	2
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2

Online Edge Coloring Is (Nearly) as Easy as Offline	2
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for $\textsf{ACC}$ Circuits	2
Deterministic Massively Parallel Connectivity	2
Constant Inapproximability for PPA	2
Approximate Graph Coloring and the Crystal with a Hollow Shadow	2
Corrigendum: Metric Embedding via Shortest Path Decompositions	2
Erratum: A Full Dichotomy for $\textsf{Holant}^\mathbf{c}$, Inspired by Quantum Computation	2

Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\)	4
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	4
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	4
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	4
Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius	4
On the Complexity of Equilibrium Computation in First-Price Auctions	4
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	4
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes	4
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)	4
Nearly Optimal Static Las Vegas Succinct Dictionary	4
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	3
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria	3
Balanced Allocation: Patience Is Not a Virtue	3
PTAS for Minimum Cost MultiCovering with Disks	3
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	3
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer	3
Almost-Optimal Sublinear Additive Spanners	3
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	3
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	3
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	3
Semidefinite Programming and Linear Equations vs. Homomorphism Problems	3
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions	3
Improved Optimal Testing Results from Global Hypercontractivity	3
A Tight Analysis of Bethe Approximation for Permanent	3
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More	3
Caching with Time Windows and Delays	3
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	3
Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph	2
On Ray Shooting for Triangles in 3-Space and Related Problems	2
Tracing Isomanifolds in \(\mathbb{R}\) ^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	2
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs	2
Sorting Short Keys in Circuits of Size ${o(n \log n)}$	2
Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?	2
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	2
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	2
Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms	2
Want to Gather? No Need to Chatter!	2
Satisfiability in MultiValued Circuits	2
A Short List of Equalities Induces Large Sign-Rank	2
Spectral Methods from Tensor Networks	2
Isomorphism Testing for Graphs Excluding Small Minors	2
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	2
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	2
Fast Metric Embedding into the Hamming Cube	2
Truly Optimal Euclidean Spanners	2
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs	2
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019)	2
Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering	2
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing	2
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2