SIAM Journal on Computing

Article	Citations
Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians	38
Optimization of the Sherrington--Kirkpatrick Hamiltonian	19
How to Use Indistinguishability Obfuscation: Deniable Encryption, and More	17
A Little Charity Guarantees Almost Envy-Freeness	14
Classical Homomorphic Encryption for Quantum Circuits	10
Error Thresholds for Arbitrary Pauli Noise	10
Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications	9
A Weighted Linear Matroid Parity Algorithm	9
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy	8
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models	8
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model	7
Online Contention Resolution Schemes with Applications to Bayesian Selection Problems	7
The Complexity of Contracts	6
New Results on Linear Size Distance Preservers	6
An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem	6
Algorithmic Stability for Adaptive Data Analysis	6
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich	5
An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees	5
Reducing Path TSP to TSP	5
Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders	5
Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs	5
Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time	5
On the Power of Relaxed Local Decoding Algorithms	5
Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing	4
From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces	4

Toward Tight Approximation Bounds for Graph Diameter and Eccentricities	4
Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC	4
Classical Verification of Quantum Computations	4
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems	4
Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations	3
Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions	3
Perfect $L_p$ Sampling in a Data Stream	3
A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation	3
Solving CSPs Using Weak Local Consistency	3
Structure Versus Hardness Through the Obfuscation Lens	3
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing	3
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions	3
Query-to-Communication Lifting Using Low-Discrepancy Gadgets	3
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle	3
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction	3
Elastic-Degenerate String Matching via Fast Matrix Multiplication	3
Derandomization from Algebraic Hardness	3
CLAP: A New Algorithm for Promise CSPs	3
On a Combinatorial Generation Problem of Knuth	3
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem	3
List-Decoding with Double Samplers	3
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions	3
A Polynomial Lower Bound for Testing Monotonicity	3
New Hardness Results for Routing on Disjoint Paths	2
The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs	2
Isomorphism Testing for Graphs Excluding Small Minors	2
Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles	2
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side	2
Unit Capacity Maxflow in Almost $m^{4/3}$ Time	2
The Communication Complexity of Set Intersection and Multiple Equality Testing	2
Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits	2
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	2
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	2
Approximating Minimum Representations of Key Horn Functions	2
Geodesic Walks in Polytopes	2
Counting Solutions to Random CNF Formulas	2
Metric Embedding via Shortest Path Decompositions	2
Perfect Secure Computation in Two Rounds	2
Quantum Hardness of Learning Shallow Classical Circuits	2
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	2
Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming	2
Proximity Search for Maximal Subgraph Enumeration	2
Truly Optimal Euclidean Spanners	2
Distributed Spanner Approximation	2
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering	2
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization	2
Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace	2
An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences	2
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem	2
Tight Bounds for the Subspace Sketch Problem with Applications	1

Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors	1
Smoothing the Gap Between NP and ER	1
Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling	1
One-Way Functions and (Im)perfect Obfuscation	1
Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems	1
Topology and Adjunction in Promise Constraint Satisfaction	1
Optimal (Euclidean) Metric Compression	1
Why Extension-Based Proofs Fail	1
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	1
Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space	1
Multi-Item Nontruthful Auctions Achieve Good Revenue	1
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games	1
A Short List of Equalities Induces Large Sign-Rank	1
Contextual Search via Intrinsic Volumes	1
Weak Zero-Knowledge beyond the Black-Box Barrier	1
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$	1
NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs	1
A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP	1
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	1
Caching with Time Windows and Delays	1
Sparse MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture	1
A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals	1
Nonlocal Games with Noisy Maximally Entangled States are Decidable	1
Satisfiability in MultiValued Circuits	1
Explicit Near-Ramanujan Graphs of Every Degree	1
Lower Bounds for External Memory Integer Sorting via Network Coding	1
Dynamic Sampling from Graphical Models	1
Consensus-Halving: Does It Ever Get Easier?	1
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs	1
Hop-Constrained Oblivious Routing	1
Corrigendum: LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs	1
Effective Wireless Scheduling via Hypergraph Sketches	1
Counting Small Induced Subgraphs Satisfying Monotone Properties	1
Distributed Lower Bounds for Ruling Sets	1
Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring	0
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020)	0
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	0
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover	0
Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time	0
Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms	0
Discrepancy Minimization via a Self-Balancing Walk	0
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer	0
A Local Search Framework for Experimental Design	0
A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines	0
Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths	0
Want to Gather? No Need to Chatter!	0
Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius	0
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)	0
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs	0
A Strong Version of Cobham’s Theorem	0
Spectral Methods from Tensor Networks	0
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	0
Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time	0
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes	0
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics	0
Optimal Algorithms for Geometric Centers and Depth	0
Balanced Allocation: Patience Is Not a Virtue	0
Deterministic Massively Parallel Connectivity	0
On the Complexity of Equilibrium Computation in First-Price Auctions	0
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	0
Sharp Thresholds in Random Simple Temporal Graphs	0
Polynomial Data Structure Lower Bounds in the Group Model	0
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions	0
Adaptive Planar Point Location	0
Special Section on the Forty-Ninth Annual ACM Symposium on the Theory of Computing (STOC 2017)	0
Fast Metric Embedding into the Hamming Cube	0
Efficient Construction of Rigid Matrices Using an NP Oracle	0
Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring	0
Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time	0
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces	0
Approximation Algorithms for LCS and LIS with Truly Improved Running Times	0
On CDCL-Based Proof Systems with the Ordered Decision Strategy	0
Spectral Analysis of Matrix Scaling and Operator Scaling	0
A Single-Exponential Time 2-Approximation Algorithm for Treewidth	0
Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions	0
Nearly Optimal Static Las Vegas Succinct Dictionary	0
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches	0
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics	0
Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs	0
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria	0

Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations	0
Almost Tight Bounds for Reordering Buffer Management	0
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance	0
Rounds vs. Communication Tradeoffs for Maximal Independent Sets	0
Special Section on the Fifty-First Annual ACM Sympositum on the Theory of Computing (STOC 2019)	0
Average Sensitivity of Graph Algorithms	0
Parameterized Complexity of Untangling Knots	0
Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018)	0
An Optimal Separation of Randomized and Quantum Query Complexity	0
Testing Linear-Invariant Properties	0
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm	0
Sublinear Algorithms for Local Graph-Centrality Estimation	0
Clustering Mixtures with Almost Optimal Separation in Polynomial Time	0
Flow Time Scheduling and Prefix Beck–Fiala	0
Counting Small Induced Subgraphs with Hereditary Properties	0
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness	0
Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs	0
A Parameterized Approximation Scheme for Min $k$-Cut	0
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection	0
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for \(\textsf{ACC}\) Circuits	0
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs	0
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao	0
Exact-Size Sampling of Enriched Trees in Linear Time	0
On Ray Shooting for Triangles in 3-Space and Related Problems	0
Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier	0
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	0
Unambiguous DNFs and Alon–Saks–Seymour	0
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems	0
Special Section on the 48th Annual ACM Symposium on Theory of Computing (STOC 2016)	0
Uniform Restricted Chase Termination	0
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification	0
On the Computability of Continuous Maximum Entropy Distributions with Applications	0
An Algebraic Approach to Nonmalleability	0
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem	0
Reachability Preservers: New Extremal Bounds and Approximation Algorithms	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
Minimum Cuts in Surface Graphs	0
The Shortest Even Cycle Problem Is Tractable	0
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification	0
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication	0
Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs	0
An ETH-Tight Exact Algorithm for Euclidean TSP	0
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders	0
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings	0
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs	0
A Tight Analysis of Bethe Approximation for Permanent	0
Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu	0
A Framework for the Secretary Problem on the Intersection of Matroids	0
Competitively Chasing Convex Bodies	0
Tracing Isomanifolds in \(\mathbb{R}\) d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	0
Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid	0
A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane	0
A Spectral Approach to Network Design	0
On Matrix Multiplication and Polynomial Identity Testing	0
Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering	0
Tight Revenue Gaps among Multiunit Mechanisms	0
Anchored Parallel Repetition for Nonlocal Games	0
An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions	0
Tree-Depth and the Formula Complexity of Subgraph Isomorphism	0
Online Edge Coloring via Tree Recurrences and Correlation Decay	0
FIXP-Membership via Convex Optimization: Games, Cakes, and Markets	0
Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model	0
Constant Depth Formula and Partial Function Versions of MCSP Are Hard	0
Low-Density Parity-Check Codes Achieve List-Decoding Capacity	0
Differentially Private Learning of Geometric Concepts	0
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	0
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion	0
Sorting Short Keys in Circuits of Size ${o(n \log n)}$	0
Maximum Rectilinear Convex Subsets	0
Corrigendum: Metric Embedding via Shortest Path Decompositions	0
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture	0