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 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
Algorithmic Stability for Adaptive Data Analysis	9
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
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
Toward Tight Approximation Bounds for Graph Diameter and Eccentricities	5
Derandomization from Algebraic Hardness	5
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
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
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
On a Combinatorial Generation Problem of Knuth	3
An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences	3
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
Four-Coloring $P_6$-Free Graphs. I. Extending an Excellent Precoloring	2
Geodesic Walks in Polytopes	2
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao	2
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	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
Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors	2
The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs	2

Smoothing the Gap Between NP and ER	2
Distributed Spanner Approximation	2
Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling	2
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness	2
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side	2
An ETH-Tight Exact Algorithm for Euclidean TSP	2
Counting Small Induced Subgraphs Satisfying Monotone Properties	2
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	2
Approximating Minimum Representations of Key Horn Functions	2
Truly Optimal Euclidean Spanners	2
Isomorphism Testing for Graphs Excluding Small Minors	2
Counting Solutions to Random CNF Formulas	2
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	2
Optimal (Euclidean) Metric Compression	2
Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace	2
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication	2
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	2
Satisfiability in MultiValued Circuits	2
Dynamic Sampling from Graphical Models	2
Multi-Item Nontruthful Auctions Achieve Good Revenue	1
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs	1
Uniform Restricted Chase Termination	1
Effective Wireless Scheduling via Hypergraph Sketches	1
Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time	1
Caching with Time Windows and Delays	1
Counting Small Induced Subgraphs with Hereditary Properties	1
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	1
Consensus-Halving: Does It Ever Get Easier?	1
Deterministic Massively Parallel Connectivity	1
One-Way Functions and (Im)perfect Obfuscation	1
A Short List of Equalities Induces Large Sign-Rank	1
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion	1
Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs	1
A $\boldsymbol{\phi }$ -Competitive Algorithm for Scheduling Packets with Deadlines	1
Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems	1
Efficient Construction of Rigid Matrices Using an NP Oracle	1
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs	1
Tight Bounds for the Subspace Sketch Problem with Applications	1
Corrigendum: LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs	1
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games	1
An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions	1
FIXP-Membership via Convex Optimization: Games, Cakes, and Markets	1
Tracing Isomanifolds in $\mathbb{R}$ ^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	1
Lower Bounds for External Memory Integer Sorting via Network Coding	1
Contextual Search via Intrinsic Volumes	1
A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals	1
On Ray Shooting for Triangles in 3-Space and Related Problems	1
Corrigendum: Metric Embedding via Shortest Path Decompositions	1
Weak Zero-Knowledge beyond the Black-Box Barrier	1
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions	1
NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs	1
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations	1
Tree-Depth and the Formula Complexity of Subgraph Isomorphism	1
On the Complexity of Equilibrium Computation in First-Price Auctions	1
Why Extension-Based Proofs Fail	1
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics	1
Maximum Rectilinear Convex Subsets	1
Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu	1
Four-Coloring $\boldsymbol{P_6}$-Free Graphs. II. Finding an Excellent Precoloring	1
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$	1
Explicit Near-Ramanujan Graphs of Every Degree	1
Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
Inapproximability of Matrix $\boldsymbol{p \rightarrow q}$ Norms	1
Hop-Constrained Oblivious Routing	1