Tue, 16 Apr 2024, 1:25 pm MDT
In 1999, Goldmann and Russell initiated a systematic study of algorithmic complexity of equation satisfiability problems in finite groups. In this talk we present some of the most important historical results on the topic as well as some of the very recent progress. We also consider closely connected problems of satisfiability and equivalence of circuits in finite algebras from congruence modular varieties. Some of the most general results in this area were obtained through relating functions computable by short polynomials in these algebras with classes of bounded-depth modular circuits. We discuss these types of connections, which turn out to be especially useful in tractability proofs.
[video]