ICE-TCS Lectures Series - Mario Szegedy - Polynomial Time Solvability and Invariants of the Witness Set

The next ICE-TCS  talk for this semester will be delivered on Thursday, 3 December, by Professor Mario Szegedy (Rutgers University, NJ, USA). The talk, entitled Polynomial Time Solvability and Invariants of the Witness Set, will be held in room K5 at Reykjavík University (Kringlan 1) from 14:00 till 15:00. 

Further information about forthcoming ICE- TCS events may be found at the ICE-TCS  news page

Abstract

This is an exploratory talk based on the vision that for large classes of important NP problems the membership in P of a given problem depends on the existence of certain invariants on the witness set. First we focus on the class of constraint satisfaction problems (CSPs), where the existence of so-called polymorphism of certain types
are known to be in relation with polynomial time solvability. This was established by Jeavons and co-authors, and by now their theory has an extensive literature. G. Kun and the speaker have recently given a very combinatorial characterization of these crucial invariants. We suggest that a similar connection may exist for well known NP problems such as linear programming and graph isomorphism that are not CSPs.

The final goal would be to build a theory that explains (and predicts) the success of solving some problems while establishing the hardness of others, based on these invariants.