OOIR: Observatory of International Research

Papers

(The median citation count 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 2022-05-01 to 2026-05-01.)

Article	Citations
Tight Revenue Gaps among Multiunit Mechanisms	20
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths	16
Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier	16
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion	13
Flow-Augmentation III: Complexity Dichotomy for Boolean CSPs Parameterized by the Number of Unsatisfied Constraints	12
Competitively Chasing Convex Bodies	10
Induced Subgraphs of Bounded Treewidth and the Container Method	10
Testing Graph Properties with the Container Method	10
Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number	9
Minimum Cuts in Surface Graphs	9
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments	9
Revisionist Simulations: A New Approach to Proving Space Lower Bounds	9
Dynamic Geometric Set Cover, Revisited	8
Parameterized Complexity of Untangling Knots	8
Circuits Resilient to Short-Circuit Errors	8
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification	8
A Single-Exponential Time 2-Approximation Algorithm for Treewidth	8
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem	8
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance	7
One-Way Functions and (Im)perfect Obfuscation	6
Further Collapses in $\boldsymbol{\mathsf{TFNP}}$	6
An Improved Upper Bound for the Universal TSP on the Grid	5
The Approximate Degree of DNF and CNF Formulas	5
Non-Black-Box Worst-Case to Average-Case Reductions Within $\mathsf{NP}$	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
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes	5
Toward Derandomizing Markov Chain Monte Carlo	5
Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius	5
On the Complexity of Equilibrium Computation in First-Price Auctions	5
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	4
Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians	4
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	4
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions	4
Improved Optimal Testing Results from Global Hypercontractivity	4
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	4
Ghost Value Augmentation for ${k}$-Edge-Connectivity	4
Nearly Optimal Static Las Vegas Succinct Dictionary	4
Almost-Optimal Sublinear Additive Spanners	4
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	4
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	4
PTAS for Minimum Cost MultiCovering with Disks	3
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	3
Quantum Eigenvalue Processing	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
Online Edge Coloring Is (Nearly) as Easy as Offline	3
Balanced Allocation: Patience Is Not a Virtue	3
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer	3
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination	3
Caching with Time Windows and Delays	3
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	3
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	3
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More	3
Doubly Efficient Private Information Retrieval and Fully Homomorphic Ram Computation from Ring LWE	3
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for $\textsf{ACC}$ Circuits	3
Semidefinite Programming and Linear Equations vs. Homomorphism Problems	3
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	3
Want to Gather? No Need to Chatter!	2
Constant Inapproximability for PPA	2
Sublinear Time Approximation of the Cost of a Metric ${k}$-Nearest Neighbor Graph	2
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2
Deterministic Massively Parallel Connectivity	2
Satisfiability in MultiValued Circuits	2
Semialgebraic Proofs, IPS Lower Bounds, and the $\boldsymbol{\tau}$-Conjecture: Can a Natural Number be Negative?	2
Spectral Methods from Tensor Networks	2
Exact Algorithms and Lower Bounds for Stable Instances of Euclidean $\boldsymbol{k}$- means	2
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited	2
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019)	2
Approximate Graph Coloring and the Crystal with a Hollow Shadow	2
Inapproximability of Matrix $\boldsymbol{p \rightarrow q}$ Norms	2
Fast Metric Embedding into the Hamming Cube	2
Laplace Transform–Based Quantum Eigenvalue Transformation via Linear Combination of Hamiltonian Simulation	2
A Short List of Equalities Induces Large Sign-Rank	2
$\boldsymbol{\Pi_2^P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem	2

Isomorphism Testing for Graphs Excluding Small Minors	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
A Unified Framework of Light Spanners I: Fast (Yet Optimal) Constructions	2
Space Complexity of Vertex Connectivity Oracles	2
Corrigendum: Metric Embedding via Shortest Path Decompositions	2
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $\boldsymbol{H}$-Free Graphs	2
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing	2
Tracing Isomanifolds in $\mathbb{R}$ ^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	2
Quantum Speedups for Linear Programming via Interior Point Methods	2
On Ray Shooting for Triangles in 3-Space and Related Problems	2
Erratum: A Full Dichotomy for $\textsf{Holant}^\mathbf{c}$, Inspired by Quantum Computation	2
Relaxed Local Correctability from Local Testing	2
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding	2
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise	1
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion	1
An Improved Parameterized Algorithm for Treewidth	1
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach	1
Contextual Search via Intrinsic Volumes	1
Classical Verification of Quantum Computations	1
Cheeger’s Inequalities for Vertex Expansion and Reweighted Eigenvalues	1
Constant Depth Formula and Partial Function Versions of MCSP Are Hard	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
On the Computability of Continuous Maximum Entropy Distributions with Applications	1
An FPT Algorithm for the Embeddability of Graphs Into Two-Dimensional Simplicial Complexes	1
A Logarithmic Lower Bound for Oblivious RAM (For All Parameters)	1
Agreement Tests on Graphs and Hypergraphs	1
On CDCL-Based Proof Systems with the Ordered Decision Strategy	1
The Shortest Even Cycle Problem Is Tractable	1
Algebraic Algorithms for Fractional Linear Matroid Parity via Noncommutative Rank	1
On the Nisan–Ronen Conjecture for Submodular Valuations	1
On Matrix Multiplication and Polynomial Identity Testing	1
Super-Logarithmic Lower Bounds for Dynamic Graph Problems	1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring	1
Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming	1
Discrepancy Minimization via a Self-Balancing Walk	1
An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions	1
Constant-Depth Arithmetic Circuits for Linear Algebra Problems	1
Counting Small Induced Subgraphs with Hereditary Properties	1
Reducing Tarski to Unique Tarski (In the Black-Box Model)	1
Parallel Repetition for the GHZ Game: Exponential Decay	1
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence	1
A Spectral Approach to Network Design	1
Sublinear Algorithms for Local Graph-Centrality Estimation	1
The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds	1
Special Section on the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (2020)	1
Online Edge Coloring via Tree Recurrences and Correlation Decay	1
Faster Isomorphism for ${p}$-Groups of Class 2 and Exponent ${p}$	1
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing	1
Order-Competitive Ratio	1
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	1
Two Variable Logic with Ultimately Periodic Counting	1
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings	1
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random	1
The Minimal Faithful Permutation Degree of Groups Without Abelian Normal Subgroups	1
Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares	1
Fitting Metrics and Ultrametrics with Minimum Disagreements	1
Gapped Clique Homology on Weighted Graphs Is ${\text{QMA}_1}$-Hard and Contained in QMA	1
Proof Complexity and the Binary Encoding of Combinatorial Principles	1