Report
Teaser, summary, work performed and final results
Periodic Reporting for period 2 - PowAlgDO (Power of Algorithms in Discrete Optimisation)
Teaser
\"The recent work on the project included the understanding of hardness for promise CSPs, and the role of #BIS (independent sets in bipartite graphs) in counting complexity of homomorphism problems related to CSPs. This is well aligned with the overall project goal of...
Summary
\"The recent work on the project included the understanding of hardness for promise CSPs, and the role of #BIS (independent sets in bipartite graphs) in counting complexity of homomorphism problems related to CSPs. This is well aligned with the overall project goal of understanding the complexity of CSPs and its variants.\"
Work performed
Main results include several complexity classifications for various fragments of constraint satisfaction problems.
Final results
The recent work on PCSPs (promise CSPs) wasn\'t envisaged in the proposal and is a nice surprise.
Website & more info
More info: http://www.cs.ox.ac.uk/standa.zivny/homepage/powalgdo.html.