Abstract

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.

Video Recording