Computational complexity is a field of research whose main objective is to understand the power and limitation of efficient computation. Complexity theory has witnessed quite remarkable progress since its inception in the 1960s, with new methods developed, some questions resolved, and many more important open questions formulated. Despite this progress, many basic questions about efficient computation remain unresolved. One of the main open questions is the famous "P versus NP" problem, considered one of the most important challenges for mathematical research in the 21st century. We are interested in the "P vs. NP" problem, circuit complexity, pseudorandomness, and, more generally, the deep and intricate interplay between Algorithms and Lower Bounds.
CSP (constraint satisfaction problem) and its variants provide a framework that allows one to model a wide range of combinatorial problems that appear both in practice and in theoretical studies. We seek to understand the complexity of constraint problems and develop efficient algorithms to solve them whenever they can be solved. This research involves the classical constraint satisfaction problem, as well as, counting and weighted problems (also known as partition functions).
