SIAM J. Comput.

Keyphrases

Publications

volume 53, number 1, 2024

Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong
Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring. SIAM J. Comput. 53 (1) (2024)
Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs. SIAM J. Comput. 53 (1) (2024)
David Gamarnik, Aukosh Jagannath, Alexander S. Wein
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics. SIAM J. Comput. 53 (1) (2024)
Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab S. Sawhney, Jakub Tarnawski
Online Edge Coloring via Tree Recurrences and Correlation Decay. SIAM J. Comput. 53 (1) (2024)
Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong
Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring. SIAM J. Comput. 53 (1) (2024)

volume 53, number 2, 2024

Jacob Focke, Marc Roth
Counting Small Induced Subgraphs with Hereditary Properties. SIAM J. Comput. 53 (2) (2024)
Artur Czumaj, Christian Sohler
Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph. SIAM J. Comput. 53 (2) (2024)
Arnaud Casteigts, Michael Raskin, Malte Renken, Viktor Zamaraev
Sharp Thresholds in Random Simple Temporal Graphs. SIAM J. Comput. 53 (2) (2024)
Ruben Becker, Yuval Emek, Mohsen Ghaffari, Christoph Lenzen
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions. SIAM J. Comput. 53 (2) (2024)
Ishay Haviv
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems. SIAM J. Comput. 53 (2) (2024)
Sjoerd Dirksen, Shahar Mendelson, Alexander Stollenwerk
Fast Metric Embedding into the Hamming Cube. SIAM J. Comput. 53 (2) (2024)
Clément Legrand-Duchesne, Ashutosh Rai, Martin Tancer
Parameterized Complexity of Untangling Knots. SIAM J. Comput. 53 (2) (2024)
Amir Abboud, Greg Bodwin
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. SIAM J. Comput. 53 (2) (2024)
Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters
Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings. SIAM J. Comput. 53 (2) (2024)
Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal
Rigid Matrices from Rectangular PCPs. SIAM J. Comput. 53 (2) (2024)

volume 53, number 3, 2024

volume 53, number 4, 2024

Sébastien Bubeck, Dan Mikulincer
How to Trap a Gradient Flow. SIAM J. Comput. 53 (4) (2024)
Sunil Arya, Guilherme Dias da Fonseca, David M. Mount
Economical Convex Coverings and Applications. SIAM J. Comput. 53 (4) (2024)
Jason M. Altschuler, Jinho Bok, Kunal Talwar
On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization. SIAM J. Comput. 53 (4) (2024)
Fedor V. Fomin, Tuukka Korhonen
Fast FPT-Approximation of Branchwidth. SIAM J. Comput. 53 (4) (2024)
Michael Benedikt, Egor V. Kostylev, Tony Tan
Two Variable Logic with Ultimately Periodic Counting. SIAM J. Comput. 53 (4) (2024)
Isolde Adler, Noleen Köhler, Pan Peng
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing. SIAM J. Comput. 53 (4) (2024)
Faith Ellen, Rati Gelashvili, Leqi Zhu
Revisionist Simulations: A New Approach to Proving Space Lower Bounds. SIAM J. Comput. 53 (4) (2024)

volume 52, number 4, 2023

Nithin Varma, Yuichi Yoshida
Average Sensitivity of Graph Algorithms. SIAM J. Comput. 52 (4) (2023)

volume 52, number 5, 2023

volume 52, number 6, 2023