Algebra Seminar talk
2023-12-15
Piotr Kawałek
Satisfiability of circuits and equations in algebras
Abstract:
Both in Computer Science as well as Mathematics satisfiability problems play a special role. In the talk we consider variants of problems connected to solving equations and finding satisfying assignments for circuits. The problems we consider come from finite algebraic structures. We seek for efficient algorithms, or argue why such algorithms cannot exist. Moreover, we demonstrate how fast algorithms can, in some cases, imply circuit lower bounds.