Andrei Bulatov "On the Complexity of CSP-based Ideal Membership Problems"
Andrei Bulatov from Simon Fraser University, Canada gave the talk "On the Complexity of CSP-based Ideal Membership Problems" on the labs' Big Seminar.
Password: first 6 decimal places of $\pi$ after the decimal point
You can also write to Alexander Polyanskii (alexander.polyanskii@yandex.ru) or to Maksim Zhukovskii (zhukmax@gmail.com) if you want to be added to mailing list.
Abstract:
We consider the Ideal Membership Problem (IMP for short), in which we are given real polynomials $f_0,f_1,..., f_k$ and the question is to decide whether $f_0$ belongs to the ideal generated by $f_1,...,f_k$. In the more stringent version the task is also to find a proof of this fact. The IMP underlies many proof systems based on polynomials such as Nullstellensatz, Polynomial Calculus, and Sum-of-Squares. In the majority of such applications the IMP involves so called combinatorial ideals that arise from a variety of discrete combinatorial problems. This restriction makes the IMP significantly easier and in some cases allows for an efficient algorithm to solve it.
In 2019 Mastrolilli initiated a systematic study of IMPs arising from Constraint Satisfaction Problems (CSP) of the form CSP(G), that is, CSPs in which the type of constraints is limited to relations from a set $G$. He described sets $G$ on a 2-element set that give rise to polynomial time solvable IMPs and showed that for the remaining ones the problem is hard. We continue this line of research.
First, 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 three sufficient ones. The sufficient conditions include IMPs arising from systems of linear equations over GF(p), p prime, and also some conditions defined through special kinds of polymorphisms.
Watch the video:
Everyone is invited to attend. The language of the lecture is English. The event is aimed at master and graduate students, as well as researchers in the field of combinatorics.