Seminar: T-codes, T-complexity, T-information and T-entropy - theory and applications

1 Nov 2019 11:00 AM - 12:00 PM
Presenter/Speaker: Dr Ulrich Speidel, School of Computer Science, University of Auckland
Location: G.1.15

This talk is my "theory turf", so to speak. It looks at T-codes, a family of statistically self-synchronising variable-length codes with a highly recursive hierarchical construction. The number of (weighted) construction steps for the code lends itself as a natural measure of code complexity: It is literally the number of bits required to address an arbitrary internal node in the tree. But T-codes also have a number of other rather intriguing properties. For one, it is possible to transform any finite string into a unique T-code and vice versa. This allows us to define a string complexity by simply using the aforementioned complexity for the code that the string transforms into. This string complexity estimate, T-complexity, and its linearised version, the T-information, whose gradient is known as the T-entropy, have been shown to align well empirically with both Shannon entropy and the Lempel-Ziv production complexity. We have used them, among others, for network event detection and in steganalysis. Another property of T-codes is their relationship with cyclic equivalence classes: Every T-code codeword belongs to its own cyclic equivalence class, and no T-code can contain two codewords from the same cyclic equivalence class. Moreover, the construction process of any T-code guarantees that any given non-periodic cyclic equivalence class is either represented by a codeword, or was represented by a codeword until that codeword was used during the construction, or can be represented by a codeword produced through further extension of the code. There is also a clear distinction on how codewords from periodic and non-periodic cyclic equivalence are generated. This links cyclic equivalence classes more generally to code synchronisation than was the case beforehand, when they were associated with fixed-length comma-free codes only. For our work, the link to cyclic equivalence classes permitted us to solve a number of problems in the asymptotics of T-complexity, lending an asymptotic rationale to the linearisation of T-complexity into T-information.

BIO:
Ulrich Speidel began academic life as a physicist, never completed his diploma at the University of Erlangen-Nuremberg in Germany and instead graduated with an MSc from Auckland in underwater acoustic signal processing for long distance global warming measurements in 1994 as hist first degree. He has since haunted the corridors of Computer Science at Auckland as a bit of an alien: as a PhD student until 1998, and then since 2000 as a member of academic staff. He has taught courses ranging from theory to object oriented programming for the web and databases - with his natural research home in data communications, information theory, and related fields. He has umpteen publications, the odd citation he is proud of, is a member of the IEEE, served as a project associate professor at the University of Tokyo in 2010, and has had visiting appointments at MIT, the University of Victoria, Canada, the University of Johannesburg, and the University of Ulm in Germany. He has been involved in the supervision of 7 successful PhD and 8 MSc graduates, as well as of five successful guide dog puppies.