SIAM Journal on Computing

Article	Citations
Tight Revenue Gaps among Multiunit Mechanisms	17
Induced Subgraphs of Bounded Treewidth and the Container Method	13
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths	11
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
Metric Embedding via Shortest Path Decompositions	10
Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number	10
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments	9
Minimum Cuts in Surface Graphs	9
Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time	8
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
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
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes	6
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
An Improved Upper Bound for the Universal TSP on the Grid	5
Parameterized Complexity of Untangling Knots	5
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance	5
One-Way Functions and (Im)perfect Obfuscation	5
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
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
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
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
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
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
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
Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification	1
Symmetries, Graph Properties, and Quantum Speedups	1
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach	1
On Matrix Multiplication and Polynomial Identity Testing	1
An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions	1
Contextual Search via Intrinsic Volumes	1
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	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
Algebraic Algorithms for Fractional Linear Matroid Parity via Noncommutative Rank	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
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings	1
Proof Complexity and the Binary Encoding of Combinatorial Principles	1
On the Computability of Continuous Maximum Entropy Distributions with Applications	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
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
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
The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs	1
Special Section on the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (2020)	1
Constant Depth Formula and Partial Function Versions of MCSP Are Hard	1
Discrepancy Minimization via a Self-Balancing Walk	1
Online Edge Coloring via Tree Recurrences and Correlation Decay	1
Unambiguous DNFs and Alon–Saks–Seymour	0
A Framework for the Secretary Problem on the Intersection of Matroids	0
An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem	0
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction	0
Exact-Size Sampling of Enriched Trees in Linear Time	0
Consensus-Halving: Does It Ever Get Easier?	0
Interior Point Methods Are Not Worse than Simplex	0
Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time	0
A Spectral Approach to Network Design	0
The Power of Two Choices in Graphical Allocation	0
Reachability Preservers: New Extremal Bounds and Approximation Algorithms	0
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020)	0
Fast Generalized DFTs for All Finite Groups	0
Average Sensitivity of Graph Algorithms	0
Smoothing the Gap Between NP and ER	0
Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits	0
Low-Density Parity-Check Codes Achieve List-Decoding Capacity	0
Tree-Depth and the Formula Complexity of Subgraph Isomorphism	0
Economical Convex Coverings and Applications	0
Counting Subgraphs in Somewhere Dense Graphs	0
Efficient Construction of Rigid Matrices Using an NP Oracle	0
Why Extension-Based Proofs Fail	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
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover	0
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao	0
Traversing Combinatorial 0/1-Polytopes via Optimization	0
Weak Zero-Knowledge beyond the Black-Box Barrier	0
Fast FPT-Approximation of Branchwidth	0
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs	0
Optimal (Euclidean) Metric Compression	0
Online List Labeling: Breaking the \({\log^2 n}\) Barrier	0
Differentially Private Learning of Geometric Concepts	0
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs	0
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough	0
AdWords in a Panorama	0

The Optimal Error Resilience of Interactive Communication over Binary Channels	0
A \({d}^{{1/2+{o}(1)}}\) Monotonicity Tester for Boolean Functions on \({d}\)-Dimensional Hypergrids	0
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations	0
Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring	0
Lower Bounds for External Memory Integer Sorting via Network Coding	0
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm	0
Approximate Gomory–Hu Tree is Faster than \(\boldsymbol{n}\,\boldsymbol{-\, 1}\) Maximum Flows	0
Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018)	0
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering	0
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	0
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication	0
How to Trap a Gradient Flow	0
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games	0
On a Combinatorial Generation Problem of Knuth	0
FIXP-Membership via Convex Optimization: Games, Cakes, and Markets	0
An ETH-Tight Exact Algorithm for Euclidean TSP	0
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue	0
Testing Linear-Invariant Properties	0
Sharp Thresholds in Random Simple Temporal Graphs	0
Anchored Parallel Repetition for Nonlocal Games	0
Computational Complexity of the Hylland–Zeckhauser Mechanism for One-Sided Matching Markets	0
Special Section on the Forty-Ninth Annual ACM Symposium on the Theory of Computing (STOC 2017)	0
Distributed Lower Bounds for Ruling Sets	0
A Parameterized Approximation Scheme for Min $k$-Cut	0
Complexity Classification Transfer for CSPs via Algebraic Products	0
Multi-Item Nontruthful Auctions Achieve Good Revenue	0
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes	0
Hop-Constrained Oblivious Routing	0
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization	0
Removing Additive Structure in 3SUM-Based Reductions	0
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity	0
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing	0
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side	0
From Contention Resolution to Matroid Secretary and Back	0
Differentially Private Sampling from Distributions	0
Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring	0
Almost Optimal SuperConstant-Pass Streaming Lower Bounds for Reachability	0
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection	0
Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier	0
Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions	0
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs	0
Rounds vs. Communication Tradeoffs for Maximal Independent Sets	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
A Local Search Framework for Experimental Design	0
CLAP: A New Algorithm for Promise CSPs	0
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics	0
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All \({\ell_{{p}}}\) Norms	0
Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions	0
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich	0
Special Section on the Fifty-First Annual ACM Sympositum on the Theory of Computing (STOC 2019)	0
Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs	0
Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid	0
Topology and Adjunction in Promise Constraint Satisfaction	0
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity	0
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem	0
Polynomial-Time Approximation Schemes for Facility Location on Planar Graphs	0
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing	0
Almost Tight Bounds for Reordering Buffer Management	0
The Minimum Formula Size Problem is (ETH) Hard	0
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders	0
The Shortest Even Cycle Problem Is Tractable	0
Prophet Secretary for Combinatorial Auctions and Matroids	0
Packing Cycles in Planar and Bounded-Genus Graphs	0
An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences	0
A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines	0
Polynomial Data Structure Lower Bounds in the Group Model	0
An Approximate Generalization of the Okamura–Seymour Theorem	0
Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu	0
Rigid Matrices from Rectangular PCPs	0
Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders	0
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions	0
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification	0
Decidability of Membership Problems for Flat Rational Subsets of \(\boldsymbol{{\textrm{GL}}(2,\boldsymbol{{\mathbb{Q}}})}\) and Singular Matrices	0
A Strong Version of Cobham’s Theorem	0
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness	0
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems	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
Clustering Mixtures with Almost Optimal Separation in Polynomial Time	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
ABE for Circuits with poly\( {(\lambda )}\)-Sized Keys from LWE	0
Optimal Resizable Arrays	0
Optimal Algorithms for Geometric Centers and Depth	0
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems	0
Flow Time Scheduling and Prefix Beck–Fiala	0
Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling	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
Geodesic Walks in Polytopes	0
Uniform Restricted Chase Termination	0
Approximating Minimum Representations of Key Horn Functions	0
Internal Pattern Matching Queries in a Text and Applications	0
Elastic-Degenerate String Matching via Fast Matrix Multiplication	0