ECE Research Seminar Series: Recreations in Coding Theory

The Electrical and Computer Engineering department will host a Recreations in Coding Theory seminar featuring Dr. Clifton Williamson, Founding Engineer at Pure Storage, Inc.

Abstract

Studying error-correcting codes requires knowledge of areas traditionally regarded as "pure mathematics." For instance, the theory of finite fields is fundamental to understanding the codes traditionally used in digital storage devices. In a sense, many results in coding theory are applications 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 have 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 to win a "game." Before the game, the players are allowed to communicate and are given time to devise a game strategy. Once the game is in progress, the players have no communication. 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 hats. Each player must then 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 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 show a strategy to 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 lighter or heavier than genuine ones. You are also given a balance for comparing the weights of two sets of n coins: the balance will tell you whether the two sets have the same weight or which is heavier. You are allowed to use the balance 3 times and must determine if * the coins are all genuine or * if there is exactly one counterfeit coin; in this 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 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.