When we work in finite algebra and take into account the
computational complexity of homomorphisms between objects (groups,
rings, etc.) -- as it is required in cryptography and computational
algebra -- we find ourselves in a strange world where, most likely,
almost nothing is invertible. However, this non-invertibility, in its
more important manifestations (which includes famous problems such as
the Discrete Logarithm Problem over finite fields) had so far never been
proven.
But I will try to demonstrate that a sincere acceptance of this
(thermodynamic in its nature) non-invertibility allows us to develop
surprisingly efficient algorithms which solve previously inaccessible
problems in computational group theory.
This is a joint work with Sukru Yalcinkaya; I will describe and
informally explain a few of our very recent results.