SIAM Journal on Computing

Article	Citations
Tight Revenue Gaps among Multiunit Mechanisms	20
Induced Subgraphs of Bounded Treewidth and the Container Method	15
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths	14
Flow-Augmentation III: Complexity Dichotomy for Boolean CSPs Parameterized by the Number of Unsatisfied Constraints	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	10
Metric Embedding via Shortest Path Decompositions	10
Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time	9
Revisionist Simulations: A New Approach to Proving Space Lower Bounds	8
A Single-Exponential Time 2-Approximation Algorithm for Treewidth	8
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem	8
Competitively Chasing Convex Bodies	8
Minimum Cuts in Surface Graphs	8
Dynamic Geometric Set Cover, Revisited	7
Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number	7
The Approximate Degree of DNF and CNF Formulas	7
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments	7
Parameterized Complexity of Untangling Knots	6
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification	6
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance	6
Circuits Resilient to Short-Circuit Errors	6
On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization	5
An Improved Upper Bound for the Universal TSP on the Grid	5
Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius	5
One-Way Functions and (Im)perfect Obfuscation	5

Toward Derandomizing Markov Chain Monte Carlo	5
Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\)	5
On the Complexity of Equilibrium Computation in First-Price Auctions	4
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	4
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions	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
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	4
Nearly Optimal Static Las Vegas Succinct Dictionary	4
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	4
Ghost Value Augmentation for \({k}\)-Edge-Connectivity	4
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	4
Improved Optimal Testing Results from Global Hypercontractivity	4
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	3
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	3
PTAS for Minimum Cost MultiCovering with Disks	3
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for \(\textsf{ACC}\) Circuits	3
Caching with Time Windows and Delays	3
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer	3
A Tight Analysis of Bethe Approximation for Permanent	3
Almost-Optimal Sublinear Additive Spanners	3
Balanced Allocation: Patience Is Not a Virtue	3
Semidefinite Programming and Linear Equations vs. Homomorphism Problems	3
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	3
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	3
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria	3
Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians	3
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More	3
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	3
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	3
Sorting Short Keys in Circuits of Size ${o(n \log n)}$	3
Truly Optimal Euclidean Spanners	2
A Short List of Equalities Induces Large Sign-Rank	2
Spectral Methods from Tensor Networks	2
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs	2
Fast Metric Embedding into the Hamming Cube	2
Corrigendum: Metric Embedding via Shortest Path Decompositions	2
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	2
Relaxed Local Correctability from Local Testing	2
Constant Inapproximability for PPA	2
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019)	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
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	2
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing	2
Erratum: A Full Dichotomy for \(\textsf{Holant}^\mathbf{c}\), Inspired by Quantum Computation	2
Satisfiability in MultiValued Circuits	2
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs	2

Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph	2
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	2
Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?	2
Tracing Isomanifolds in \(\mathbb{R}\) d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	2
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2
Isomorphism Testing for Graphs Excluding Small Minors	2
Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering	2
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding	2
Want to Gather? No Need to Chatter!	2
Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms	2
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited	2
Approximate Graph Coloring and the Crystal with a Hollow Shadow	2
Agreement Tests on Graphs and Hypergraphs	1
Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming	1
Counting Small Induced Subgraphs with Hereditary Properties	1
A Spectral Approach to Network Design	1
Symmetries, Graph Properties, and Quantum Speedups	1
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion	1
Sublinear Algorithms for Local Graph-Centrality Estimation	1
Online Edge Coloring via Tree Recurrences and Correlation Decay	1
On Matrix Multiplication and Polynomial Identity Testing	1
Classical Verification of Quantum Computations	1
Contextual Search via Intrinsic Volumes	1
A Logarithmic Lower Bound for Oblivious RAM (For All Parameters)	1
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring	1
Fitting Metrics and Ultrametrics with Minimum Disagreements	1
Constant Depth Formula and Partial Function Versions of MCSP Are Hard	1
Derandomization from Algebraic Hardness	1
Quantum Lower Bounds by Sample-to-Query Lifting	1
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing	1
Counting Small Induced Subgraphs Satisfying Monotone Properties	1
Testing Linear-Invariant Properties	1
On CDCL-Based Proof Systems with the Ordered Decision Strategy	1
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach	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
An Improved Parameterized Algorithm for Treewidth	1
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random	1
Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model	1
The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds	1
Two Variable Logic with Ultimately Periodic Counting	1
On the Computability of Continuous Maximum Entropy Distributions with Applications	1
The Shortest Even Cycle Problem Is Tractable	1
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise	1
Algebraic Algorithms for Fractional Linear Matroid Parity via Noncommutative Rank	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
On the Nisan–Ronen Conjecture for Submodular Valuations	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
An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
Parallel Repetition for the GHZ Game: Exponential Decay	1
Why Extension-Based Proofs Fail	0
Unambiguous DNFs and Alon–Saks–Seymour	0
Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018)	0
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs	0
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems	0
Internal Pattern Matching Queries in a Text and Applications	0
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem	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
Differentially Private Learning of Geometric Concepts	0
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches	0
Fast FPT-Approximation of Branchwidth	0
Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier	0
Hop-Constrained Oblivious Routing	0
ABE for Circuits with poly\( {(\lambda )}\)-Sized Keys from LWE	0
Almost Optimal SuperConstant-Pass Streaming Lower Bounds for Reachability	0
A Nearly Quadratic-Time FPTAS for Knapsack	0
Tree Evaluation is in Space \({O}\)\({(\log n \cdot \log \log n)}\)	0
Computational Complexity of the Hylland–Zeckhauser Mechanism for One-Sided Matching Markets	0
A Direct Product Theorem for Quantum Communication Complexity with Applications to Device-Independent Cryptography	0
A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines	0
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All \({\ell_{{p}}}\) Norms	0
Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions	0
CLAP: A New Algorithm for Promise CSPs	0
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders	0

A Local Search Framework for Experimental Design	0
Topology and Adjunction in Promise Constraint Satisfaction	0
On a Combinatorial Generation Problem of Knuth	0
Approximating Minimum Representations of Key Horn Functions	0
An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem	0
Almost Tight Bounds for Reordering Buffer Management	0
Optimal Resizable Arrays	0
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes	0
Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu	0
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection	0
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	0
AdWords in a Panorama	0
Rounds vs. Communication Tradeoffs for Maximal Independent Sets	0
Clustering Mixtures with Almost Optimal Separation in Polynomial Time	0
Uniform Restricted Chase Termination	0
Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time	0
Fast Generalized DFTs for All Finite Groups	0
Optimal Algorithms for Geometric Centers and Depth	0
Smoothing the Gap Between NP and ER	0
Efficient Construction of Rigid Matrices Using an NP Oracle	0
Special Section on the Fifty-First Annual ACM Sympositum on the Theory of Computing (STOC 2019)	0
Economical Convex Coverings and Applications	0
FIXP-Membership via Convex Optimization: Games, Cakes, and Markets	0
Shortest Paths Without a Map, but with an Entropic Regularizer	0
A Strong Version of Cobham’s Theorem	0
Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring	0
Special Section on The Sixty-Third Annual IEEE Symposium on Foundations of Computer Science (2022)	0
Weak Zero-Knowledge beyond the Black-Box Barrier	0
Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs	0
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs	0
Multi-Item Nontruthful Auctions Achieve Good Revenue	0
A \({d}^{{1/2+{o}(1)}}\) Monotonicity Tester for Boolean Functions on \({d}\)-Dimensional Hypergrids	0
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover	0
Approximating Maximum Independent Set for Rectangles in the Plane	0
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems	0
Geodesic Walks in Polytopes	0
Packing Cycles in Planar and Bounded-Genus Graphs	0
The Optimal Error Resilience of Interactive Communication over Binary Channels	0
An Approximate Generalization of the Okamura–Seymour Theorem	0
Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions	0
Average Sensitivity of Graph Algorithms	0
Approximate Gomory–Hu Tree is Faster than \(\boldsymbol{n}\,\boldsymbol{-\, 1}\) Maximum Flows	0
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side	0
Distributed Lower Bounds for Ruling Sets	0
Differentially Private Sampling from Distributions	0
Decidability of Membership Problems for Flat Rational Subsets of \(\boldsymbol{{\textrm{GL}}(2,\boldsymbol{{\mathbb{Q}}})}\) and Singular Matrices	0
A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane	0
A Framework for the Secretary Problem on the Intersection of Matroids	0
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions	0
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics	0
Polynomial-Time Approximation Schemes for Facility Location on Planar Graphs	0
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness	0
Proximity Search for Maximal Subgraph Enumeration	0
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue	0
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity	0
Locally Consistent Parsing for Text Indexing in Small Space	0
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020)	0
Tree-Depth and the Formula Complexity of Subgraph Isomorphism	0
Optimal (Euclidean) Metric Compression	0
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm	0
Low-Density Parity-Check Codes Achieve List-Decoding Capacity	0
Approximation Algorithms for LCS and LIS with Truly Improved Running Times	0
A Parameterized Approximation Scheme for Min $k$-Cut	0
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering	0
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics	0
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication	0
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing	0
Consensus-Halving: Does It Ever Get Easier?	0
Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling	0
From Contention Resolution to Matroid Secretary and Back	0
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture	0
Removing Additive Structure in 3SUM-Based Reductions	0
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs	0
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity	0
Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring	0
Traversing Combinatorial 0/1-Polytopes via Optimization	0
Online List Labeling: Breaking the \({\log^2 n}\) Barrier	0
Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid	0
Flow Time Scheduling and Prefix Beck–Fiala	0
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough	0
Elastic-Degenerate String Matching via Fast Matrix Multiplication	0
Prophet Secretary for Combinatorial Auctions and Matroids	0
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games	0
The Power of Two Choices in Graphical Allocation	0
Sharp Thresholds in Random Simple Temporal Graphs	0
Exact-Size Sampling of Enriched Trees in Linear Time	0
Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification	0
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich	0
Special Section on the Forty-Ninth Annual ACM Symposium on the Theory of Computing (STOC 2017)	0
Polynomial Data Structure Lower Bounds in the Group Model	0
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations	0
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction	0
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao	0
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics	0
How to Trap a Gradient Flow	0