SIAM Journal on Computing

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

Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	4
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	4
Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius	4
On the Complexity of Equilibrium Computation in First-Price Auctions	4
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	4
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes	4
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)	4
Nearly Optimal Static Las Vegas Succinct Dictionary	4
Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\)	4
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	4
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer	3
Almost-Optimal Sublinear Additive Spanners	3
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	3
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	3
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	3
Semidefinite Programming and Linear Equations vs. Homomorphism Problems	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
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More	3
Caching with Time Windows and Delays	3
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	3
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	3
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria	3
Balanced Allocation: Patience Is Not a Virtue	3
PTAS for Minimum Cost MultiCovering with Disks	3
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	3
Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms	2
Want to Gather? No Need to Chatter!	2
Satisfiability in MultiValued Circuits	2
A Short List of Equalities Induces Large Sign-Rank	2
Spectral Methods from Tensor Networks	2
Isomorphism Testing for Graphs Excluding Small Minors	2
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	2
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	2
Fast Metric Embedding into the Hamming Cube	2
Truly Optimal Euclidean Spanners	2
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs	2
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019)	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
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2
Online Edge Coloring Is (Nearly) as Easy as Offline	2
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for \(\textsf{ACC}\) Circuits	2
Deterministic Massively Parallel Connectivity	2
Constant Inapproximability for PPA	2
Approximate Graph Coloring and the Crystal with a Hollow Shadow	2
Corrigendum: Metric Embedding via Shortest Path Decompositions	2
Erratum: A Full Dichotomy for \(\textsf{Holant}^\mathbf{c}\), Inspired by Quantum Computation	2
Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph	2

On Ray Shooting for Triangles in 3-Space and Related Problems	2
Tracing Isomanifolds in \(\mathbb{R}\) d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	2
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs	2
Sorting Short Keys in Circuits of Size ${o(n \log n)}$	2
Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?	2
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	2
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	2
Faster Isomorphism for \({p}\)-Groups of Class 2 and Exponent \({p}\)	1
Discrepancy Minimization via a Self-Balancing Walk	1
On the Computability of Continuous Maximum Entropy Distributions with Applications	1
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding	1
A Logarithmic Lower Bound for Oblivious RAM (For All Parameters)	1
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings	1
Agreement Tests on Graphs and Hypergraphs	1
Derandomization from Algebraic Hardness	1
Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming	1
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise	1
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion	1
On the Nisan–Ronen Conjecture for Submodular Valuations	1
Constant Depth Formula and Partial Function Versions of MCSP Are Hard	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
On CDCL-Based Proof Systems with the Ordered Decision Strategy	1
Counting Small Induced Subgraphs with Hereditary Properties	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
Parallel Repetition for the GHZ Game: Exponential Decay	1
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach	1
Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model	1
Sublinear Algorithms for Local Graph-Centrality Estimation	1
Classical Verification of Quantum Computations	1
Symmetries, Graph Properties, and Quantum Speedups	1
Online Edge Coloring via Tree Recurrences and Correlation Decay	1
Algebraic Algorithms for Fractional Linear Matroid Parity via Noncommutative Rank	1
On Matrix Multiplication and Polynomial Identity Testing	1
Contextual Search via Intrinsic Volumes	1
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	1
An Improved Parameterized Algorithm for Treewidth	1
The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs	1
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random	1
Fitting Metrics and Ultrametrics with Minimum Disagreements	1
Proof Complexity and the Binary Encoding of Combinatorial Principles	1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring	1
Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification	1
Counting Small Induced Subgraphs Satisfying Monotone Properties	1
Super-Logarithmic Lower Bounds for Dynamic Graph Problems	1
An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions	1
Two Variable Logic with Ultimately Periodic Counting	1
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering	0
Sharp Thresholds in Random Simple Temporal Graphs	0
Differentially Private Sampling from Distributions	0
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches	0
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics	0
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs	0
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs	0
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich	0
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture	0
Proximity Search for Maximal Subgraph Enumeration	0
The Optimal Error Resilience of Interactive Communication over Binary Channels	0
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue	0
A Direct Product Theorem for Quantum Communication Complexity with Applications to Device-Independent Cryptography	0
Unambiguous DNFs and Alon–Saks–Seymour	0
Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring	0
Computational Complexity of the Hylland–Zeckhauser Mechanism for One-Sided Matching Markets	0
Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions	0
Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions	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
Topology and Adjunction in Promise Constraint Satisfaction	0
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	0
Multi-Item Nontruthful Auctions Achieve Good Revenue	0
Reducing Path TSP to TSP	0
Hop-Constrained Oblivious Routing	0
Lower Bounds for Regular Resolution over Parities	0
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics	0
The Shortest Even Cycle Problem Is Tractable	0
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing	0
Smoothing the Gap Between NP and ER	0
An ETH-Tight Exact Algorithm for Euclidean TSP	0
A Nearly Quadratic-Time FPTAS for Knapsack	0
Polynomial Data Structure Lower Bounds in the Group Model	0

Traversing Combinatorial 0/1-Polytopes via Optimization	0
Consensus-Halving: Does It Ever Get Easier?	0
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication	0
Packing Cycles in Planar and Bounded-Genus Graphs	0
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions	0
A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane	0
Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018)	0
Decidability of Membership Problems for Flat Rational Subsets of \(\boldsymbol{{\textrm{GL}}(2,\boldsymbol{{\mathbb{Q}}})}\) and Singular Matrices	0
On a Combinatorial Generation Problem of Knuth	0
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao	0
Polynomial-Time Approximation Schemes for Facility Location on Planar Graphs	0
Weak Zero-Knowledge beyond the Black-Box Barrier	0
Almost Tight Bounds for Reordering Buffer Management	0
Why Extension-Based Proofs Fail	0
Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling	0
Distributed Lower Bounds for Ruling Sets	0
Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier	0
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations	0
Optimal Resizable Arrays	0
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction	0
A \({d}^{{1/2+{o}(1)}}\) Monotonicity Tester for Boolean Functions on \({d}\)-Dimensional Hypergrids	0
The Power of Two Choices in Graphical Allocation	0
A Local Search Framework for Experimental Design	0
Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu	0
CLAP: A New Algorithm for Promise CSPs	0
An Approximate Generalization of the Okamura–Seymour Theorem	0
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All \({\ell_{{p}}}\) Norms	0
Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders	0
Elastic-Degenerate String Matching via Fast Matrix Multiplication	0
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems	0
Fast Generalized DFTs for All Finite Groups	0
Low-Density Parity-Check Codes Achieve List-Decoding Capacity	0
Exact-Size Sampling of Enriched Trees in Linear Time	0
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity	0
A Strong Version of Cobham’s Theorem	0
A Spectral Approach to Network Design	0
Optimal Algorithms for Geometric Centers and Depth	0
Anchored Parallel Repetition for Nonlocal Games	0
Fast FPT-Approximation of Branchwidth	0
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing	0
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems	0
A Parameterized Approximation Scheme for Min $k$-Cut	0
Interior Point Methods Are Not Worse than Simplex	0
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection	0
Tree-Depth and the Formula Complexity of Subgraph Isomorphism	0
Optimal (Euclidean) Metric Compression	0
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders	0
An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem	0
Rounds vs. Communication Tradeoffs for Maximal Independent Sets	0
Clustering Mixtures with Almost Optimal Separation in Polynomial Time	0
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough	0
Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid	0
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization	0
Average Sensitivity of Graph Algorithms	0
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity	0
Almost Optimal SuperConstant-Pass Streaming Lower Bounds for Reachability	0
Uniform Restricted Chase Termination	0
Special Section on the Fifty-First Annual ACM Sympositum on the Theory of Computing (STOC 2019)	0
Online List Labeling: Breaking the \({\log^2 n}\) Barrier	0
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm	0
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs	0
AdWords in a Panorama	0
Flow Time Scheduling and Prefix Beck–Fiala	0
Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time	0
Geodesic Walks in Polytopes	0
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics	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
Lower Bounds for External Memory Integer Sorting via Network Coding	0
Prophet Secretary for Combinatorial Auctions and Matroids	0
Approximating Minimum Representations of Key Horn Functions	0
Efficient Construction of Rigid Matrices Using an NP Oracle	0
Shortest Paths Without a Map, but with an Entropic Regularizer	0
Economical Convex Coverings and Applications	0
A Framework for the Secretary Problem on the Intersection of Matroids	0
Removing Additive Structure in 3SUM-Based Reductions	0
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games	0
From Contention Resolution to Matroid Secretary and Back	0
Testing Linear-Invariant Properties	0
Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring	0
Internal Pattern Matching Queries in a Text and Applications	0
The Minimum Formula Size Problem is (ETH) Hard	0
Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs	0
Special Section on the Forty-Ninth Annual ACM Symposium on the Theory of Computing (STOC 2017)	0
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification	0
Differentially Private Learning of Geometric Concepts	0
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem	0
ABE for Circuits with poly\( {(\lambda )}\)-Sized Keys from LWE	0
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes	0
Locally Consistent Parsing for Text Indexing in Small Space	0
FIXP-Membership via Convex Optimization: Games, Cakes, and Markets	0
Reachability Preservers: New Extremal Bounds and Approximation Algorithms	0
Approximation Algorithms for LCS and LIS with Truly Improved Running Times	0
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness	0
How to Trap a Gradient Flow	0