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).
CEQV and CSAT for nilpotent Maltsev algebras
Nov. 03, 2020 2pm (zoom)
Lie Theory
Flor Orosz Hunziker (CU)
X
In this talk we will discuss the tensor structure associated with certain representations of the Virasoro algebra. In particular, we will show that there is a braided tensor category structure on the category of C1-cofinite modules for the Virasoro vertex operator algebras of arbitrary central charge. This talk is based on joint work with Thomas Creutzig, Cuibo Jiang, David Ridout and Jinwei Yang.
Tensor Categories arising from the Virasoro algebra