default search action
SIAM Journal on Computing, Volume 53
Volume 53, Number 1, February 2024
- David Gamarnik, Aukosh Jagannath, Alexander S. Wein:
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics. 1-46 - Maria Chudnovsky
, Marcin Pilipczuk
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs. 47-86 - Janardhan Kulkarni, Yang P. Liu
Online Edge Coloring via Tree Recurrences and Correlation Decay. 87-110 - Maria Chudnovsky
Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring. 111-145 - Maria Chudnovsky
Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring. 146-187
Volume 53, Number 2, 2024
- Jacob Focke
Counting Small Induced Subgraphs with Hereditary Properties. 189-220 - Amir Abboud, Greg Bodwin
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. 221-246 - Ruben Becker, Yuval Emek, Mohsen Ghaffari, Christoph Lenzen:
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions. 247-286 - Ishay Haviv
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems. 287-314 - Sjoerd Dirksen, Shahar Mendelson, Alexander Stollenwerk:
Fast Metric Embedding into the Hamming Cube. 315-345 - Arnaud Casteigts
Sharp Thresholds in Random Simple Temporal Graphs. 346-388 - Zeyu Guo
Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings. 389-430 - Clément Legrand-Duchesne, Ashutosh Rai, Martin Tancer:
Parameterized Complexity of Untangling Knots. 431-479 - Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal:
Rigid Matrices from Rectangular PCPs. 480-523 - Artur Czumaj, Christian Sohler:
Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph. 524-571
Volume 53, Number 3, 2024
- Mika Göös, Alexandros Hollender
Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\). 573-587 - Ravishankar Krishnaswamy, Viswanath Nagarajan
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing. 588-623 - Tara Abrishami, Maria Chudnovsky
Induced Subgraphs of Bounded Treewidth and the Container Method. 624-647 - Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret
Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative? 648-700 - Zhiyi Huang
AdWords in a Panorama. 701-763 - Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin:
Proof Complexity and the Binary Encoding of Combinatorial Principles. 764-802
Volume 53, Number 4, 2024
- Sébastien Bubeck, Dan Mikulincer
How to Trap a Gradient Flow. 803-824 - Isolde Adler, Noleen Köhler
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing. 825-883 - Michael Benedikt
Two Variable Logic with Ultimately Periodic Counting. 884-968 - Jason M. Altschuler
On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization. 969-1001 - Sunil Arya
Economical Convex Coverings and Applications. 1002-1038 - Faith Ellen
Revisionist Simulations: A New Approach to Proving Space Lower Bounds. 1039-1084 - Fedor V. Fomin, Tuukka Korhonen
Fast FPT-Approximation of Branchwidth. 1085-1131 - Haitao Wang
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments. 1132-1161 - Jason Li, Debmalya Panigrahi
Approximate Gomory-Hu Tree is Faster than \(\boldsymbol{n}\,\boldsymbol{-\, 1}\) Maximum Flows. 1162-1180 - Ziyun Huang, Qilong Feng, Jianxin Wang, Jinhui Xu:
PTAS for Minimum Cost MultiCovering with Disks. 1181-1215
Volume 53, Number 5, 2024
- Zhiyi Huang
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue. 1217-1256 - Arturo Merino
Traversing Combinatorial 0/1-Polytopes via Optimization. 1257-1292 - Manuel Bodirsky
Complexity Classification Transfer for CSPs via Algebraic Products. 1293-1353 - Robert E. Tarjan, Uri Zwick
Optimal Resizable Arrays. 1354-1380 - Gilad Asharov
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions. 1381-1408 - Marco Bressan
Counting Subgraphs in Somewhere Dense Graphs. 1409-1438 - Huck Bennett, Mahdi Cheraghchi
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All \({\ell_{{p}}}\) Norms. 1439-1475 - George Christodoulou, Alkmini Sgouritsa:
An Improved Upper Bound for the Universal TSP on the Grid. 1476-1523 - Tomasz Kociumaka
Internal Pattern Matching Queries in a Text and Applications. 1524-1577 - Édouard Bonnet
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes. 1578-1601 - Édouard Bonnet
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring. 1602-1640
Volume 53, Number 6, 2024
- Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim
Prophet Secretary for Combinatorial Auctions and Matroids. 1641-1662 - Tarun Kathuria, Yang P. Liu, Aaron Sidford:
Unit Capacity Maxflow in Almost $m^{4/3}$ Time. S20-175 - Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein:
Polynomial Data Structure Lower Bounds in the Group Model. S20-74 - Nima Anari, Kuikui Liu, Shayan Oveis Gharan:
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. S20-1 - Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow
Smoothing the Gap Between NP and ER. S20-102 - Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan
A Parameterized Approximation Scheme for Min $k$-Cut. S20-205 - Yuval Filmus, Elena Grigorescu, Sungjin Im, Yi Li:
Special Section on the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (2020). S20- - Paul Dütting, Thomas Kesselheim
An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions. S20-239 - Rahul Ilango:
Constant Depth Formula and Partial Function Versions of MCSP Are Hard. S20-317 - Jonathan Mosheiff
Low-Density Parity-Check Codes Achieve List-Decoding Capacity. S20-38 - Shai Evra, Tali Kaufman, Gilles Zémor
Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders. S20-276 - Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang:
Symmetries, Graph Properties, and Quantum Speedups. S20-368 - Marc Roth
Counting Small Induced Subgraphs Satisfying Monotone Properties. S20-139 - Volker Diekert, Igor Potapov, Pavel Semukhin:
Decidability of Membership Problems for Flat Rational Subsets of \(\boldsymbol{{\textrm{GL}}(2,\boldsymbol{{\mathbb{Q}}})}\) and Singular Matrices. 1663-1708 - Antoine Mottet, Tomás Nagy
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough. 1709-1745
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-03-13 20:06 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: