OOIR: Observatory of International Research

Papers

(The TQCC of SIAM Journal on Computing is 3. 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-11-01 to 2024-11-01.)

Article	Citations
Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians	50
How to Use Indistinguishability Obfuscation: Deniable Encryption, and More	22
Optimization of the Sherrington--Kirkpatrick Hamiltonian	22
A Little Charity Guarantees Almost Envy-Freeness	17
Error Thresholds for Arbitrary Pauli Noise	15
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy	15
Classical Homomorphic Encryption for Quantum Circuits	13
Online Contention Resolution Schemes with Applications to Bayesian Selection Problems	12
Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications	11
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models	10
CLAP: A New Algorithm for Promise CSPs	9
An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem	9
A Weighted Linear Matroid Parity Algorithm	9
Algorithmic Stability for Adaptive Data Analysis	9
Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders	8
Topology and Adjunction in Promise Constraint Satisfaction	7
Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC	7
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model	7
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich	6
The Complexity of Contracts	6
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems	6
Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time	6
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem	6
New Results on Linear Size Distance Preservers	6
Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs	6

Reducing Path TSP to TSP	6
On the Power of Relaxed Local Decoding Algorithms	6
An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees	6
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	6
List-Decoding with Double Samplers	5
The Communication Complexity of Set Intersection and Multiple Equality Testing	5
Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing	5
Toward Tight Approximation Bounds for Graph Diameter and Eccentricities	5
Derandomization from Algebraic Hardness	5
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	4
Structure Versus Hardness Through the Obfuscation Lens	4
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing	4
From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces	4
Query-to-Communication Lifting Using Low-Discrepancy Gadgets	4
Proximity Search for Maximal Subgraph Enumeration	4
A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP	4
Elastic-Degenerate String Matching via Fast Matrix Multiplication	4
Solving CSPs Using Weak Local Consistency	4
Classical Verification of Quantum Computations	4
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes	4
Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions	4
New Hardness Results for Routing on Disjoint Paths	3
Sublinear Algorithms for Local Graph-Centrality Estimation	3
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	3
Sparse MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture	3
Perfect Secure Computation in Two Rounds	3
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	3
Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits	3
A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation	3
Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming	3
A Polynomial Lower Bound for Testing Monotonicity	3
Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles	3
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering	3
Distributed Lower Bounds for Ruling Sets	3
Perfect $L_p$ Sampling in a Data Stream	3
Nonlocal Games with Noisy Maximally Entangled States are Decidable	3
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction	3
Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations	3
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization	3
Metric Embedding via Shortest Path Decompositions	3
On a Combinatorial Generation Problem of Knuth	3
An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences	3