SIAM Journal on Computing

Papers
(The median citation count of SIAM Journal on Computing is 0. 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.)
ArticleCitations
Optimal (Euclidean) Metric Compression11
Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier9
Special Section on the Forty-Ninth Annual ACM Symposium on the Theory of Computing (STOC 2017)9
Fast Generalized DFTs for All Finite Groups8
Parallel Repetition for the GHZ Game: Exponential Decay7
Caching with Time Windows and Delays7
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions6
Metric Embedding via Shortest Path Decompositions6
Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions6
An Approximate Generalization of the Okamura–Seymour Theorem6
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions5
Why Extension-Based Proofs Fail4
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao4
Clustering Mixtures with Almost Optimal Separation in Polynomial Time4
A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane4
Optimal Algorithms for Geometric Centers and Depth4
Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model4
Fitting Metrics and Ultrametrics with Minimum Disagreements4
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side4
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for \(\textsf{ACC}\) Circuits4
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion4
Unit Capacity Maxflow in Almost $m^{4/3}$ Time3
Tree-Depth and the Formula Complexity of Subgraph Isomorphism3
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness3
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes3
Polynomial Data Structure Lower Bounds in the Group Model3
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity3
Tight Revenue Gaps among Multiunit Mechanisms3
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough3
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization3
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge3
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering3
Induced Subgraphs of Bounded Treewidth and the Container Method3
Sorting Short Keys in Circuits of Size ${o(n \log n)}$2
Almost Optimal SuperConstant-Pass Streaming Lower Bounds for Reachability2
Special Section on the Fifty-First Annual ACM Sympositum on the Theory of Computing (STOC 2019)2
Minimum Cuts in Surface Graphs2
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error2
Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs2
Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time2
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs2
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random2
Hop-Constrained Oblivious Routing2
Weak Zero-Knowledge beyond the Black-Box Barrier2
Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling2
Approximation Algorithms for LCS and LIS with Truly Improved Running Times2
Competitively Chasing Convex Bodies2
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs2
Geodesic Walks in Polytopes2
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems2
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem2
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All \({\ell_{{p}}}\) Norms1
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs1
On Ray Shooting for Triangles in 3-Space and Related Problems1
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs1
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches1
Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number1
Differentially Private Learning of Geometric Concepts1
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification1
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture1
Economical Convex Coverings and Applications1
Revisionist Simulations: A New Approach to Proving Space Lower Bounds1
Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?1
Derandomization from Algebraic Hardness1
A Local Search Framework for Experimental Design1
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification1
Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions1
A Short List of Equalities Induces Large Sign-Rank1
CLAP: A New Algorithm for Promise CSPs1
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems1
Online List Labeling: Breaking the \({\log^2 n}\) Barrier1
Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\)1
An Optimal Separation of Randomized and Quantum Query Complexity1
Discrepancy Minimization via a Self-Balancing Walk1
Isomorphism Testing for Graphs Excluding Small Minors1
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring1
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$1
Contextual Search via Intrinsic Volumes1
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders1
Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier1
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments1
An Improved Parameterized Algorithm for Treewidth1
Traversing Combinatorial 0/1-Polytopes via Optimization1
A Single-Exponential Time 2-Approximation Algorithm for Treewidth1
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions1
Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring1
Optimal Resizable Arrays1
Two Variable Logic with Ultimately Periodic Counting1
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model1
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank0
Multi-Item Nontruthful Auctions Achieve Good Revenue0
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics0
On a Combinatorial Generation Problem of Knuth0
Super-Logarithmic Lower Bounds for Dynamic Graph Problems0
An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions0
Balanced Allocation: Patience Is Not a Virtue0
Uniform Restricted Chase Termination0
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity0
Approximating Maximum Independent Set for Rectangles in the Plane0
Anchored Parallel Repetition for Nonlocal Games0
Algebraic Algorithms for Fractional Linear Matroid Parity via Noncommutative Rank0
Nearly Optimal Static Las Vegas Succinct Dictionary0
Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid0
On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization0
Counting Subgraphs in Somewhere Dense Graphs0
Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering0
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations0
On CDCL-Based Proof Systems with the Ordered Decision Strategy0
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing0
Rounds vs. Communication Tradeoffs for Maximal Independent Sets0
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics0
Lower Bounds for External Memory Integer Sorting via Network Coding0
Internal Pattern Matching Queries in a Text and Applications0
Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits0
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals0
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication0
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing0
A Parameterized Approximation Scheme for Min $k$-Cut0
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise0
On Min Sum Vertex Cover and Generalized Min Sum Set Cover0
Generic Reed–Solomon Codes Achieve List-Decoding Capacity0
Parameterized Complexity of Untangling Knots0
Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time0
Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming0
The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs0
Low-Density Parity-Check Codes Achieve List-Decoding Capacity0
Deterministic Massively Parallel Connectivity0
An Improved Upper Bound for the Universal TSP on the Grid0
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees0
Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph0
Elastic-Degenerate String Matching via Fast Matrix Multiplication0
A Tight Analysis of Bethe Approximation for Permanent0
Complexity Classification Transfer for CSPs via Algebraic Products0
A Spectral Approach to Network Design0
A Strong Version of Cobham’s Theorem0
Proximity Search for Maximal Subgraph Enumeration0
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics0
Unambiguous DNFs and Alon–Saks–Seymour0
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm0
Almost Tight Bounds for Reordering Buffer Management0
Almost-Optimal Sublinear Additive Spanners0
On the Computability of Continuous Maximum Entropy Distributions with Applications0
Tracing Isomanifolds in \(\mathbb{R}\) d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations0
Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs0
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs0
A Framework for the Secretary Problem on the Intersection of Matroids0
Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu0
Average Sensitivity of Graph Algorithms0
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games0
Online Edge Coloring via Tree Recurrences and Correlation Decay0
Approximating Minimum Representations of Key Horn Functions0
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree0
How to Trap a Gradient Flow0
Corrigendum: Metric Embedding via Shortest Path Decompositions0
Flow Time Scheduling and Prefix Beck–Fiala0
Topology and Adjunction in Promise Constraint Satisfaction0
Fast FPT-Approximation of Branchwidth0
The Power of Two Choices in Graphical Allocation0
Sharp Thresholds in Random Simple Temporal Graphs0
Circuits Resilient to Short-Circuit Errors0
The Optimal Error Resilience of Interactive Communication over Binary Channels0
An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences0
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection0
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions0
Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring0
Special Section on the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (2020)0
Symmetries, Graph Properties, and Quantum Speedups0
Satisfiability in MultiValued Circuits0
A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines0
One-Way Functions and (Im)perfect Obfuscation0
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes0
Want to Gather? No Need to Chatter!0
Proof Complexity and the Binary Encoding of Combinatorial Principles0
An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem0
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm0
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria0
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion0
On the Complexity of Equilibrium Computation in First-Price Auctions0
Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace0
Rigid Matrices from Rectangular PCPs0
AdWords in a Panorama0
Constant Inapproximability for PPA0
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem0
Counting Small Induced Subgraphs with Hereditary Properties0
PTAS for Minimum Cost MultiCovering with Disks0
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle0
Constant Depth Formula and Partial Function Versions of MCSP Are Hard0
Reducing Path TSP to TSP0
Efficient Construction of Rigid Matrices Using an NP Oracle0
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue0
Consensus-Halving: Does It Ever Get Easier?0
The Shortest Even Cycle Problem Is Tractable0
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020)0
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)0
FIXP-Membership via Convex Optimization: Games, Cakes, and Markets0
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer0
Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018)0
Removing Additive Structure in 3SUM-Based Reductions0
Sublinear Algorithms for Local Graph-Centrality Estimation0
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover0
Classical Verification of Quantum Computations0
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich0
On Matrix Multiplication and Polynomial Identity Testing0
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence0
An ETH-Tight Exact Algorithm for Euclidean TSP0
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction0
Reachability Preservers: New Extremal Bounds and Approximation Algorithms0
Spectral Methods from Tensor Networks0
Smoothing the Gap Between NP and ER0
Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification0
Fast Metric Embedding into the Hamming Cube0
Decidability of Membership Problems for Flat Rational Subsets of \(\boldsymbol{{\textrm{GL}}(2,\boldsymbol{{\mathbb{Q}}})}\) and Singular Matrices0
Truly Optimal Euclidean Spanners0
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation0
Counting Small Induced Subgraphs Satisfying Monotone Properties0
Approximate Gomory–Hu Tree is Faster than \(\boldsymbol{n}\,\boldsymbol{-\, 1}\) Maximum Flows0
Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders0
Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius0
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings0
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving0
Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms0
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance0
Distributed Lower Bounds for Ruling Sets0
Prophet Secretary for Combinatorial Auctions and Matroids0
Testing Linear-Invariant Properties0
Exact-Size Sampling of Enriched Trees in Linear Time0
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension0
0.039978981018066