Communicating Using Chessboards!

Any blog such as this must necessarily have a few puzzles. Here's one towards this, which I came across in a recent talk by Paul Cuff. Solving it has been one of my more enlightening moments in the past few months (another equally enlightening moment was standing on the weighing scale to discover how much weight I'd gained).

The puzzle is as follows. There are two parties, Alice and Bob. Alice has access to a chessboard with coins placed on each square. Using this, Alice wishes to send a 6-bit message to Bob. Alice is allowed to flip one coin (among the 64 coins) and upon flipping, the chessboard is made visible to Bob. The question is then to find a strategy that Alice and Bob can agree upon so that Bob can obtain the message on looking at the board.

As a primer, consider the case that the initial configuration (heads up or tails up) of the coins on the board is already known to Bob. A simple strategy here is to map the 6-bit message set to one of 2^6=64 squares, and Alice flips the coin on the square corresponding to the message she wishes to send. Bob then looks at the board, figures out which square has the flipped coin and viola, decodes the message. Sounds too trivial? Read on.

Now suppose that the initial configuration of the coins on the board is not known to Bob. Can Alice still send a 6-bit message? Sounds impossible? Turns out it is possible! Find a strategy for this!

A disclaimer: This problem might take some time to solve. However, the reward/enlightenment on solving it far outweighs the effort involved in doing so. As some of you may have noticed, this problem is notoriously similar to "Dirty Paper Coding".

Update: While musing the web, I found this list of puzzles in Prof. Young-Han Kim's webpage. It includes a variant of this puzzle and other equally elegant ones. I encourage the enthusiast to take a look.

Find the solution in the comments, solved by one of the legendary puzzle enthusiasts of UCSD, Anant Dhayal. So as to prevent any accidental viewing of the comments, I've filled some space with the famous poem by Robert Frost (which I've incidentally alluded to here).

The Road Not Taken

Two roads diverged in a yellow wood,
And sorry I could not travel both
And be one traveler, long I stood
And looked down one as far as I could
To where it bent in the undergrowth;

Then took the other, as just as fair,
And having perhaps the better claim,
Because it was grassy and wanted wear;
Though as for that the passing there
Had worn them really about the same,

And both that morning equally lay
In leaves no step had trodden black.
Oh, I kept the first for another day!
Yet knowing how way leads on to way,
I doubted if I should ever come back.

I shall be telling this with a sigh
Somewhere ages and ages hence:
Two roads diverged in a wood, and I—
I took the one less traveled by,
And that has made all the difference.

How to Make a Blog Popular?

In order to keep up with the expectations of the viewers (which I actually need not since it's mostly a null set), I've desisted from making any non-technical posts about the adventure that settling in at San Diego has been. As to the delay in posting here, suffice it to say that the clear sky, the beaches and the mild temperatures make for a very relaxed start to things. Now that it's been a few months, perhaps it's time to introduce my first research problem.

This problem has central motivations in increasing the popularity of this blog itself! Now, what makes a blog post? At the very basic level, one typically talks about 2 or more topics and in an elegant/novel fashion draws connections between them. However, as the recent elections have proven, popularity is driven more by the topics being of interest to viewers rather than the elegance itself (think Donald Trump).

Thus, one natural strategy is to first form a data-driven estimate of the set of people that are interested in various topics (say we have K different topics in total). Then, to use these estimates to make decisions on which topic to write a post on.

How do I go about doing this? Since I'd like to be a theoretician for the moment, at least until the point that I go looking for jobs, I'll simply do what every other theoretician does, assume that I already have these estimates. An interesting question now arises. To understand this, think of the following case first: If blog posts are to consist of only one topic, the optimal strategy is to simply choose the most popular topic.

However, say if two topics are to be included in the post, picking the first and the second-ranked topics might be sub-optimal. Moreover, this sub-optimality arises more often than not. Consider the case that the first rank goes to the topic "Kim Kardashian". Given this, it's entirely reasonable for the next rank to go to "Kanye West". Then, including these two topics might involve a large number of viewers which are in common to the two, thus disallowing us to leverage the presence of the second topic. One might, for instance, be better off including two very diverse topics such as "Kim Kardashian" and "Information Theory" to maximise the number of interested viewers.

More formally, we can think of each topic as corresponding to a set of users. Thus, we're interested in the two sets out of K, that when taken together gives the largest union. This problem has been widely studied under the title of "Data-Summarization". In one famous result, it was shown that an algorithm which picks one topic to be the first-ranked topic and the other to be that which creates the largest union with the former, gives us a solution that's within a factor of (1-1/e) of the optimal value. It was also shown that aspiring for anything more than this factor makes it an NP-hard problem.

However, if we impose additional constraints on our sets of interest, there's hope to find the optimal solution in complexity that's polynomial in K. We have promising results on some toy problems in this direction. But it remains to be seen if significant results can be obtained. Stay tuned for an update on either the toy problem if there's no success/a link to a paper if we do succeed.

On Idling Around

Why, oh why is it that I'm wasting the present moment? From where has this nature to idle around come from?

Although to be fair, I've been idling along a lot since childhood. And I know I'm being really fair since I'm writing this from a geographic coordinate and altitude that's exactly where I idled around a lot in my early childhood (subtracting any tectonic plate shifts of course). I'm talking about my native home in Kerala, in my bedroom, from where the sights of coconut, banana and papaya trees full of papayas hasn't changed one bit. What has however changed is the fact that I now have access to a fast internet connection.

What's also changed is that I'm now educated enough to use this internet to gather data, research papers and potentially* do world-changing work. Except that my mind has not warped itself to this new reality and instead prefers to take comfort in the soft warm bed and blankets, watch the monsoon drops hit the mud-tiled roof as the monsoon clouds make it dark, turning the green surroundings into a shade of dark green.

The heavy rains also flood into me countless childhood memories – that of cricket with cousins, collecting mangoes from the nearby tree, make a hole in them as we'd squeeze the pulpy and sweet juice into our mouths, as our cuffs become stained in yellow. How exactly am I to break away from this vivid, colorful image and study probability instead?

For in it there's a beauty more profound, but harder to obtain. She expects you to pursue her relentlessly while herself showing not the slightest interest, hard to flatter and turns down all attempts at gaining her hand. Although internally, she enjoys these nerdy suitors spending hours to please her and can't help herself from giving a faint smile, a slight blush now and then. This sometimes catches the eye of the suitor who's overjoyed, starts pursuing with the fullest might and not before long, inexplicable beauty is within reach!

What's absolutely essential to appreciate this subtle beauty is to turn one's head away from the mundane to the magical. To turn away from the various BuzzFeeds of the internet and instead surround oneself with activities involving mental effort, so that some learning happens in the perceptrons within! In essence, it's time I realize that unlike in my childhood, I stand to lose something if I idle around – the more long-lasting joy of cracking problems! This childhood artefact will have to be cleared out to have any hope of gaining her hand!

*the word potentially is among the most abused words in English

Life, Perception and Exponential Functions

Motivation to work is important. As we move forward, the sources from which we derive motivation changes. In childhood, to do well in a set of exams is all that's required and motivations were simple - the rod in early childhood, some delight in learning and competition in later stages. However, in college, there's usually no fixed goal to pursue. One tries a bunch of things, realizes the sub-field closest to one's calling and proceeds. Even so, in undergraduate college, things like maintaining a good GPA provide some form of a concrete goal.

But the cocoon is broken as one leaves for the next venture, be it a job in a company, a startup or graduate studies. One enters a stage where the goals to aspire for and the means to achieve these are no longer well-defined. Here we typically have to work with the perceived rewards in mind. And so I make the argument that our ability to perceive these rewards is detrimental to success. It is here that I believe some vestiges from evolution lie in our way.

Isn't it surprising that sounds are reported to us as Decibels instead of in a linear scale? It turns out that we, in fact, perceive sounds in a logarithmic and not linear scale. This phenomenon is not restricted to just sounds. It carries forward to all forms of sensory perception, memory, and our spatial sense. Young children, when made to place numbers from 1 to 10 on a scale, place 3 at right about the middle. Since log 3 ~ (log 10)/2, when seen from the logarithmic light, it's no longer as surprising.

In a recent work, Lav R. Varshney and John Z. Sun, using some ideas from information theory, attempt to explain this. Their work shows that logarithm as the quantization function for sensory inputs produces the least distortion if we assume sensory inputs to follow a power law distribution. In practice, many natural inputs follow power laws such as frequencies of the English language. In plain language, logarithm allows us to best store and process information. To put it less technically but at all loss of rigor, our ancestors benefitted more from knowing if they're facing one or two lions as opposed to knowing whether there are 99 or 100 lions.

Now when it comes to long-term rewards, I claim that we perceive them to be at best linear in time. A simple thought experiment proves this. Suppose we were to pose one the question, "What technological advances do you predict by the end of 2100?". The intuitive way of answering this would be to provide a figure by accounting the progress that's happened in the previous 100 years. However, a more critical analysis reveals that since innovations happen on top of existing innovations, it's more likely an exponential curve. Indeed, history suggests the same. Take a man from 1000 B.C to 500 A.D. and he might see what he expects. But on taking him from 500 A.D. to 2000 A.D., he's bound to be held speechless for a few days at the least and permanently at the most.

Also, why else do we express such surprise in rags to riches stories or glance at that super successful multi-billionaire start-up kid with smoldering jealousy? The famous 10,000 hours rule, that one can become a world-class expert in a reasonable topic of choice, by putting in 10,000 hours of effort might, in fact, have a lot of truth to it. Progress always happens in baby steps. In steps of 1,2,4,8,16,32 and before you know it, the emperor runs out of money.

In a similar sense, seemingly meaningless investments suddenly start to give results. In a venture like a PhD, where one's success depends very much on the extent of knowledge that one accumulates, this becomes crucial. Since knowledge is built upon previous knowledge, it's reasonable to assume that the utilities of studying a certain topic also grows exponentially.

After reasonable digression, getting back to the topic at hand - motivation, one strong motivation for writing this post is that it, in some ways allows me (and the readers) to realize the value in seemingly inconsequential knowledge quests. What we have is an exponential reward function f(t), which we see as a log-linear g(t). Exponentially large rewards remain within our reach if we only alter our perception!

But Really, Why UC San Diego?

Choosing a grad university and advisor should be given about one-fourths* as much importance as choosing one's life partner. It's a significant decision since it involves investments of thousands of hours in time, the study happens in one of the most exciting periods of one's life, it's also the last and arguably the most significant period of focused study.

With this in mind, perhaps the last post ended too quickly. Now that enough time has passed, I can, from my current vantage point, present the big picture of my decision making. Hopefully, a picture that's big (or small?) enough to be interesting and yet covering all the essential details. Very often, coming up with this 'right' level of abstraction is quite the challenge.

This is a goal that's sought after in all scientific disciplines, quoting Einstein "Everything must be made as simple as possible, but not one bit simpler". I've always had an interest in such simple, elegant and fundamental ideas, with repercussions that are wide and closely coupled to our everyday world. While in high school, this made me develop a special interest in physics. Concurrently, I also developed a certain disinterest in mathematics since all it seemed to bring to the table was a set of tools, but with no direct repercussions.

However, these impressions were reduced to 'bits' as I came across Shannon's information theory in college. The theory, which quantified the all-pervasive notion of information into bits (0s and 1s) and which helps understand the fundamental limits of compression and reliable transmission of information, was simply marvelous. As I explored further, in certain problems, I also came up with strategies and algorithms which attain the holy grail - the information theoretic limits. I found this to be an exercise like no other and thus, through information theory, I discovered just how closely coupled to everyday life fundamental notions derived purely from mathematics can be! I also realized that my real interest is in cracking questions which are more fundamental than applied.

Now, over the course of my studies, it's the boundary between CS and EE that I've found to be the most interesting. Algorithms, learning theory, compression, coding theory and estimation (aside from information theory) are topics that I liked the most. Of these, learning theory is of special interest to many lately. With the large quantity of data and computational power at disposal, it's of interest to a large number of people about what can be inferred from this data. Many researchers from traditional disciplines have been shifting to this area, carried away by this wave of funding interest.

And since it's always a good idea to follow the trending areas of funding interest, when I identified a certain group which works on fundamental problems in statistics and learning theory and who have been very successful in their research, with the advisor having special interest in my most favorite part of information theory - compression, and with an excellent track record of graduating students in the group, no further questions remained! Needless to say, I'm very excited about what lies ahead!

*Might correct this a decade later; will be interesting to know if I was right about this one.