Tue, 03 Nov 2020, 1 pm MST
Even though nilpotent algebras with a Maltsev term have many pleasant algebraic properties, they are not completely understood from a computational point of view. This concerns in particular the complexity of the circuit equivalence problem CEQV(A), i.e. the problem of deciding whether an equation of polynomials p(x_1,…,x_k) = q(x_1,…,x_k), encoded by circuits, holds for all values in the algebra A; and the closely related circuit satisfiability problem CSAT(A), which asks if there is a solution to such an equation.
In a previous talk in Boulder I showed how, under the assumption of an open conjecture in circuit complexity, there are algorithms with quasipolynomial running time O(e^{log(n)^c}) for both CEQV(A) and CSAT(A), for all finite nilpotent Maltsev algebras A. Assuming the Exponential Time Hypothesis, Idziak, Kawalek and Krzaczkowski, recently showed proper quasipolynomial lower bounds (i.e. c>1) on the complexity for some nilpotent algebras. Thus, under the assumption of both conjectures, there are nilpotent algebras A such that CEQV(A) and CSAT(A) can be solved in quasipolynomial, but not polynomial time.
In this talk I would like to discuss their proof and outline how to generalize it to all nilpotent algebras of Fitting length >= 3 (work in progress).