Talks
Spring 2016
Constraints, Gadgets, and Invariants
Wednesday, January 27th, 2016, 9:30 am–10:30 am
Speaker:
Andrei Bulatov (Simon Fraser University)
Location:
Calvin Lab Auditorium
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.
Attachment | Size |
---|---|
Constraints, Gadgets, and Invariants | 217.63 KB |