SIAM Journal on Computing

Article	Citations
Optimal (Euclidean) Metric Compression	13
Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier	11
Special Section on the Forty-Ninth Annual ACM Symposium on the Theory of Computing (STOC 2017)	10
Agreement Tests on Graphs and Hypergraphs	9
Fast Generalized DFTs for All Finite Groups	8
Parallel Repetition for the GHZ Game: Exponential Decay	7
Caching with Time Windows and Delays	7
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	6
An Approximate Generalization of the Okamura–Seymour Theorem	6
Shortest Paths Without a Map, but with an Entropic Regularizer	6
Metric Embedding via Shortest Path Decompositions	6
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions	5
Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions	5
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side	4
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion	4
Clustering Mixtures with Almost Optimal Separation in Polynomial Time	4
Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model	4
Why Extension-Based Proofs Fail	4
Fitting Metrics and Ultrametrics with Minimum Disagreements	4
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao	4
A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane	4
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for \(\textsf{ACC}\) Circuits	4
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	3
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths	3
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization	3

Induced Subgraphs of Bounded Treewidth and the Container Method	3
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering	3
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	3
Tree-Depth and the Formula Complexity of Subgraph Isomorphism	3
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness	3
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes	3
Polynomial Data Structure Lower Bounds in the Group Model	3
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	3
Tight Revenue Gaps among Multiunit Mechanisms	3
Optimal Algorithms for Geometric Centers and Depth	2
Geodesic Walks in Polytopes	2
Almost Optimal SuperConstant-Pass Streaming Lower Bounds for Reachability	2
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs	2
Discrepancy Minimization via a Self-Balancing Walk	2
Optimal Resizable Arrays	2
Sorting Short Keys in Circuits of Size ${o(n \log n)}$	2
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough	2
Special Section on the Fifty-First Annual ACM Sympositum on the Theory of Computing (STOC 2019)	2
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs	2
Competitively Chasing Convex Bodies	2
Approximation Algorithms for LCS and LIS with Truly Improved Running Times	2
Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time	2
Weak Zero-Knowledge beyond the Black-Box Barrier	2
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	2
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments	2
Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling	1
Derandomization from Algebraic Hardness	1
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing	1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring	1
Minimum Cuts in Surface Graphs	1
Online List Labeling: Breaking the \({\log^2 n}\) Barrier	1
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	1
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random	1
Isomorphism Testing for Graphs Excluding Small Minors	1
Flow Time Scheduling and Prefix Beck–Fiala	1
Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number	1
Tracing Isomanifolds in \(\mathbb{R}\) d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	1
Consensus-Halving: Does It Ever Get Easier?	1
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches	1
Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier	1
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs	1
A Single-Exponential Time 2-Approximation Algorithm for Treewidth	1
Circuits Resilient to Short-Circuit Errors	1
An Improved Parameterized Algorithm for Treewidth	1
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems	1
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring	1
On Matrix Multiplication and Polynomial Identity Testing	1
Economical Convex Coverings and Applications	1

A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification	1
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing	1
Revisionist Simulations: A New Approach to Proving Space Lower Bounds	1
Traversing Combinatorial 0/1-Polytopes via Optimization	1
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification	1
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model	1
Hop-Constrained Oblivious Routing	1
Two Variable Logic with Ultimately Periodic Counting	1
CLAP: A New Algorithm for Promise CSPs	1
Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs	1
Differentially Private Learning of Geometric Concepts	1
Truly Optimal Euclidean Spanners	1
Contextual Search via Intrinsic Volumes	1
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem	1
On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization	1
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems	1
Rounds vs. Communication Tradeoffs for Maximal Independent Sets	0
Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs	0
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All \({\ell_{{p}}}\) Norms	0
Uniform Restricted Chase Termination	0
Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius	0
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity	0
Average Sensitivity of Graph Algorithms	0
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders	0
Nearly Optimal Static Las Vegas Succinct Dictionary	0
A Short List of Equalities Induces Large Sign-Rank	0
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	0
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding	0
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs	0
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations	0
Approximating Maximum Independent Set for Rectangles in the Plane	0
Proof Complexity and the Binary Encoding of Combinatorial Principles	0
A Strong Version of Cobham’s Theorem	0
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$	0
Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms	0
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	0
Counting Small Induced Subgraphs Satisfying Monotone Properties	0
Smoothing the Gap Between NP and ER	0
Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders	0
On Ray Shooting for Triangles in 3-Space and Related Problems	0
Almost Tight Bounds for Reordering Buffer Management	0
On CDCL-Based Proof Systems with the Ordered Decision Strategy	0
Super-Logarithmic Lower Bounds for Dynamic Graph Problems	0
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction	0
Approximating Minimum Representations of Key Horn Functions	0
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing	0
Elastic-Degenerate String Matching via Fast Matrix Multiplication	0
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	0
Distributed Lower Bounds for Ruling Sets	0
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue	0
Symmetries, Graph Properties, and Quantum Speedups	0
An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem	0
Testing Linear-Invariant Properties	0
An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions	0
Constant Inapproximability for PPA	0
Counting Small Induced Subgraphs with Hereditary Properties	0
Multi-Item Nontruthful Auctions Achieve Good Revenue	0
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games	0
The Shortest Even Cycle Problem Is Tractable	0
AdWords in a Panorama	0
Differentially Private Sampling from Distributions	0
How to Trap a Gradient Flow	0
Complexity Classification Transfer for CSPs via Algebraic Products	0
On the Complexity of Equilibrium Computation in First-Price Auctions	0
Corrigendum: Metric Embedding via Shortest Path Decompositions	0
The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs	0
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise	0
Internal Pattern Matching Queries in a Text and Applications	0
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs	0
Deterministic Massively Parallel Connectivity	0
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection	0
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer	0
Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu	0
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem	0
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	0
Satisfiability in MultiValued Circuits	0
Interior Point Methods Are Not Worse than Simplex	0
Lower Bounds for External Memory Integer Sorting via Network Coding	0
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication	0
A Local Search Framework for Experimental Design	0

Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	0
Fast FPT-Approximation of Branchwidth	0
Special Section on the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (2020)	0
Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph	0
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	0
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	0
The Optimal Error Resilience of Interactive Communication over Binary Channels	0
Computational Complexity of the Hylland–Zeckhauser Mechanism for One-Sided Matching Markets	0
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance	0
Reducing Path TSP to TSP	0
Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions	0
A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines	0
Parameterized Complexity of Untangling Knots	0
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)	0
Algebraic Algorithms for Fractional Linear Matroid Parity via Noncommutative Rank	0
Topology and Adjunction in Promise Constraint Satisfaction	0
Decidability of Membership Problems for Flat Rational Subsets of \(\boldsymbol{{\textrm{GL}}(2,\boldsymbol{{\mathbb{Q}}})}\) and Singular Matrices	0
A Tight Analysis of Bethe Approximation for Permanent	0
On the Computability of Continuous Maximum Entropy Distributions with Applications	0
Reachability Preservers: New Extremal Bounds and Approximation Algorithms	0
Low-Density Parity-Check Codes Achieve List-Decoding Capacity	0
A Spectral Approach to Network Design	0
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	0
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	0
Proximity Search for Maximal Subgraph Enumeration	0
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics	0
Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018)	0
Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification	0
Constant Depth Formula and Partial Function Versions of MCSP Are Hard	0
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	0
Classical Verification of Quantum Computations	0
Balanced Allocation: Patience Is Not a Virtue	0
Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time	0
Sharp Thresholds in Random Simple Temporal Graphs	0
The Power of Two Choices in Graphical Allocation	0
Anchored Parallel Repetition for Nonlocal Games	0
An Improved Upper Bound for the Universal TSP on the Grid	0
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020)	0
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm	0
Fast Metric Embedding into the Hamming Cube	0
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria	0
Spectral Methods from Tensor Networks	0
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich	0
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes	0
Approximate Gomory–Hu Tree is Faster than \(\boldsymbol{n}\,\boldsymbol{-\, 1}\) Maximum Flows	0
Prophet Secretary for Combinatorial Auctions and Matroids	0
Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\)	0
Efficient Construction of Rigid Matrices Using an NP Oracle	0
Sublinear Algorithms for Local Graph-Centrality Estimation	0
Want to Gather? No Need to Chatter!	0
A Parameterized Approximation Scheme for Min $k$-Cut	0
ABE for Circuits with poly\( {(\lambda )}\)-Sized Keys from LWE	0
Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring	0
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings	0
On a Combinatorial Generation Problem of Knuth	0
Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?	0
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions	0
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence	0
PTAS for Minimum Cost MultiCovering with Disks	0
FIXP-Membership via Convex Optimization: Games, Cakes, and Markets	0
Almost-Optimal Sublinear Additive Spanners	0
Online Edge Coloring via Tree Recurrences and Correlation Decay	0
A Framework for the Secretary Problem on the Intersection of Matroids	0
Rigid Matrices from Rectangular PCPs	0
One-Way Functions and (Im)perfect Obfuscation	0
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion	0
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover	0
Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid	0
Removing Additive Structure in 3SUM-Based Reductions	0
An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences	0
Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits	0
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics	0
An ETH-Tight Exact Algorithm for Euclidean TSP	0
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics	0
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	0
Unambiguous DNFs and Alon–Saks–Seymour	0
Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering	0
Counting Subgraphs in Somewhere Dense Graphs	0
Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming	0
Exact-Size Sampling of Enriched Trees in Linear Time	0