Constraint Satisfaction Problems and friends: Symmetries and algorithm design

The Constraint Satisfaction Problem (CSP) provides a general framework for a wide range of combinatorial problems dealing with mappings and assignments, including satisfiability, graph colorability, and systems of equations. Followed by seminal work of Feder and Vardi 1993, universal algebraic techniques have been developed and quite successfully employed in studies of CSPs from different perspectives. In this dissertation, we consider two significant generalizations of CSPs, namely the Ideal Membership Problem (IMP) and Valued CSP (VCSP), and study them through the lens of universal algebra.IMP is a fundamental algorithmic problem in which we are given a real polynomial f and an ideal I and the question is to decide whether f belongs to the ideal I. We consider a systematic study of IMPs arising from CSPs where the type of constraints is limited to relations from a constraint language. We show that many CSP techniques can be translated to IMPs thus allowing us to significantly improve the methods of studying the complexity of the IMP. We also develop universal algebraic techniques for the IMP that have been so useful in the study of the CSP. This allows us to prove a general necessary condition for the tractability of the IMP, and several sufficient ones. We furthermore introduce a variant of the IMP and study its complexity. We prove several algorithmic consequences of it such as a unifying framework to design polynomial-time algorithm to construct Groebner basis for many combinatorial problems. Finally, we study applications of our results in automatability of Sum-of-Squares (SoS) proofs and construction of Theta Bodies of combinatorial problems. We then turn our attention to the most general optimization variant of the CSP namely, Valued Constraint Satisfaction Problem (VCSP), which deals with both feasibility and optimization. We consider the Minimum Cost H-coloring problem which is an important type of VCSP and is a natural optimization version of the classical H-coloring problem. We give a complete classification of graphs, in terms of their polymorphisms, for which the Minimum Cost H-coloring is approximable within a constant factor, and present several positive results regarding digraphs. From a more practical point of view, VCSPs are at the core of many machine learning and data mining tasks and in numerous number of such applications the underlying VCSPs satisfy the submodularity property. We study central topics in machine learning, namely differential privacy and sparsification, in the context of submodularity, and present several algorithmic results.