Hamilton Day 2012
The 2012 Hamilton Lecture, ‘'Silver lining, codes and clouds: Error-correcting codes, their asymptotic bounds, and Kolmogorov complexit', was delivered by ProfessorYuri Manin
Abstract
An error-correcting code C over a given finite alphabet A is simply a set of words of some fixed length n of which one can think as ‘meaningful’ ones, such as Morse code for letters.
When such a code is used in practice, some input data are translated into a sequence of code words that are then transmitted through a channel with random noise.
There arises a problem: at the output end the initial words must be reconstructed from corrupted words. ‘Good codes’ are those that maximize simultaneously the probability of correct reconstruction and the relative quantity of meaningful words.
In 1981 the author defined and proved the existence of the so called ‘asymptotic bound’: a continuous curve that in a sense determines the boundary for possible good codes. But not a single value of this function is known, and in 2011 the author even conjectured that it might be uncomputable.
In this talk, he sketched all the relevant techniques and a proved the recent result (2012, joint with M. Marcolli) showing that a natural partition function involving Kolmogorov complexity allows us to interpret the asymptotic bound as a curve dividing two different thermodynamic phases of codes.
Speaker Biography
Born 1937. M.Sc., University of Moscow 1958. Ph.D. (Candidate of physical and mathematical sciences), Steklov Mathematical Institute of the Russian Academy of Sciences, Moscow, 1960. Habilitation, Steklov Mathematical Institute, Moscow, 1963. Principal Researcher, Steklov Mathematical Institute, 1960-1993; since 1993 Principal Researcher in absentia. Professor (Algebra Chair), University of Moscow 1965-1992. Professor, M.I.T. 1992-1993. Scientific Member, MPI for Mathematics since 1993. Director, MPI for Mathematics 1995-2005, now Professor Emeritus. Board of Trustees Professor, Northwestern University (Evanston, USA) 2002-2011, now Professor Emeritus. Lenin Prize 1967. Brouwer Medal 1987. Frederic Esser Nemmers Prize 1994. Rolf Schock Prize in Mathematics 1999. King Faisal International Prize in Mathematics 2002. Georg Cantor Medal 2002. Order pour le Mérite for Science and Art, Germany, 2007. Great Cross of Merit with Star, Germany, 2008. János Bolyai International Mathematical Prize, Hungarian Academy of Sciences, 2010. Member of nine Academies of Sciences. Honorary degrees at Sorbonne, Oslo, Warwick. Honorary Member of the London Math. Society.