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

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

The Approximate Degree of DNF and CNF Formulas	5
Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius	5
An Improved Upper Bound for the Universal TSP on the Grid	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	4
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	4
Almost-Optimal Sublinear Additive Spanners	4
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	4
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	4
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions	4
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	4
Improved Optimal Testing Results from Global Hypercontractivity	4
Non-Black-Box Worst-Case to Average-Case Reductions Within $\mathsf{NP}$	4
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	4
Nearly Optimal Static Las Vegas Succinct Dictionary	4
Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians	4
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	4
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
Tracing Isomanifolds in $\mathbb{R}$ ^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	3
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	3
Sorting Short Keys in Circuits of Size ${o(n \log n)}$	3
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More	3
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	3
Balanced Allocation: Patience Is Not a Virtue	3
Isomorphism Testing for Graphs Excluding Small Minors	3
Spectral Methods from Tensor Networks	3
Online Edge Coloring Is (Nearly) as Easy as Offline	3
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs	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
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	3
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	3
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing	3
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	3
Caching with Time Windows and Delays	3
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	2
Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering	2
Deterministic Massively Parallel Connectivity	2
Sublinear Time Approximation of the Cost of a Metric ${k}$-Nearest Neighbor Graph	2
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	2
Approximate Graph Coloring and the Crystal with a Hollow Shadow	2
Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model	2
Constant Inapproximability for PPA	2
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $\boldsymbol{H}$-Free Graphs	2
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited	2
Erratum: A Full Dichotomy for $\textsf{Holant}^\mathbf{c}$, Inspired by Quantum Computation	2
Semialgebraic Proofs, IPS Lower Bounds, and the $\boldsymbol{\tau}$-Conjecture: Can a Natural Number be Negative?	2
A Short List of Equalities Induces Large Sign-Rank	2

Fast Metric Embedding into the Hamming Cube	2
Inapproximability of Matrix $\boldsymbol{p \rightarrow q}$ Norms	2
Parallel Repetition for the GHZ Game: Exponential Decay	2
Agreement Tests on Graphs and Hypergraphs	2
Want to Gather? No Need to Chatter!	2
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding	2
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019)	2
Satisfiability in MultiValued Circuits	2
Truly Optimal Euclidean Spanners	2
On Ray Shooting for Triangles in 3-Space and Related Problems	2
Corrigendum: Metric Embedding via Shortest Path Decompositions	2
Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares	2
Fitting Metrics and Ultrametrics with Minimum Disagreements	2
A Logarithmic Lower Bound for Oblivious RAM (For All Parameters)	2
Relaxed Local Correctability from Local Testing	2
Faster Isomorphism for ${p}$-Groups of Class 2 and Exponent ${p}$	1
Symmetries, Graph Properties, and Quantum Speedups	1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring	1
An Improved Parameterized Algorithm for Treewidth	1
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings	1
Special Section on the Forty-Ninth Annual ACM Symposium on the Theory of Computing (STOC 2017)	1
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions	1
Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification	1
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing	1
Counting Small Induced Subgraphs Satisfying Monotone Properties	1
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence	1
The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds	1
Constant Depth Formula and Partial Function Versions of MCSP Are Hard	1
On CDCL-Based Proof Systems with the Ordered Decision Strategy	1
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach	1
Two Variable Logic with Ultimately Periodic Counting	1
Derandomization from Algebraic Hardness	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
Special Section on the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (2020)	1
Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming	1
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes	1
The Shortest Even Cycle Problem Is Tractable	1
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise	1
Algebraic Algorithms for Fractional Linear Matroid Parity via Noncommutative Rank	1
On the Computability of Continuous Maximum Entropy Distributions with Applications	1
Super-Logarithmic Lower Bounds for Dynamic Graph Problems	1
Proof Complexity and the Binary Encoding of Combinatorial Principles	1
On Matrix Multiplication and Polynomial Identity Testing	1
On the Nisan–Ronen Conjecture for Submodular Valuations	1
Contextual Search via Intrinsic Volumes	1
Discrepancy Minimization via a Self-Balancing Walk	1
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random	1
Classical Verification of Quantum Computations	1
An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions	1
Quantum Lower Bounds by Sample-to-Query Lifting	1
A Spectral Approach to Network Design	1
Testing Linear-Invariant Properties	1
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	1
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion	1
Counting Small Induced Subgraphs with Hereditary Properties	1
Online Edge Coloring via Tree Recurrences and Correlation Decay	1
Sublinear Algorithms for Local Graph-Centrality Estimation	1

Fast Metric Embedding into the Hamming Cube	2
Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms	2
Parallel Repetition for the GHZ Game: Exponential Decay	2
Agreement Tests on Graphs and Hypergraphs	2
Want to Gather? No Need to Chatter!	2
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding	2
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019)	2
Satisfiability in MultiValued Circuits	2
Truly Optimal Euclidean Spanners	2
On Ray Shooting for Triangles in 3-Space and Related Problems	2
Corrigendum: Metric Embedding via Shortest Path Decompositions	2
Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares	2
Fitting Metrics and Ultrametrics with Minimum Disagreements	2
A Logarithmic Lower Bound for Oblivious RAM (For All Parameters)	2
Relaxed Local Correctability from Local Testing	2
Faster Isomorphism for \({p}\)-Groups of Class 2 and Exponent \({p}\)	1
Symmetries, Graph Properties, and Quantum Speedups	1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring	1
An Improved Parameterized Algorithm for Treewidth	1
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings	1
Special Section on the Forty-Ninth Annual ACM Symposium on the Theory of Computing (STOC 2017)	1
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions	1
Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification	1
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing	1
Counting Small Induced Subgraphs Satisfying Monotone Properties	1
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence	1
The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds	1
Constant Depth Formula and Partial Function Versions of MCSP Are Hard	1
On CDCL-Based Proof Systems with the Ordered Decision Strategy	1
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach	1
Two Variable Logic with Ultimately Periodic Counting	1
Derandomization from Algebraic Hardness	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
Special Section on the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (2020)	1
Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming	1
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes	1
The Shortest Even Cycle Problem Is Tractable	1
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise	1
Algebraic Algorithms for Fractional Linear Matroid Parity via Noncommutative Rank	1
On the Computability of Continuous Maximum Entropy Distributions with Applications	1
Super-Logarithmic Lower Bounds for Dynamic Graph Problems	1
Proof Complexity and the Binary Encoding of Combinatorial Principles	1
On Matrix Multiplication and Polynomial Identity Testing	1
On the Nisan–Ronen Conjecture for Submodular Valuations	1
Contextual Search via Intrinsic Volumes	1
Discrepancy Minimization via a Self-Balancing Walk	1
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random	1
Classical Verification of Quantum Computations	1
An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions	1
Quantum Lower Bounds by Sample-to-Query Lifting	1
A Spectral Approach to Network Design	1
Testing Linear-Invariant Properties	1
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	1
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion	1
Counting Small Induced Subgraphs with Hereditary Properties	1
Online Edge Coloring via Tree Recurrences and Correlation Decay	1
Sublinear Algorithms for Local Graph-Centrality Estimation	1