Archiv zpráv a událostí

Z fakulty

  • Informatické kolokvium 6. 11. Power of algorithms for homomorphisms and generalisations seen . . .

    Informatické kolokvium 6. 11. 2018, 14:00 posluchárna D2
    Assoc. Prof. Dr. Standa Živný, Department of Computer Science, University of
    Oxford
    Power of algorithms for homomorphisms and generalisations seen from both sides
    Abstrakt: The topic of this talk is the computational complexity of and the
    power of algorithms for the homomorphism problem between two relational
    structures, also known as the constraint satisfaction problem (CSP). We briefly
    discuss the known algorithmic and complexity classifications for CSPs
    parametrised by the source or target structures.

    We then discuss in more detail a classification of general-valued CSPs
    parametrised by the source structures. This part of the talk is based on joint
    work (published in FOCS 2018) with Clement Carbonnel and Miguel Romero.

    Webová adresa