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

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

Non-Black-Box Worst-Case to Average-Case Reductions Within $\mathsf{NP}$	4
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	4
Further Collapses in $\boldsymbol{\mathsf{TFNP}}$	4
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	4
Nearly Optimal Static Las Vegas Succinct Dictionary	4
On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization	4
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	4
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	4
On the Complexity of Equilibrium Computation in First-Price Auctions	4
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	3
Semidefinite Programming and Linear Equations vs. Homomorphism Problems	3
Caching with Time Windows and Delays	3
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	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
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	3
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	3
Balanced Allocation: Patience Is Not a Virtue	3
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	3
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria	3
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More	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
PTAS for Minimum Cost MultiCovering with Disks	3
Almost-Optimal Sublinear Additive Spanners	3
Tracing Isomanifolds in $\mathbb{R}$ ^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	2
Isomorphism Testing for Graphs Excluding Small Minors	2
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	2
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs	2
Fast Metric Embedding into the Hamming Cube	2
On Ray Shooting for Triangles in 3-Space and Related Problems	2
Inapproximability of Matrix $\boldsymbol{p \rightarrow q}$ Norms	2
Sublinear Time Approximation of the Cost of a Metric ${k}$-Nearest Neighbor Graph	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
Spectral Methods from Tensor Networks	2
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	2
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	2
Semialgebraic Proofs, IPS Lower Bounds, and the $\boldsymbol{\tau}$-Conjecture: Can a Natural Number be Negative?	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
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $\boldsymbol{H}$-Free Graphs	2
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	2
Corrigendum: Metric Embedding via Shortest Path Decompositions	2
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$	2
Truly Optimal Euclidean Spanners	2
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2
Sorting Short Keys in Circuits of Size ${o(n \log n)}$	2
A Short List of Equalities Induces Large Sign-Rank	2

Erratum: A Full Dichotomy for $\textsf{Holant}^\mathbf{c}$, Inspired by Quantum Computation	2
Constant Inapproximability for PPA	2
Want to Gather? No Need to Chatter!	2
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	2
Satisfiability in MultiValued Circuits	2
Deterministic Massively Parallel Connectivity	2

Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)	4
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	4
Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\)	4
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	4
Nearly Optimal Static Las Vegas Succinct Dictionary	4
On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization	4
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	4
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	4
On the Complexity of Equilibrium Computation in First-Price Auctions	4
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	3
Semidefinite Programming and Linear Equations vs. Homomorphism Problems	3
Caching with Time Windows and Delays	3
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	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
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	3
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	3
Balanced Allocation: Patience Is Not a Virtue	3
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	3
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria	3
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More	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
PTAS for Minimum Cost MultiCovering with Disks	3
Almost-Optimal Sublinear Additive Spanners	3
Tracing Isomanifolds in \(\mathbb{R}\) ^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	2
Isomorphism Testing for Graphs Excluding Small Minors	2
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	2
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs	2
Fast Metric Embedding into the Hamming Cube	2
On Ray Shooting for Triangles in 3-Space and Related Problems	2
Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms	2
Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph	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
Spectral Methods from Tensor Networks	2
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	2
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	2
Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?	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
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs	2
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	2
Corrigendum: Metric Embedding via Shortest Path Decompositions	2
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$	2
Truly Optimal Euclidean Spanners	2
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2
Sorting Short Keys in Circuits of Size ${o(n \log n)}$	2
A Short List of Equalities Induces Large Sign-Rank	2

Erratum: A Full Dichotomy for \(\textsf{Holant}^\mathbf{c}\), Inspired by Quantum Computation	2
Constant Inapproximability for PPA	2
Want to Gather? No Need to Chatter!	2
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	2
Satisfiability in MultiValued Circuits	2
Deterministic Massively Parallel Connectivity	2