Tight Algorithms for Conservative Finite-Valued CSPs Parameterized by Treewidth
cs.DS, cs.CC
Submitted: 2026-11-12
Updated: 2026-11-12
Code: https://github.com/anthropics/formal-math
Terminology
Sources
- 3SUM Made Simpler (Without Matrix Multiplication), k-SUM Hypothesis Refuted for Odd k, and Real 3SUM/APSP Derandomized
- k-SUM Hardness Implies Treewidth-SETH
- Fast Dynamic Programming on Graph Decompositions
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time