SCIENTIFIC PROGRAMS AND ACTIVITIES
|December 6, 2013|
Day Celebrating New Fellows of the Royal Society of Canada
Ian F. Blake, Dept. of Electrical and Computer
Engineering, University of Toronto
Directions in Cryptography
The notion of a one-way function and their use in public key cryptography, introduced in the mid-seventies, led the field of security in a variety of directions. An area of particular interest is the effort to determine the difficulty of certain mathematical tasks, such as integer factorization and the modular discrete logarithm function. Additionally, the use of such mathematical functions in the formulation and implementation of protocols which achieve achieve useful communication functions, has been an area of intense recent interest. This talk will address recent progress on certain aspects of these two areas.
Henri Darmon, Dept. of Mathematics and
Statistics, McGill University
Elliptic curves and Kronecker's solution to Pell's equation
A celebrated 1865 paper of Kronecker describes how to solve Pell's equation in terms of values of the Dedekind eta-function. I will describe his approach, assuming no prior number theoretic background, and indicate how it can be modified to construct rational points on elliptic curves in terms of the modular symbols of Birch and Manin; the latter topic is part of a work in progress with Massimo Bertolini.
Ian Munro, University of Waterloo
Succinct Data Structures
Although computer memories, at all levels of the hierarchy, have grown dramatically over the past few years, increased problem size continues to outstrip this growth. Recently developed data compression techniques attack one major aspect of the problem, but here we focus on structural information: combinatorial objects such as trees, other classes of graphs, permutations and the like. The interest is in representations that are not only terse, but also permit the basic operations one would expect on the underlying data type to be performed quickly without decoding large portions of the data. We call such data structures succinct. The archtypical example is the binary tree, whose usual representation requires 4n lg n bits, if we are to navigate up and down the tree and report subtree size. The information theoretic minimum, however, is only about 2n bits. We present a representation requiring essentially this mimimal space while supporting, in constant time, the natural operations used in traversing a tree. The general approach is then applied to several other structures to obtain optimal (or near optimal) space bounds while.
Keith J. Worsley, Dept. of Mathematics
and Statistics, McGill University
The geometry of random images in astrophysics and brain mapping
The geometry in the title is not the geometry of lines and angles but the geometry of topology, shape and knots. For example, galaxies are not distributed randomly in the universe, but they tend to form clusters, or sometimes strings, or even sheets of high galaxy density. How can this be handled statistically? The Euler characteristic (EC) of the set of high density regions has been used to measure the topology of such shapes; it counts the number of connected components of the set, minus the number of `holes', plus the number of `hollows'. Despite its complex definition, the exact expectation of the EC can be found for some simple models, so that observed EC can be compared with expected EC to check the model. A similar problem arises in functional magnetic resonance imaging (fMRI), where the EC is used to detect local increases in brain activity due to an external stimulus. The famous Nash Embedding Theorem helps us to extend these ideas to manifolds, so that we can detect changes in brain shape via structure masking, surface extraction, and 3D deformation fields. Finally, we look at some curious random fields whose excursion sets are strings, and we show using the Siefert representation that these strings can be knotted.