{"id":"hexagon/2610.00594","pdf":"https://hexagonmath.org/pdf/2610.00594v1","url":"https://hexagonmath.org/abs/2610.00594v1","tags":["math.CO","cs.DS","msc:68Q25","msc:68Q17","msc:68W40","msc:05C31","msc:05C85","Exponential Time Hypothesis","LDPC codes.","Max-SAT"],"score":0,"title":"Subexponential Weighted Counting and Exact Optimisation","domain":"cs.CC","origin":"ai-generated","source":"hexagon","authors":["Deep Bhattacharjee"],"reviews":0,"subject":"cs.CC","summary":"The deterministic algorithm of \\oai{} that counts the satisfying assignments of a $k$-CNF in time $2^{o(n)}$ is reproduced in full and extended from counting to sums of local weights with values in any commutative $\\Q$-algebra. The extension gives deterministic $2^{o(n)}$ algorithms for exact Max-Cut and Max-$k$-SAT on sparse instances, for the independence polynomial, the maximum independent set and the knapsack problem with a conflict graph on every graph, for $0$-$1$ integer programs whose rows involve boundedly many variables, for Vertex Cover in time $2^{o(k)}+\\poly(n)$, for the density…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-29","reactions":{},"withdrawn":false,"authorship":"mixed","formalized":false,"human_understanding":"some"}