SIAM Journal on Computing

Article	Citations
Tight Revenue Gaps among Multiunit Mechanisms	17
Induced Subgraphs of Bounded Treewidth and the Container Method	13
Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier	11
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion	11
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths	11
Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number	10
Metric Embedding via Shortest Path Decompositions	10
Minimum Cuts in Surface Graphs	9
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments	9
Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time	8
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem	7
Circuits Resilient to Short-Circuit Errors	7
A Single-Exponential Time 2-Approximation Algorithm for Treewidth	7
Competitively Chasing Convex Bodies	7
Revisionist Simulations: A New Approach to Proving Space Lower Bounds	7
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification	7
Dynamic Geometric Set Cover, Revisited	6
Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius	6
The Approximate Degree of DNF and CNF Formulas	6
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes	6
Parameterized Complexity of Untangling Knots	5
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance	5
One-Way Functions and (Im)perfect Obfuscation	5
An Improved Upper Bound for the Universal TSP on the Grid	5
On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization	4

Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	4
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	4
On the Complexity of Equilibrium Computation in First-Price Auctions	4
Toward Derandomizing Markov Chain Monte Carlo	4
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)	4
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	4
Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\)	4
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	4
Nearly Optimal Static Las Vegas Succinct Dictionary	4
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	3
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria	3
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More	3
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer	3
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for \(\textsf{ACC}\) Circuits	3
PTAS for Minimum Cost MultiCovering with Disks	3
Almost-Optimal Sublinear Additive Spanners	3
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	3
Semidefinite Programming and Linear Equations vs. Homomorphism Problems	3
Caching with Time Windows and Delays	3
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	3
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions	3
Improved Optimal Testing Results from Global Hypercontractivity	3
A Tight Analysis of Bethe Approximation for Permanent	3
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	3
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	3
Balanced Allocation: Patience Is Not a Virtue	3
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$	2
Truly Optimal Euclidean Spanners	2
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2
Sorting Short Keys in Circuits of Size ${o(n \log n)}$	2
A Short List of Equalities Induces Large Sign-Rank	2
Erratum: A Full Dichotomy for \(\textsf{Holant}^\mathbf{c}\), Inspired by Quantum Computation	2
Constant Inapproximability for PPA	2
Want to Gather? No Need to Chatter!	2
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	2
Satisfiability in MultiValued Circuits	2
Deterministic Massively Parallel Connectivity	2
Tracing Isomanifolds in \(\mathbb{R}\) d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	2
Isomorphism Testing for Graphs Excluding Small Minors	2
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	2
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs	2
Fast Metric Embedding into the Hamming Cube	2
On Ray Shooting for Triangles in 3-Space and Related Problems	2
Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms	2
Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph	2
Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering	2
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing	2
Spectral Methods from Tensor Networks	2
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	2
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	2

Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?	2
Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model	2
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding	2
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs	2
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	2
Corrigendum: Metric Embedding via Shortest Path Decompositions	2
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach	1
On Matrix Multiplication and Polynomial Identity Testing	1
Contextual Search via Intrinsic Volumes	1
Agreement Tests on Graphs and Hypergraphs	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
Parallel Repetition for the GHZ Game: Exponential Decay	1
Two Variable Logic with Ultimately Periodic Counting	1
Counting Small Induced Subgraphs with Hereditary Properties	1
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings	1
Algebraic Algorithms for Fractional Linear Matroid Parity via Noncommutative Rank	1
On the Computability of Continuous Maximum Entropy Distributions with Applications	1
Counting Small Induced Subgraphs Satisfying Monotone Properties	1
Reducing Path TSP to TSP	1
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
An Improved Parameterized Algorithm for Treewidth	1
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random	1
Fitting Metrics and Ultrametrics with Minimum Disagreements	1
Classical Verification of Quantum Computations	1
The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs	1
Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming	1
Constant Depth Formula and Partial Function Versions of MCSP Are Hard	1
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise	1
Online Edge Coloring via Tree Recurrences and Correlation Decay	1
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion	1
Super-Logarithmic Lower Bounds for Dynamic Graph Problems	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
Discrepancy Minimization via a Self-Balancing Walk	1
Derandomization from Algebraic Hardness	1
A Logarithmic Lower Bound for Oblivious RAM (For All Parameters)	1
Sublinear Algorithms for Local Graph-Centrality Estimation	1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring	1
An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions	1
Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification	1
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	1
Symmetries, Graph Properties, and Quantum Speedups	1
Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu	0
Fast FPT-Approximation of Branchwidth	0
Optimal (Euclidean) Metric Compression	0
An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences	0
Polynomial Data Structure Lower Bounds in the Group Model	0
Differentially Private Learning of Geometric Concepts	0
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough	0
Rigid Matrices from Rectangular PCPs	0
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions	0
AdWords in a Panorama	0
Decidability of Membership Problems for Flat Rational Subsets of \(\boldsymbol{{\textrm{GL}}(2,\boldsymbol{{\mathbb{Q}}})}\) and Singular Matrices	0
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness	0
Lower Bounds for Regular Resolution over Parities	0
Clustering Mixtures with Almost Optimal Separation in Polynomial Time	0
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations	0
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches	0
Optimal Resizable Arrays	0
Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018)	0
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm	0
Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling	0
Flow Time Scheduling and Prefix Beck–Fiala	0
How to Trap a Gradient Flow	0
On a Combinatorial Generation Problem of Knuth	0
Geodesic Walks in Polytopes	0
Approximating Maximum Independent Set for Rectangles in the Plane	0
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue	0
Sharp Thresholds in Random Simple Temporal Graphs	0
Elastic-Degenerate String Matching via Fast Matrix Multiplication	0
Approximating Minimum Representations of Key Horn Functions	0
Computational Complexity of the Hylland–Zeckhauser Mechanism for One-Sided Matching Markets	0
Distributed Lower Bounds for Ruling Sets	0
A Framework for the Secretary Problem on the Intersection of Matroids	0
Multi-Item Nontruthful Auctions Achieve Good Revenue	0
Hop-Constrained Oblivious Routing	0
An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem	0
Exact-Size Sampling of Enriched Trees in Linear Time	0

Consensus-Halving: Does It Ever Get Easier?	0
Removing Additive Structure in 3SUM-Based Reductions	0
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing	0
Interior Point Methods Are Not Worse than Simplex	0
A Spectral Approach to Network Design	0
Smoothing the Gap Between NP and ER	0
From Contention Resolution to Matroid Secretary and Back	0
Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring	0
Reachability Preservers: New Extremal Bounds and Approximation Algorithms	0
Fast Generalized DFTs for All Finite Groups	0
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection	0
Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions	0
Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits	0
Tree-Depth and the Formula Complexity of Subgraph Isomorphism	0
Rounds vs. Communication Tradeoffs for Maximal Independent Sets	0
Counting Subgraphs in Somewhere Dense Graphs	0
Why Extension-Based Proofs Fail	0
Shortest Paths Without a Map, but with an Entropic Regularizer	0
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao	0
Proximity Search for Maximal Subgraph Enumeration	0
Weak Zero-Knowledge beyond the Black-Box Barrier	0
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs	0
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics	0
Online List Labeling: Breaking the \({\log^2 n}\) Barrier	0
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs	0
Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid	0
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich	0
A \({d}^{{1/2+{o}(1)}}\) Monotonicity Tester for Boolean Functions on \({d}\)-Dimensional Hypergrids	0
The Optimal Error Resilience of Interactive Communication over Binary Channels	0
Polynomial-Time Approximation Schemes for Facility Location on Planar Graphs	0
Almost Tight Bounds for Reordering Buffer Management	0
Lower Bounds for External Memory Integer Sorting via Network Coding	0
Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring	0
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders	0
Prophet Secretary for Combinatorial Auctions and Matroids	0
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering	0
Approximate Gomory–Hu Tree is Faster than \(\boldsymbol{n}\,\boldsymbol{-\, 1}\) Maximum Flows	0
A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines	0
An Approximate Generalization of the Okamura–Seymour Theorem	0
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	0
Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders	0
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification	0
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication	0
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games	0
FIXP-Membership via Convex Optimization: Games, Cakes, and Markets	0
A Strong Version of Cobham’s Theorem	0
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems	0
An ETH-Tight Exact Algorithm for Euclidean TSP	0
Testing Linear-Invariant Properties	0
A Parameterized Approximation Scheme for Min $k$-Cut	0
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics	0
Approximation Algorithms for LCS and LIS with Truly Improved Running Times	0
Anchored Parallel Repetition for Nonlocal Games	0
Special Section on the Forty-Ninth Annual ACM Symposium on the Theory of Computing (STOC 2017)	0
ABE for Circuits with poly\( {(\lambda )}\)-Sized Keys from LWE	0
Optimal Algorithms for Geometric Centers and Depth	0
Complexity Classification Transfer for CSPs via Algebraic Products	0
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes	0
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems	0
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization	0
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity	0
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side	0
Differentially Private Sampling from Distributions	0
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics	0
Almost Optimal SuperConstant-Pass Streaming Lower Bounds for Reachability	0
Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier	0
Internal Pattern Matching Queries in a Text and Applications	0
Uniform Restricted Chase Termination	0
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs	0
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture	0
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction	0
Unambiguous DNFs and Alon–Saks–Seymour	0
CLAP: A New Algorithm for Promise CSPs	0
A Local Search Framework for Experimental Design	0
Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time	0
The Power of Two Choices in Graphical Allocation	0
Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions	0
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All \({\ell_{{p}}}\) Norms	0
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020)	0
Average Sensitivity of Graph Algorithms	0
Special Section on the Fifty-First Annual ACM Sympositum on the Theory of Computing (STOC 2019)	0
Low-Density Parity-Check Codes Achieve List-Decoding Capacity	0
Economical Convex Coverings and Applications	0
Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs	0
Topology and Adjunction in Promise Constraint Satisfaction	0
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity	0
Efficient Construction of Rigid Matrices Using an NP Oracle	0
A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane	0
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem	0
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing	0
Packing Cycles in Planar and Bounded-Genus Graphs	0
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover	0
Traversing Combinatorial 0/1-Polytopes via Optimization	0
The Minimum Formula Size Problem is (ETH) Hard	0
The Shortest Even Cycle Problem Is Tractable	0