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.
Complexity of Satisfiability and Equivalence Problems in Finite Algebras Sponsored by the Meyer Fund
We review the setup of topological invariants as they appear in physics in the interpretation of K-theory. The basic Z-valued invariant can be identified with the first Chern-class. This goes back to the TKNN integers appearing in the quantum Hall effect. More subtle invariants appear in the setting of symmetries. These can be identified as coming from Real K-theory (KR) theory and its shifted cousin, quaternionic K-theory (KQ). We will give a gentle introduction and present the mathematical and condensed matter classification. This is joint work with D. Li and E.B Kaufmann
Topological Insulators and K-theory Sponsored by the Meyer Fund
Complexity of Satisfiability and Equivalence Problems in Finite Algebras