ECE Research Seminar Series: Recreations in Coding Theory

The Electrical and Computer Engineering department will be hosting a seminar featuring Dr. Clifton Williamson, Founding Engineer at Pure Storage, Inc. The title of the seminar is Recreations in Coding Theory.

Abstract

The study of error correcting codes requires knowledge of areas that had been traditionally regarded as "pure mathematics". For instance, the theory of finite fields is fundamental to an understanding of the codes traditionally used in digital storage devices. In a sense, many results in coding theory are an application of pure mathematics.

In this talk, we will solve two interesting mathematical problems using ideas from coding theory. While the solutions are "novel", "elegant", and "beautiful", the problems themselves are of little, if any, practical value. Thus, we will have applied coding theory to produce results in pure mathematics!

The two problems are the Hats Problem and the 12 Coins Problem. The problems are stated below as a challenge to the attendees.

The Hats Problem
In the Hats Problem, a team of 3 "players" works together in an attempt to win a "game". Prior to the game, the players are allowed to communicate and are given time to devise a strategy for playing the game. Once the game is in progress, there is no communication among the players. At the start of the game, each player is given a hat of a randomly chosen color, either Orange or Indigo. The players can see the colors of the other players' hats, but do not see the color of their own hats. Each player must then either guess the color of his/her hat or "pass", i.e. decline to make a guess. (Again there is no communication among players: no player hears another player's guess/pass!) If at least one player correctly guesses his/her hat color and no player makes an incorrect guess, the team wins the game. If one or more players make incorrect guesses or if no player makes a guess, the team loses the game. The object is to devise a strategy that maximizes the probability of winning the game.

Here is one possible strategy: one player is chosen and will randomly guess a hat color, based on, say, a coin flip. The other 2 players will pass and remain silent. This strategy will win 1/2 the time. See if you can devise a strategy that will win 3/4 of the time. In the talk, we'll look at the case of 7 hats and will show a strategy that will win 7/8 of the time. (The strategy is quite general, for N = 2^n - 1 hats, there is a strategy that will win 1 - (1/2)^n of the time.)

The 12 Coins Problem
You are given 12 coins, one of which may be counterfeit. All genuine coins have the same weight, but counterfeit coins have a different weight, which may be either lighter or heavier than a genuine coin. You are also given a balance for comparing the weights of two sets of n coins: the balance will either tell you the two sets have the same weight or will tell you which set is heavier. You are allowed to use the balance 3 times and must determine if * the coins are all genuine, or * there is exactly one counterfeit coin, in which case you must identify the coin and tell whether it is heavy or light.

Background
The talk uses the theory of Hamming Codes. The necessary results will be developed during the talk: no prior knowledge of coding theory is required!

Speaker's Biography

Clifton Williamson holds a Ph.D. in Mathematics from the University of California, Berkeley, his research focusing on computational number theory and symbolic computation. After completing his doctorate, he joined the computer algebra group at IBM Watson Labs, where he worked on the AXIOM computer algebra system. Following post docs at Cal Poly and ETH Zurich, he began a career in magnetic storage, designing error control systems at Seagate, Agere, LSI, and Proton Digital Systems. Since 2013, Williamson has worked at Pure Storage, as a digital designer responsible for the LDPC coding system in the FlashBlade storage array.

Williamson continues to be interested in education, whether it be hosting Math Day at a local middle school or giving talks at private companies and universities. He is the brother of Geoffrey Williamson, Associate Dean for Analytics for Armour College of Engineering, Professor of Electrical and Computer Engineering, and Duchossois Leadership Professor at IIT.