Counting Approximation Complexity Classification Through Clones and Invariants
summary
Classifies approximation complexity of counting CSPs by the closure of constraint sets under gadget constructions and limits, using gadget reductions, Fourier analysis and holographic ideas to build functional clones. Proves for conservative clones (all unary functions present) every problem is either in FP, equivalent to #BIS, or #P-hard, leaving a stubborn unresolved IMP–LSM gap of clones between implication and log-supermodular functions. Introduces Omega-clone closures to handle limits and shows which fragments reduce to known hard or tractable targets.
AI-written summary · about