OOIR: Observatory of International Research

Papers

(The TQCC 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-03-01 to 2025-03-01.)

Article	Citations
Optimal (Euclidean) Metric Compression	11
Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier	9
Special Section on the Forty-Ninth Annual ACM Symposium on the Theory of Computing (STOC 2017)	9
Fast Generalized DFTs for All Finite Groups	8
Parallel Repetition for the GHZ Game: Exponential Decay	7
Caching with Time Windows and Delays	7
Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions	6
An Approximate Generalization of the Okamura–Seymour Theorem	6
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	6
Metric Embedding via Shortest Path Decompositions	6
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions	5
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side	4
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for $\textsf{ACC}$ Circuits	4
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion	4
Why Extension-Based Proofs Fail	4
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao	4
Clustering Mixtures with Almost Optimal Separation in Polynomial Time	4
A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane	4
Optimal Algorithms for Geometric Centers and Depth	4
Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model	4
Fitting Metrics and Ultrametrics with Minimum Disagreements	4
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	3
Tree-Depth and the Formula Complexity of Subgraph Isomorphism	3
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness	3
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes	3

Polynomial Data Structure Lower Bounds in the Group Model	3
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	3
Tight Revenue Gaps among Multiunit Mechanisms	3
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough	3
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization	3
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	3
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering	3
Induced Subgraphs of Bounded Treewidth and the Container Method	3
Approximation Algorithms for LCS and LIS with Truly Improved Running Times	2
Competitively Chasing Convex Bodies	2
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs	2
Geodesic Walks in Polytopes	2
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems	2
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem	2
Sorting Short Keys in Circuits of Size ${o(n \log n)}$	2
Almost Optimal SuperConstant-Pass Streaming Lower Bounds for Reachability	2
Special Section on the Fifty-First Annual ACM Sympositum on the Theory of Computing (STOC 2019)	2
Minimum Cuts in Surface Graphs	2
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	2
Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs	2
Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time	2
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs	2
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random	2
Hop-Constrained Oblivious Routing	2
Weak Zero-Knowledge beyond the Black-Box Barrier	2
Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling	2
Traversing Combinatorial 0/1-Polytopes via Optimization	1
A Single-Exponential Time 2-Approximation Algorithm for Treewidth	1
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	1
Four-Coloring $P_6$-Free Graphs. I. Extending an Excellent Precoloring	1
Optimal Resizable Arrays	1
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model	1
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ${\ell_{{p}}}$ Norms	1
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs	1
On Ray Shooting for Triangles in 3-Space and Related Problems	1
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs	1
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches	1
Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number	1
Differentially Private Learning of Geometric Concepts	1
Two Variable Logic with Ultimately Periodic Counting	1
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification	1
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture	1
Economical Convex Coverings and Applications	1
Revisionist Simulations: A New Approach to Proving Space Lower Bounds	1
Semialgebraic Proofs, IPS Lower Bounds, and the $\boldsymbol{\tau}$-Conjecture: Can a Natural Number be Negative?	1
A Local Search Framework for Experimental Design	1
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification	1
Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions	1
A Short List of Equalities Induces Large Sign-Rank	1
CLAP: A New Algorithm for Promise CSPs	1

When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems	1
Online List Labeling: Breaking the ${\log^2 n}$ Barrier	1
Further Collapses in $\boldsymbol{\mathsf{TFNP}}$	1
Derandomization from Algebraic Hardness	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
Discrepancy Minimization via a Self-Balancing Walk	1
Isomorphism Testing for Graphs Excluding Small Minors	1
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing	1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring	1
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$	1
Contextual Search via Intrinsic Volumes	1
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders	1
Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier	1
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments	1
An Improved Parameterized Algorithm for Treewidth	1

When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems	1
Online List Labeling: Breaking the \({\log^2 n}\) Barrier	1
Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\)	1
Derandomization from Algebraic Hardness	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
Discrepancy Minimization via a Self-Balancing Walk	1
Isomorphism Testing for Graphs Excluding Small Minors	1
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing	1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring	1
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$	1
Contextual Search via Intrinsic Volumes	1
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders	1
Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier	1
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments	1
An Improved Parameterized Algorithm for Treewidth	1