Talks
Spring 2016

Constraints, Gadgets, and Invariants

Wednesday, January 27th, 2016, 9:30 am10:30 am

Add to Calendar

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.

AttachmentSize
PDF icon Constraints, Gadgets, and Invariants217.63 KB