Mr. Johan Chrisnata, recipient of ISITA 2020 Best Student Paper Award
Johan Chrisnata, a PhD student in the Division of Mathematical Sciences at SPMS, has won the Best Student Paper Award at ISITA 2020 (International Symposium on Information Theory and Its Applications), a leading conference on information theory.
Mr Chrisnata’s winning paper, “Optimal Reconstruction Codes for Deletion Channels”, was written with Assistant Professor Kiah Han Mao, a faculty member at SPMS, and their collaborator Associate Professor Eitan Yaakobi from Technion University in Israel. It concerns the sequence reconstruction problem, a two-decade-old mathematical problem that has numerous applications in science and technology, including in data storage and genomics.
Originally slated to be held in Hawaii, ISITA 2020 was run as a virtual conference due to the COVID-19 pandemic. The Best Student Paper Award, selected by a committee of leading researchers in the field of information theory, is given each year in recognition of the most outstanding paper presented at the symposium with a student as the main contributor.
Overcoming the Missing Pieces of a Puzzle
Consider the following game played by three participants, named Albert, Bernard and Cheryl. Cheryl writes two different messages, ‘010’ and ‘101’, with each message consisting of three binary digits, and places each message in an envelope. Albert and Bernard then randomly open one of the two envelopes, without Cheryl knowing which envelope they chose.
Suppose the message in the chosen envelope is ‘010’. Instead of revealing the entire message to Cheryl, Albert removes the first 0 and informs her of the truncated message ‘10’. Similarly, Bernard removes the last 0, and tells Cheryl that the remainder is ‘01’.
In this case, it is impossible for Cheryl to figure out which envelope Albert and Bernard chose. Why? Suppose they had opened the envelope with ‘101’. Albert removes the last 1 and Bernard removes the first 1, and they would provide Cheryl with the same two incomplete strings as if they had opened the other envelope.
On the other hand, if Cheryl had used a different set of three binary digits, such as ‘011’ or ‘110’, she would have been able to determine the chosen envelope by a process of elimination. (We leave it to the interested reader to figure out how.) No matter which envelope Albert and Bernard choose, Cheryl would be able work out their choice using only the incomplete messages provided by them.
Cheryl can do even better! Cheryl can place six different messages, ‘000’, ‘001’, ‘011’, ‘100’, ‘110’ and ‘111’ into different envelopes and always work out the envelope (out of the possible six). By checking all possibilities, it can be shown that six is the maximum number of distinct messages that Cheryl can decode in this way.
Mr. Johan Chrisnata and Assistant Professor Kiah Han Mao
The question then arises: what is the maximum number of messages Cheryl can handle if the message is longer – not just three binary digits, but a larger number of digits, N?
In the paper written by Mr. Chrisnata, Assistant Professor Kiah, and Associate Professor Yaakobi, an almost-complete solution to the puzzle is provided for any number of digits.
Implications for Computer Storage Technology
The message reconstruction problem has deep implications for the storing of information in digital media.
Think of the message Cheryl puts into an envelope as a digital file written into an information storage medium, like a hard disk. The other two participants, Albert and Bernard, correspond to devices that are subsequently responsible for reading the file. The devices are not perfectly reliable, so the information they return is incomplete. From the puzzle, we see that the original file can be cleverly reconstructed in spite of the incomplete read-out. Reconstruction schemes of this sort are the subject of coding theory, an area of mathematics used extensively in the design of computer storage devices.
In classical coding theory, it is usually assumed that there is only one noisy read-out (i.e. only Albert providing an incomplete string for Cheryl to decode). However, various emerging storage technologies can provide multiple cheap reads, hence the scenario with two agents, Albert and Bernard.
The challenge, therefore, is to determine whether the multiple read-outs can be leveraged to make the information reconstruction more reliable and efficient.
The research by Mr. Chrisnata, Assistant Professor Kiah and Associate Professor Yaakobi shows that the answer is yes: Cheryl can place many more messages in the envelope than she otherwise could. Their paper quantifies exactly how much the improvement is. In the future, this result may help improve the reliability and capacity of computer memory storage.