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 2020-05-01 to 2024-05-01.)

Article	Citations
Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians	39
Optimization of the Sherrington--Kirkpatrick Hamiltonian	19
How to Use Indistinguishability Obfuscation: Deniable Encryption, and More	19
A Little Charity Guarantees Almost Envy-Freeness	14
Error Thresholds for Arbitrary Pauli Noise	10
Classical Homomorphic Encryption for Quantum Circuits	10
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models	9
A Weighted Linear Matroid Parity Algorithm	9
Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications	9
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy	8
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model	7
An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem	7
Online Contention Resolution Schemes with Applications to Bayesian Selection Problems	7
New Results on Linear Size Distance Preservers	6
An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees	6
The Complexity of Contracts	6
Algorithmic Stability for Adaptive Data Analysis	6
Reducing Path TSP to TSP	5
On the Power of Relaxed Local Decoding Algorithms	5
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich	5
Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs	5
Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time	5
Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders	5
Toward Tight Approximation Bounds for Graph Diameter and Eccentricities	4
Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing	4

Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions	4
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	4
Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC	4
From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces	4
Classical Verification of Quantum Computations	4
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems	4
List-Decoding with Double Samplers	3
Structure Versus Hardness Through the Obfuscation Lens	3
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing	3
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	3
On a Combinatorial Generation Problem of Knuth	3
A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation	3
Solving CSPs Using Weak Local Consistency	3
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction	3
A Polynomial Lower Bound for Testing Monotonicity	3
Derandomization from Algebraic Hardness	3
Query-to-Communication Lifting Using Low-Discrepancy Gadgets	3
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem	3
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions	3
Elastic-Degenerate String Matching via Fast Matrix Multiplication	3
Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations	3
CLAP: A New Algorithm for Promise CSPs	3
Perfect $L_p$ Sampling in a Data Stream	3
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	2
Quantum Hardness of Learning Shallow Classical Circuits	2
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem	2
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	2
New Hardness Results for Routing on Disjoint Paths	2
Isomorphism Testing for Graphs Excluding Small Minors	2
Geodesic Walks in Polytopes	2
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering	2
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization	2
Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits	2
An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences	2
Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming	2
Proximity Search for Maximal Subgraph Enumeration	2
Approximating Minimum Representations of Key Horn Functions	2
Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles	2
Counting Solutions to Random CNF Formulas	2
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side	2
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	2
Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace	2
The Communication Complexity of Set Intersection and Multiple Equality Testing	2
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	2
The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs	2
Truly Optimal Euclidean Spanners	2
Distributed Spanner Approximation	2
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	2
Metric Embedding via Shortest Path Decompositions	2
Perfect Secure Computation in Two Rounds	2