Constraints, Gadgets, and Invariants
summary
Gadget constructions reduce CSPs to each other by wiring small constraint networks; polymorphisms characterize gadget reductions for decision CSPs (and for exact unweighted counting), so presence of nontrivial polymorphisms predicts tractability. For optimization and approximation, distributions over operations—fractional polymorphisms yield SDP relaxations—give tight thresholds under the Unique Games Conjecture. Partial polymorphisms and Fourier/LSM analyses extend the method to conservative counting cases; holographic reductions remain an outlier.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 1:34Outline
- 3:02Constraints
- 5:29Decision Problems
- 9:04Gadgets
- 14:47Constraint Language
- 15:28Quantifying
- 17:58Atomization
- 18:33Stretching
- 20:16Counting
- 21:24In implication
- 23:59Polymorphisms
- 31:35Optimization
- 36:58Fractional Polymorphism
- 42:05Approximation Counting
- 43:31CSP of Relations
related talks
01h 25mInapproximability of Constraint Satisfaction Problems IV
01h 17mInapproximability of Constraint Satisfaction Problems V
01h 17mInapproximability of Constraint Satisfaction Problems III
01h 01mThe Gospel According to TCS
01h 04mFrontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
01h 22mTutorial 5: The GCT Chasm II
56mEntropy, Capacity, and Counting
01h 30mInapproximability of Constraint Satisfaction Problems II