University of Tartu - ©2011 Dominique Peer Ghislain Dr Unruh - Last update: 11.05.2015 16:40
Date: 14/05/2015 Location: J. Liivi 2, room 317 (next to the coffee room)
Title: Do we really know how to compute geometric progressions?
Abstract:
The problem of efficient computation of exponentiation has been studied with extreme details, due to its very high importance in implementing various cryptographic algorithms. The same cannot be said about the problem of computing sums of consecutive powers of a number or a matrix. This is somewhat unusual, because many problems in graph theory, coding theory, cryptography and, most notably, numerical analysis, can naturally lead to this computational task.
The seminar is aimed at unveiling some rather interesting and non-trivial computational results, associated with the division-free evaluation of the arithmetic progressions. Many of the upper bounds obtained are better than the best known so far estimates. The specific analysis of the computational complexity of based on some classical Markov chain analysis techniques.
The last part of the seminar will cover the possible applications. They include algorithms for efficient solution of a system of linear equations, implementation of the Google's page-ranking algorithms and inversions in binary Galois fields. A large number of possible generalizations and additional applications will be discussed.
Bio: Dr. Vassil Dimitrov is a Professor at the Department of Electrical and Computer Engineering, University of Calgary, Canada since July 2001. Prior to this he hold an Associate Professor position at the University of Windsor, Canada. Dr. Dimitrov had a postdoctoral position at the VLSI Laboratory, University of Windsor, Canada (1996-1998); worked as a research scientist at Reliable Software Technologies, VA, USA (1998-1999) and as a chief research scientist at the Helsinki University of Technology (1999-2000). He has strong contacts with Estonian cryptographic community, due to his participation at the Erasmus-Mundus MSN program during the period 2010-2012. He has taught two graduate courses at the Institute of Computer Science, University of Tartu.
Dr. Dimitrov main scientific interests are in the domain of efficient implementation of algorithms in cryptography, signal and image processing, digital watermarking and, lately, hardware implementation of homomorphic encryption schemes.