SIAM Journal on Computing

Article	Citations
Tight Revenue Gaps among Multiunit Mechanisms	15
Induced Subgraphs of Bounded Treewidth and the Container Method	12
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths	11
Metric Embedding via Shortest Path Decompositions	10
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion	10
Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier	10
Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number	9
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments	7
Minimum Cuts in Surface Graphs	7
Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time	7
A Single-Exponential Time 2-Approximation Algorithm for Treewidth	6
Revisionist Simulations: A New Approach to Proving Space Lower Bounds	6
Competitively Chasing Convex Bodies	6
Circuits Resilient to Short-Circuit Errors	5
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification	5
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem	5
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes	5
Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\)	5
Parameterized Complexity of Untangling Knots	5
An Improved Upper Bound for the Universal TSP on the Grid	4
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)	4
On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization	4
Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius	4
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	4
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance	4

One-Way Functions and (Im)perfect Obfuscation	4
On the Complexity of Equilibrium Computation in First-Price Auctions	4
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	3
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	3
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer	3
PTAS for Minimum Cost MultiCovering with Disks	3
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	3
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	3
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria	3
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions	3
Improved Optimal Testing Results from Global Hypercontractivity	3
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More	3
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	3
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	3
Nearly Optimal Static Las Vegas Succinct Dictionary	3
Almost-Optimal Sublinear Additive Spanners	3
A Tight Analysis of Bethe Approximation for Permanent	3
Balanced Allocation: Patience Is Not a Virtue	3
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	2
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	2
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for \(\textsf{ACC}\) Circuits	2
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs	2
Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering	2
Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?	2
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$	2
Isomorphism Testing for Graphs Excluding Small Minors	2
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	2
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	2
Truly Optimal Euclidean Spanners	2
A Short List of Equalities Induces Large Sign-Rank	2
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2
Deterministic Massively Parallel Connectivity	2
On Ray Shooting for Triangles in 3-Space and Related Problems	2
Sorting Short Keys in Circuits of Size ${o(n \log n)}$	2
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	2
Caching with Time Windows and Delays	2
Semidefinite Programming and Linear Equations vs. Homomorphism Problems	2
Spectral Methods from Tensor Networks	2
Tracing Isomanifolds in \(\mathbb{R}\) d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	2
Fast Metric Embedding into the Hamming Cube	2
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing	2
On CDCL-Based Proof Systems with the Ordered Decision Strategy	1
Faster Isomorphism for \({p}\)-Groups of Class 2 and Exponent \({p}\)	1
Proof Complexity and the Binary Encoding of Combinatorial Principles	1
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model	1
Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms	1
A Logarithmic Lower Bound for Oblivious RAM (For All Parameters)	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
Agreement Tests on Graphs and Hypergraphs	1
Counting Small Induced Subgraphs with Hereditary Properties	1

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding	1
Corrigendum: Metric Embedding via Shortest Path Decompositions	1
Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming	1
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	1
On the Computability of Continuous Maximum Entropy Distributions with Applications	1
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence	1
Special Section on the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (2020)	1
Two Variable Logic with Ultimately Periodic Counting	1
Derandomization from Algebraic Hardness	1
Discrepancy Minimization via a Self-Balancing Walk	1
Parallel Repetition for the GHZ Game: Exponential Decay	1
Constant Depth Formula and Partial Function Versions of MCSP Are Hard	1
Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model	1
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	1
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings	1
Satisfiability in MultiValued Circuits	1
Classical Verification of Quantum Computations	1
The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs	1
On Matrix Multiplication and Polynomial Identity Testing	1
Contextual Search via Intrinsic Volumes	1
An Improved Parameterized Algorithm for Treewidth	1
Constant Inapproximability for PPA	1
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random	1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring	1
Fitting Metrics and Ultrametrics with Minimum Disagreements	1
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	1
Want to Gather? No Need to Chatter!	1
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs	1
An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions	1
Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph	1
Sublinear Algorithms for Local Graph-Centrality Estimation	1
Low-Density Parity-Check Codes Achieve List-Decoding Capacity	0
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches	0
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing	0
Why Extension-Based Proofs Fail	0
Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders	0
Geodesic Walks in Polytopes	0
Approximation Algorithms for LCS and LIS with Truly Improved Running Times	0
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs	0
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics	0
An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences	0
Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions	0
Optimal Resizable Arrays	0
Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs	0
Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid	0
A Local Search Framework for Experimental Design	0
A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane	0
Special Section on the Forty-Ninth Annual ACM Symposium on the Theory of Computing (STOC 2017)	0
Rigid Matrices from Rectangular PCPs	0
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification	0
The Shortest Even Cycle Problem Is Tractable	0
Optimal Algorithms for Geometric Centers and Depth	0
Packing Cycles in Planar and Bounded-Genus Graphs	0
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem	0
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich	0
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing	0
Internal Pattern Matching Queries in a Text and Applications	0
Decidability of Membership Problems for Flat Rational Subsets of \(\boldsymbol{{\textrm{GL}}(2,\boldsymbol{{\mathbb{Q}}})}\) and Singular Matrices	0
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise	0
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders	0
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games	0
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations	0
Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018)	0
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication	0
The Power of Two Choices in Graphical Allocation	0
Online Edge Coloring via Tree Recurrences and Correlation Decay	0
How to Trap a Gradient Flow	0
Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits	0
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection	0
Algebraic Algorithms for Fractional Linear Matroid Parity via Noncommutative Rank	0
Efficient Construction of Rigid Matrices Using an NP Oracle	0
Shortest Paths Without a Map, but with an Entropic Regularizer	0
Hop-Constrained Oblivious Routing	0
Tree-Depth and the Formula Complexity of Subgraph Isomorphism	0
Computational Complexity of the Hylland–Zeckhauser Mechanism for One-Sided Matching Markets	0
Weak Zero-Knowledge beyond the Black-Box Barrier	0
Average Sensitivity of Graph Algorithms	0
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes	0
Multi-Item Nontruthful Auctions Achieve Good Revenue	0
Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling	0

Fixed-Parameter Algorithms for the Kneser and Schrijver Problems	0
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture	0
A Strong Version of Cobham’s Theorem	0
Online List Labeling: Breaking the \({\log^2 n}\) Barrier	0
Optimal (Euclidean) Metric Compression	0
Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier	0
Fast FPT-Approximation of Branchwidth	0
A \({d}^{{1/2+{o}(1)}}\) Monotonicity Tester for Boolean Functions on \({d}\)-Dimensional Hypergrids	0
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough	0
Flow Time Scheduling and Prefix Beck–Fiala	0
Polynomial Data Structure Lower Bounds in the Group Model	0
Counting Subgraphs in Somewhere Dense Graphs	0
Economical Convex Coverings and Applications	0
Fast Generalized DFTs for All Finite Groups	0
Sharp Thresholds in Random Simple Temporal Graphs	0
Elastic-Degenerate String Matching via Fast Matrix Multiplication	0
Interior Point Methods Are Not Worse than Simplex	0
On a Combinatorial Generation Problem of Knuth	0
Testing Linear-Invariant Properties	0
Smoothing the Gap Between NP and ER	0
Reachability Preservers: New Extremal Bounds and Approximation Algorithms	0
Uniform Restricted Chase Termination	0
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness	0
Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu	0
Exact-Size Sampling of Enriched Trees in Linear Time	0
FIXP-Membership via Convex Optimization: Games, Cakes, and Markets	0
Approximate Gomory–Hu Tree is Faster than \(\boldsymbol{n}\,\boldsymbol{-\, 1}\) Maximum Flows	0
Almost Tight Bounds for Reordering Buffer Management	0
Symmetries, Graph Properties, and Quantum Speedups	0
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction	0
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All \({\ell_{{p}}}\) Norms	0
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics	0
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion	0
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems	0
Complexity Classification Transfer for CSPs via Algebraic Products	0
A Framework for the Secretary Problem on the Intersection of Matroids	0
Approximating Maximum Independent Set for Rectangles in the Plane	0
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020)	0
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side	0
Prophet Secretary for Combinatorial Auctions and Matroids	0
Clustering Mixtures with Almost Optimal Separation in Polynomial Time	0
A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines	0
Almost Optimal SuperConstant-Pass Streaming Lower Bounds for Reachability	0
Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring	0
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions	0
Removing Additive Structure in 3SUM-Based Reductions	0
CLAP: A New Algorithm for Promise CSPs	0
Traversing Combinatorial 0/1-Polytopes via Optimization	0
Special Section on the Fifty-First Annual ACM Sympositum on the Theory of Computing (STOC 2019)	0
From Contention Resolution to Matroid Secretary and Back	0
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs	0
Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions	0
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs	0
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover	0
Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring	0
An Approximate Generalization of the Okamura–Seymour Theorem	0
The Optimal Error Resilience of Interactive Communication over Binary Channels	0
Lower Bounds for External Memory Integer Sorting via Network Coding	0
The Minimum Formula Size Problem is (ETH) Hard	0
Consensus-Halving: Does It Ever Get Easier?	0
Reducing Path TSP to TSP	0
Distributed Lower Bounds for Ruling Sets	0
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm	0
An ETH-Tight Exact Algorithm for Euclidean TSP	0
Unambiguous DNFs and Alon–Saks–Seymour	0
A Spectral Approach to Network Design	0
A Parameterized Approximation Scheme for Min $k$-Cut	0
An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem	0
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics	0
Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification	0
Differentially Private Learning of Geometric Concepts	0
Differentially Private Sampling from Distributions	0
Rounds vs. Communication Tradeoffs for Maximal Independent Sets	0
Approximating Minimum Representations of Key Horn Functions	0
AdWords in a Panorama	0
Counting Small Induced Subgraphs Satisfying Monotone Properties	0
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue	0
Anchored Parallel Repetition for Nonlocal Games	0
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity	0
Super-Logarithmic Lower Bounds for Dynamic Graph Problems	0
Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time	0
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization	0
Topology and Adjunction in Promise Constraint Satisfaction	0
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	0
ABE for Circuits with poly\( {(\lambda )}\)-Sized Keys from LWE	0
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering	0
Proximity Search for Maximal Subgraph Enumeration	0
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao	0