SIAM Journal on Computing

Article	Citations
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths	20
Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier	17
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion	16
Flow-Augmentation III: Complexity Dichotomy for Boolean CSPs Parameterized by the Number of Unsatisfied Constraints	14
Testing Graph Properties with the Container Method	12
Induced Subgraphs of Bounded Treewidth and the Container Method	11
Tight Revenue Gaps among Multiunit Mechanisms	10
Competitively Chasing Convex Bodies	10
Minimum Cuts in Surface Graphs	9
A Single-Exponential Time 2-Approximation Algorithm for Treewidth	9
Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number	9
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments	9
Revisionist Simulations: A New Approach to Proving Space Lower Bounds	9
Circuits Resilient to Short-Circuit Errors	8
Dynamic Geometric Set Cover, Revisited	8
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification	8
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem	8
Parameterized Complexity of Untangling Knots	7
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance	6
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)	5
Separating MAX 2-AND, MAX DI-CUT, and MAX CUT	5
Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius	5
Toward Derandomizing Markov Chain Monte Carlo	5
On the Complexity of Equilibrium Computation in First-Price Auctions	5
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes	5

On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization	5
One-Way Functions and (Im)perfect Obfuscation	5
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	5
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	5
The Approximate Degree of DNF and CNF Formulas	5
An Improved Upper Bound for the Universal TSP on the Grid	5
Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\)	5
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	4
Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time	4
Ghost Value Augmentation for \({k}\)-Edge-Connectivity	4
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	4
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions	4
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	3
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	3
Balanced Allocation: Patience Is Not a Virtue	3
Quantum Eigenvalue Processing	3
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for \(\textsf{ACC}\) Circuits	3
Improved Optimal Testing Results from Global Hypercontractivity	3
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	3
Caching with Time Windows and Delays	3
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination	3
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More	3
Almost-Optimal Sublinear Additive Spanners	3
Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians	3
Doubly Efficient Private Information Retrieval and Fully Homomorphic Ram Computation from Ring LWE	3
PTAS for Minimum Cost MultiCovering with Disks	3
Approximate Graph Coloring and the Crystal with a Hollow Shadow	2
Corrigendum: Metric Embedding via Shortest Path Decompositions	2
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019)	2
Erratum: A Full Dichotomy for \(\textsf{Holant}^\mathbf{c}\), Inspired by Quantum Computation	2
Tracing Isomanifolds in \(\mathbb{R}\) d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	2
Deterministic Massively Parallel Connectivity	2
On Ray Shooting for Triangles in 3-Space and Related Problems	2
Online Edge Coloring Is (Nearly) as Easy as Offline	2
Semidefinite Programming and Linear Equations vs. Homomorphism Problems	2
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2
Quantum Speedups for Linear Programming via Interior Point Methods	2
Space Complexity of Vertex Connectivity Oracles	2
Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph	2
Fast Metric Embedding into the Hamming Cube	2
Quantum Time-Space Tradeoffs for Matrix Problems	2
\(\boldsymbol{\Pi_2^P}\) vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem	2
Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?	2
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	2
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	2
Laplace Transform–Based Quantum Eigenvalue Transformation via Linear Combination of Hamiltonian Simulation	2
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	2
Relaxed Local Correctability from Local Testing	2
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs	2
Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms	2

Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	2
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited	2
Exact Algorithms and Lower Bounds for Stable Instances of Euclidean \(\boldsymbol{k}\)- means	2
A Short List of Equalities Induces Large Sign-Rank	2
Isomorphism Testing for Graphs Excluding Small Minors	2
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	2
Spectral Methods from Tensor Networks	2
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing	2
Online Edge Coloring via Tree Recurrences and Correlation Decay	1
The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds	1
Classical Verification of Quantum Computations	1
Cheeger’s Inequalities for Vertex Expansion and Reweighted Eigenvalues	1
Special Section on the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (2020)	1
On the Computability of Continuous Maximum Entropy Distributions with Applications	1
An Improved Parameterized Algorithm for Treewidth	1
Sublinear Algorithms for Local Graph-Centrality Estimation	1
Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares	1
Parallel Repetition for the GHZ Game: Exponential Decay	1
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding	1
Want to Gather? No Need to Chatter!	1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring	1
Contextual Search via Intrinsic Volumes	1
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach	1
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings	1
Gapped Clique Homology on Weighted Graphs Is \({\text{QMA}_1}\)-Hard and Contained in QMA	1
On CDCL-Based Proof Systems with the Ordered Decision Strategy	1
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	1
Discrepancy Minimization via a Self-Balancing Walk	1
On Matrix Multiplication and Polynomial Identity Testing	1
Counting Small Induced Subgraphs with Hereditary Properties	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	1
Fitting Metrics and Ultrametrics with Minimum Disagreements	1
Constant Inapproximability for PPA	1
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random	1
Reducing Tarski to Unique Tarski (In the Black-Box Model)	1
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion	1
Super-Logarithmic Lower Bounds for Dynamic Graph Problems	1
The Minimal Faithful Permutation Degree of Groups Without Abelian Normal Subgroups	1
Order-Competitive Ratio	1
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence	1
On the Nisan–Ronen Conjecture for Submodular Valuations	1
Two Variable Logic with Ultimately Periodic Counting	1
Constant Depth Formula and Partial Function Versions of MCSP Are Hard	1
Proof Complexity and the Binary Encoding of Combinatorial Principles	1
An FPT Algorithm for the Embeddability of Graphs Into Two-Dimensional Simplicial Complexes	1
A Logarithmic Lower Bound for Oblivious RAM (For All Parameters)	1
Agreement Tests on Graphs and Hypergraphs	1
A Unified Framework of Light Spanners I: Fast (Yet Optimal) Constructions	1
Constant-Depth Arithmetic Circuits for Linear Algebra Problems	1
Faster Isomorphism for \({p}\)-Groups of Class 2 and Exponent \({p}\)	1
Almost Optimal SuperConstant-Pass Streaming Lower Bounds for Reachability	0
Linear Independence, Alternants and Applications	0
Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs	0
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing	0
Tree Evaluation is in Space \({O}\)\({(\log n \cdot \log \log n)}\)	0
A Nearly Quadratic-Time FPTAS for Knapsack	0
An Approximate Generalization of the Okamura–Seymour Theorem	0
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs	0
Flow Time Scheduling and Prefix Beck–Fiala	0
Removing Additive Structure in 3SUM-Based Reductions	0
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems	0
Interior Point Methods Are Not Worse than Simplex	0
Algebraic Algorithms for Fractional Linear Matroid Parity via Noncommutative Rank	0
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders	0
Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring	0
FIXP-Membership via Convex Optimization: Games, Cakes, and Markets	0
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection	0
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing	0
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm	0
AdWords in a Panorama	0
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles	0
Testing Linear-Invariant Properties	0
One-Way Functions and Zero Knowledge	0
Counting Subgraphs in Somewhere Dense Graphs	0
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes	0
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue	0
Toward Better Depth Lower Bounds: A KRW-like Theorem For Strong Composition	0
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity	0
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020)	0

Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction	0
Sharp Thresholds in Random Simple Temporal Graphs	0
Complexity Classification Transfer for CSPs via Algebraic Products	0
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All \({\ell_{{p}}}\) Norms	0
A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines	0
Faster Isomorphism Testing of p -Groups of Frattini Class 2	0
Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits	0
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	0
Competitive Analysis with a Sample and the Secretary Problem	0
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough	0
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering	0
Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier	0
A Strong Version of Cobham’s Theorem	0
Hop-Constrained Oblivious Routing	0
A \({d}^{{1/2+{o}(1)}}\) Monotonicity Tester for Boolean Functions on \({d}\)-Dimensional Hypergrids	0
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture	0
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover	0
Economical Convex Coverings and Applications	0
Approximating Maximum Independent Set for Rectangles in the Plane	0
From Contention Resolution to Matroid Secretary and Back	0
Combinatorial Contracts	0
Online List Labeling: Breaking the \({\log^2 n}\) Barrier	0
Tree-Depth and the Formula Complexity of Subgraph Isomorphism	0
Packing Cycles in Planar and Bounded-Genus Graphs	0
CLAP: A New Algorithm for Promise CSPs	0
The Power of Two Choices in Graphical Allocation	0
A Framework for the Secretary Problem on the Intersection of Matroids	0
Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification	0
Special Section on The Sixty-Third Annual IEEE Symposium on Foundations of Computer Science (2022)	0
A Subquadratic Upper Bound on Hurwitz’s Problem and Related Noncommutative Polynomials	0
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem	0
A Spectral Approach to Network Design	0
The Power of Proportional Fairness for Nonclairvoyant Polytope Scheduling	0
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics	0
An ETH-Tight Exact Algorithm for Euclidean TSP	0
Symmetries, Graph Properties, and Quantum Speedups	0
Uniform Restricted Chase Termination	0
The Minimum Formula Size Problem is (ETH) Hard	0
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions	0
Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018)	0
Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension	0
Why Extension-Based Proofs Fail	0
ABE for Circuits with poly\( {(\lambda )}\)-Sized Keys from LWE	0
Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid	0
Average Sensitivity of Graph Algorithms	0
\({\mathcal{O}}\)\({(\log\,\log\,{{n}})}\) Passes Are Optimal for Semistreaming Maximal Independent Set	0
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness	0
Computational Complexity of the Hylland–Zeckhauser Mechanism for One-Sided Matching Markets	0
Proximity Search for Maximal Subgraph Enumeration	0
Lower Bounds for Regular Resolution over Parities	0
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs	0
Efficient Two-Sided Markets with Limited Information	0
Approximation Algorithms for LCS and LIS with Truly Improved Running Times	0
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches	0
Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the \(\boldsymbol{\sqrt {n}}\) Dimension Threshold	0
Fast FPT-Approximation of Branchwidth	0
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification	0
A Direct Product Theorem for Quantum Communication Complexity with Applications to Device-Independent Cryptography	0
Optimal Resizable Arrays	0
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics	0
Traversing Combinatorial 0/1-Polytopes via Optimization	0
The Optimal Error Resilience of Interactive Communication over Binary Channels	0
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics	0
Locally Consistent Parsing for Text Indexing in Small Space	0
Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling	0
Topology and Adjunction in Promise Constraint Satisfaction	0
Rounds vs. Communication Tradeoffs for Maximal Independent Sets	0
A Local Search Framework for Experimental Design	0
Differentially Private Learning of Geometric Concepts	0
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity	0
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise	0
Internal Pattern Matching Queries in a Text and Applications	0
Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu	0
Differentially Private Sampling from Distributions	0
The Shortest Even Cycle Problem Is Tractable	0
Unambiguous DNFs and Alon–Saks–Seymour	0
Rigid Matrices from Rectangular PCPs	0
Quantum Lower Bounds by Sample-to-Query Lifting	0
How to Trap a Gradient Flow	0
Reachability Preservers: New Extremal Bounds and Approximation Algorithms	0
Clustering Mixtures with Almost Optimal Separation in Polynomial Time	0
Polynomial-Time Approximation Schemes for Facility Location on Planar Graphs	0
Prophet Secretary for Combinatorial Auctions and Matroids	0
Approximate Gomory–Hu Tree is Faster than \(\boldsymbol{n}\,\boldsymbol{-\, 1}\) Maximum Flows	0
Fast Generalized DFTs for All Finite Groups	0
Consensus-Halving: Does It Ever Get Easier?	0
Reverse Mathematics of Complexity Lower Bounds	0
Edge-Disjoint Paths in Expanders: Online with Removals	0
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao	0
Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders	0
A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane	0
Shortest Paths Without a Map, but with an Entropic Regularizer	0
Special Section on the Fifty-First Annual ACM Sympositum on the Theory of Computing (STOC 2019)	0
Multi-Item Nontruthful Auctions Achieve Good Revenue	0
Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring	0