Paweł Idziak (Jagiellonian University, Krakow, Poland), Circuits over finite algebras

Tue, 21 Mar 2023, 1:25 pm MDT

The talk reports how the project of characterizing finite algebras with tractable equation solving problem led us to the concepts of circuits and non-uniform automata over arbitrary algebras.
As a byproduct we get (under some complexity hypothesis, like Exponential Time Hypothesis and Constant Degree Hypothesis) a full characterization of finite algebras from congruence modular varieties with tractable checking if two circuits compute the same function. A similar (but not the same one) characterization is also provided for finite groups with respect to checking if two polynomials define the same function.

[slides] [video]