Constraints, Gadgets, and Invariants

   Lecture 1: Constraints, Gadgets, and Invariants
   

This series of talks is part of the Counting Complexity and Phase Transitions Boot Camp. 

Speaker: Andrei Bulatov (Simon Fraser University)

Gadgets, big and small, are ubiquitous in deciding the complexity of various computational problems. One approach to study gadget reducibility between problems is to design certain invariants preserved by gadgets. A special type of such invariants, algebraic invariants, plays a significant rope in the decision constraint satisfaction problem, and in exact counting. We review the invariants approach in those two cases and look for ways to expand this approach to approximate counting.