Algebraic, logical and combinatorial methods with applications in theoretical computer science

Within this project we will conduct research in several connected areas of mathematics and apply our results in computer science. The group of researchers headed by the principal investigator will apply the results of Universal Algebra and Graph Theory to the Dichotomy Conjecture on complexity of the Constraint Satisfaction Problem. This conjecture has lately attracted attention of large number of researchers from the areas of Mathematical Logic, Computational Complexity, Graph Theory and Universal Algebra. Another group of researchers is working in the area of Combinatorial Optimization. They are applying the methods of nonlinear programming to classical problems of Combinatorial Optimization, while simultaneously developing algorithms able to resolve practical problems which can be modeled by discrete structures. We also plan to connect these two topics. Namely, the idea of polymorphisms which is fundamental for decomposing structures which are investigated within the framework of the Constraint Satisfaction Problem, could be applied to the problems of Combinatorial Optimization, as well. On the other hand, new techniques used in the analysis of Combinatorial Optimization problems could also be applied to the decision problems, such as Constraint Satisfaction Problem.