A week on coding and information
Day one
Today is the first day of the Latin American Workshop on Coding and Information, a satellite event of the celebrated International Congress of Mathematicians which will be held in Rio de Janeiro on August (you know, Fields medals and stuff). The workshop is devoted to discussing questions of mathematical foundations of secure and reliable data storage and transmission, including applications to the quantum world, cryptography, and biology.
How to solve a sudoku effectively?
The first lecture was given by Prof Daniel Panario (Carleton U) on finite fields an applications. Finite fields are arguably one of the finest fields of mathematics (see what I did there?). They can be regarded as one of the purest areas of mathematical knowledge and, at the same time, are in the foundations for digital communications and modern cryptography. Indeed the recent story of finite fields has a huge correlation with core technological developments of the 20th century and, as such, they are an indispensable part of the education of any applied mathematician and computer scientist.
In the Finite Fields world, we can only operate with a finite number of elements (wait, isn’t it always the case in the digital world?), and the name of the game is how to make arithmetical operations consistent (weird things may happen with arithmetics, such as the Freshmen’s dream). The obvious examples of Finite Fields are Boolean fields (where only the elements {0,1} are allowed), but it doesn’t stop there — virtually any combinatorial problems can be turn into finite fields. Prof Panario explained some of them, including how to share a secret key throughout a compromised link, relations to combinatorial designs and how to solve sudokus with Latin squares (which unfortunately have nothing to do with Latin America, as patiently explained Prof Panario after my embarrassingly out-of-scope question).
There are still beautiful open problems in this well-established field. A top example is the Prime-Power conjecture on the existence of certain latin squares, where brute force computational methods fall short.
That’s IT
For the second lecture of the day, we have been awarded with a well-paced, self-contained talk on the foundations of Information Theory (IT) by Prof Max Costa (U of Campinas, IEEE Life Fellow). The lecture started with the definition of (Shannon) entropy to measure the uncertainty of a random variable. Indeed, the entropy can capture the nature of a random variable in the high dimensional regime. For instance a random variable is always concentrated almost uniformly around a set of volume dictated by the entropy. This concept is crucial, for instance, in hypothesis testing.
Proceeding on the concepts of conditional entropy, Prof Costa discussed the problems with drawing conclusions from marginalised distributions. One should exercise great care with marginal distributions so as not to fall into traps such as Bertrand’s box paradox.
Further down the road, Information Theory can provide powerful tools for analysing data dependent systems. Some ubiquitous examples are the Data Processing inequality, Fano’s inequality and Jensen’s Inequality. If you happen to have missed Prof Costa’s talk and don’t know these, you might be in need of an IT book (NB: entirely free advertising).
With these tools, along with coding techniques, one can essentially derive all important results that establish the ultimate limits of point-to-point data transmission and storage. The case of multiple users is significantly harder, and is the topic of Prof Costa’s second lecture on Tuesday…
For the second part of school, click here.
NB: Claude Shannon’s recently released biography includes testimonials by true information theorists and is a must to get familiarised with the story of the field.