Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | future lectures)

On 22.03.2018 at 12:20 in S6, there is the following noon lecture:

Algebraic Approach to Promise Constraint Satisfaction

Alexandr Kazda

Abstract

The Promise Constraint Satisfaction Problem (PCSP) with the right hand side pair A and B, denoted by PCSP(A,B) for short, is a promise problem whose "Yes" instances are relational structures that can be homomorphically mapped into the relational structure A and "No" instances are structures that can't be homomorphically mapped into the structure B. An example of such a problem is (3,4)-coloring of graphs, where we are obliged to answer "Yes" if the input graph is 3-colorable (maps into K_3) and "No" if the input graph is not 4-colorable (does not map into K_4).

In this talk, we will report on a result by Jakub Opršal that a homomorphism from the clonoid of polymorphisms Pol(A,B) to the polymorphism clonoid Pol(A',B') yields a reduction from PCSP(A',B') to PCSP(A,B).

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010