What's Your Problem?

The first time I remember asking about another graduate student's research was during a meeting with Bobak on June 25, 2004. It was Bobak's birthday, and my job was to distract him while others were setting up his surprise party. While I still have a copy of Bobak's LaTeXed writeup from that day, it didn't appear that talking to other students about their research would become a common occurrence.

Things changed once we moved into the Wong Center. In fact, during our first year there, Paolo and I developed a habit of sharing interesting technical problems that were coming out of our research on an almost daily basis. While I like to believe this frequent interaction led us to solutions faster, the real reason I did it was simple. Another person's problems offered me a welcome break from my routine, especially on days when I wasn't gaining any traction on my own problems.

As student interaction became more common, conversations started to shift away from research into areas that ranged from politics to musical preferences. While sharing our problems has declined (at least of the research variety), brain teasers have been on the rise. Many of these have been initiated by Prasad, so I thought I'd share a personal favorite from his collection.

Alice and Bob each roll a six-sided die. Each of them can only see the outcome of the other's roll. Without communicating with one another, Alice and Bob will each win a dollar if both of them correctly guess the outcome of their own rolls. If either Alice or Bob guesses incorrectly, neither wins anything. Is there a way for them to win with a probability of at least 1/6? The answer is yes, which they do by guessing the other person's die roll as their own. Note that if each of them simply guessed at random without looking at the other person's die, they would only win with probability 1/36.

Now suppose 1000 people each roll a six-sided die and observe the outcome of everyone else's roll. Without communicating with one another, they each win a dollar if all of them correctly guess the outcome of their own rolls. If any of them guesses incorrectly, none of them wins anything. Is there a way for them to win with a probability of at least 1/6?

Closed Form Expressions

This summer, I had a conversation with Baris in which I claimed ignorance about the meaning of a closed form solution. One may say an expression is in closed form if one can intuit its behavior simply by looking at it; however, this is both imprecise and subjective. Baris suggested an alternate definition that went along the following lines:

closed form solution. n. an equation that can be evaluated by a scientific calculator.

I was happier with this definition, but it was still a little unsatisfying mainly because the capabilities of scientific calculators have improved significantly over the years. What if a scientific calculator can solve differential equations or an LP? I can't intuit these solutions. Even if we accept such a definition, we would likely reject a paper titled "Closed Form Solution for [insert problem here] via Improved Scientific Calculator" for publication... or would we?

While some may disagree, computers have proved useful in helping information theorists develop intuition. For instance, Permuter et al.'s "Capacity of the Trapdoor Channel via Feedback" proves the capacity after using a computer to conjecture the solution. At a seminar this summer, Stephen P. Boyd advocated for more information theorists to adopt this pragmatic approach to problem solving.

Recently, Michael suggested MATLAB to help me gain insights about a research problem. My own intuitions were a little jumbled, and a few plots in MATLAB seemed like the best path to clarity.

Not everyone is a fan of MATLAB. Prasad told me he prefers a combination of C and gnuplot. Others are purer still. Someone scoffed at the idea that as an information theorist, I needed to resort to a computer for help.

Published in 1945, Vannevar Bush's "As We May Think" predicts a future device called the memex (memory extension), a device in many ways reminiscent of the modern computer that enables the easy storage and retrieval of one's books, communications, etc. If I can use a memex to organize my records, then I have no problem using an intuitex to organize my thoughts.

Reading the Classics

When "Reading the Classics" was first offered two years ago, the course announcement started by mentioning the Iliad. This year the facetious introduction was absent:

There are several papers in the history of science that seem to have been written with the express purpose of changing (or creating) a field. Their authors were often young, and the writing is almost always self-conscious --- and usually a joy to read.

In this seminar we shall read several such papers from computer science and abutting fields.

The seminar has been fundamentally different from other courses or reading groups in which I've participated. Although we've been reading papers by Turing, Feynman, Nash, and Shannon, we have already encountered many of the results or there consequences in some previous form. Indeed, when Christos Papadimitriou introduced the class, he mentioned that one definition of a classic is something one can only reread because by the time one reads it, it has already influenced his or her thinking in fundamental ways.

How does one reread a classic? In addition to understanding the technical aspects of the paper, its historical context is important. The context can be divided into two parts: research prior to the work and research following it. A classic sometimes alters how research is conducted, so it helps to gain an appreciation of how the research was conducted before its publication. The impact of the work complements this by giving people a sense of how research was affected by it.

In addition to the intellectual context, there are also the authors' biographies. Who were these authors? The answers have led to interesting class discussions. For instance, in last week's discussion about Nash's "Non-Cooperative Games" paper, Professor Addison, who attended graduate school with Nash, described students' impressions of Nash and also his experiences with Albert W. Tucker, their adviser. Christos, in addition to describing how his own research has been influenced by Nash's work, talked about his graduate days at Princeton, a time when Nash was known as The Phantom.

This week, we'll be discussing Claude Shannon's "A Mathematical Theory of Communication." I've already discovered a few gems on this reread and look forward to tomorrow's discussion.

Sergio Servetto

It was a few weeks into the start of the semester, and my schedule was set. As I went to the lab printer to pick up a problem set, I accidentally picked up one for ECE 445. Some problems required tools from signals and systems or probability to answer questions about quantization. The final problem was to design a primitive image compression algorithm. Although I would have to switch my schedule, I wanted to take the class. An e-mail to the professor was met with an enthusiastic response, so I made the switch.

Sergio's class was one of my favorites at Cornell. The course mixed theory and programming and made me appreciate the important role theoretical questions have in the design of practical systems. Sergio's teaching style was also one that encouraged questions. He would often pause before answering as if the question being asked were important. Even if I later realized I had said something incorrect or the answer to my question was self-evident, Servetto never sounded dismissive when he answered.

Part of the reason Sergio was able to relate with students was how comfortable he was around them. The first time I walked into his office was just after someone had brought him a freshly baked chocolate chip cookie. Without a second thought, he immediately split the cookie and handed me half. I still remember seeing one of the melted chips stretch between the two halves of the cookie and thinking what a generous thing to do.

Given my experiences in Sergio's class and others, I wanted to pursue information theory and communications after starting graduate school. Sergio and I would periodically meet at conferences. As we were catching up during ITA 2006, he mentioned that he had looked over my Master's thesis. It was great a feeling to know that one of my former professors was still interested in my progress.

Most recently, I saw Sergio at ISIT 2007. He had recently agreed to oversee the Information Theory Society Student Committee, and we talked a bit at one of their events. I last saw him among the audience at my talk.

I found out about the plane crash this evening. It is much easier to reminisce about the past than to describe how I am currently feeling. I've been fortunate to have professors like Sergio Servetto who have encouraged my interests.

I remember we tested our primitive image compressors from that first problem set on a photo of one of Sergio's sons. My thoughts are with the family.