Wednesday, 28 June 2017

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".

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.

Friday, 17 February 2017

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.

Wednesday, 17 August 2016

My Journey and Thoughts on 'Apping'

As I'm about to embark on this journey, and especially just after the convocation, there's a feeling of wanting to share my experience with those who might similarly be interested pursuing a Ph.D. I start with this reference - DAGAP since I can't do a better job at comprehensively covering the application process. I strongly urge those interested in applying for an M.S./Ph.D. to read this - it's well worth the time spent.

A topic such as this just can't be very poetic. If instead, it's something poetic that you're looking for, let me point you here. In the remainder of this post, I'll talk a little about my journey, some common mistakes I think an aspiring undergraduate makes and some advise based on what helped my own application.

My journey largely began with this decision, of choosing to major in EE at IIT Bombay. The motivation for EE stemmed for an intense liking for physics, and with the impression that EE has more to provide in this respect than CSE (I wasn't considering majoring outside these two departments). However, I was in for a disappointment. I realized that in the subjects that I thought to involve a lot of physics, such as solid state devices, were taught without enough rigor. To really understand them required one to do several courses in physics that were outside the standard EE curriculum and would so require a lot of additional effort to do. To add to the disappointment was that I, in fact, liked many of the CSE courses more.

Just when things were looking down, I finally found the first course that I liked at the end of my 2nd year. It was the course - "Signals and Systems" and I decided that areas surrounding the subject are worth serious exploration. This leads to the first mistake that I'd like to talk about - Not speaking to professors! Professors are actually fun people to talk to! Many of us, partly because of our upbringing in school imagine Prof. Snape to be the archetype of every professor. Perhaps a lesson to be learned from Harry Potter is to not wait till one's 7th year in college to really find out about him/her! This hesitation on my part to speak to a certain professor until it was too late cost me a great internship opportunity. It's essential to grow out of this cocoon, which many students have, of shying away from speaking to professors.

As a result, the summer was largely unproductive and 3rd year, the time to start getting serious about future began. In the beginning of the 3rd year, like many other students, I had aspirations to secure an internship in a top university. One major mistake that might be made here is sending emails in bulk to professors. Now that I've interacted with many professors, I can say that most detest such insincere emails. I stuck to sending only a few but well-composed emails, i.e. after actually going through the professors' work and following a well-made email template. I had a very good rate of reply and I encourage everyone to do the same.

However, what finally clinched the internship for me was a recommendation from one of the professors at IITB to whom I would often speak to. As I'd said, networking pays! An internship at EPFL, one of the top schools in information theory was on the cards! This set the stage for most of what was to follow. At the end of the season, looking at the responses my friends received from their emails, I realised this - without a professor to back one, it's actually very difficult to secure internships even on sending sincere emails.

Don't panic! Failing to secure the internship at one's favourite university can easily be mitigated by working with the 'right' professors. Picking the 'right' professor to work with should be given about one-fourths as much importance as picking a Ph.D. advisor. Broadly speaking, a 'right' professor should be someone who's active in research, is well-known, who's friendly and who has a track record of 'sending' students to top universities (more on why later). The former two can be figured out by looking at the recent publications and the latter two by speaking with seniors.

Coming back to my own story, as many others who've been on a foreign internship might remark, it was a learning experience in many dimensions. My work was on a multi-user variant of a setup that was previously studied in the lab. Nothing ground-breaking occurred since the bulk of the time was spent on studying the problem. And so the summer, which has been my most memorable yet, rolled by, and I was back to living in the small IITB hostel room.

In my final year, there was a desire to continue working on problems that followed the summers' work. This might arguably be the best decision that I took through my undergraduate days. Having already studied related literature and acquired sufficient depth, I was able to obtain some concrete results and managed to work towards a publication by the application deadline. I strongly recommend that one works on problems that have a natural continuum and obtain publishable results. Perhaps no other attribute speaks of one's potential as a Ph.D. candidate to the admissions committee than this.

As the application deadlines started appearing on the horizon, a more technical version of this story above went into my Statement of Purpose, references were obtained from my EPFL, final year project advisors and the applications were sent out.

Now in the context of whom to take references from, I'd like to add that it's useful to obtain a reference from someone with a track record of 'sending' their students to the top universities. This is for the following reason: In general, there's a lot of variance in the references which are received by the university that one applies to. Some professors might talk about all of his/her students as being the absolute best! One effective way that the admissions committee removes this variance is by comparing one's reference to the reference that was written by the same professor for a student who's already studying in the university. And then by comparing the relative level of one's reference with how that student is currently performing in the university. Yes, they do go to such lengths!

The next semester, which was the last semester of my undergraduate journey was filled with many emotions. The application results were due in the first couple of months and every morning began with checking the phone for emails of acceptance/rejection.

The first acceptance came in from EPFL and here's something interesting - that my probability going to EPFL actually decreased on getting an acceptance from EPFL. Why you might ask. It goes as follows: I was always concerned if I did a bad job at EPFL. Hence I was concerned if the recommendation I received from the professor at EPFL said good things about me. Now, the fact that EPFL accepted me certainly meant that the professor had, in fact, given a good reference for all my other applications, which meant that I could anticipate more acceptances to follow, in turn meaning that I now have more offers to choose from as opposed to EPFL.

Then began my own decision process, of going through the research of the various groups in detail, speaking to professors, post-docs and Ph.D. students, as I have outlined in some of my earlier posts. My 'apping' effort was largely a success. I managed to secure admission for a Ph.D. to 8 of the 11 universities that I applied to. I end with this reference. It's a compilation of what current Ph.D. students at various universities (alumni of IITM) have to say about their own application experience and some advice from their end. All the best!

*I've skipped one major part of the story - about how of all courses that I explored, I found information theory to be the most interesting. This, I plan to make a post in itself, due on an unkown date.

Thursday, 4 August 2016

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 really 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. So intoxicating it is that even this article, which was to originally serve as a dreary-dry reminder that I have to work, is taking a more poetic tone.

But then if I'm to be really fair again, there's also beauty in exploring new problems and cracking them. Albeit a beauty that's more subtle and harder to obtain. She expects you to pursue her relentlessly while herself showing not the slightest interest. She's hard to flatter and turns down all attempts at gaining her hand. Although internally, she enjoys these nerdy (unlike most other girls) 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

Tuesday, 5 July 2016

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!

Wednesday, 18 May 2016

But really, why 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 Einstien "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.

Saturday, 12 March 2016

The First Leg

I've changed a lot in the past four years and my older blogs have simply become out of place. There seem to be only 40 days left at IIT Bombay and the growth that I've experienced in multiple facets is too much to describe. I've also come to realize that the nitty-gritty details associated with these growth-events, a feature of my previous blogs, are actually interesting only to me, and perhaps my closest kith and kin.

Thus, the style now is going to be a more colorful exposition, a true expression of creativity, and all the other superlatives someone who's just about to enter into a PhD might use. I imagine the coming years to be a jolly ride at La Jolla, California, but certainly with its ups and downs, an ideal testbed for my perceived 'growth' over the last few years. Indeed, the substance will be separated from the shadow.

What I intend to put down here is the PhD journey of an aspiring lad, who wishes to make some fundamental contributions. At the very least, wish to maintain the same enthusiasm over the coming five years!

Here we go! Now, the first big question is about where I should go. Having multiple offers should supposedly make life better. But that's not to be so because of the associated decision making! I'm tempted to write at lengths about the factors I should consider in choosing a university, almost mirroring every discussion I have with my peers, relatives and faculties these days.

Instead of boring both the reader and myself, I'd like to talk about two interesting ideas here. It relates to the poem "The Road Not Taken" by Robert Frost. I happen to be a big fan of this poem since it's interpreted in two different and beautiful ways. The first and most commonly held interpretation stems from looking at the following lines in isolation - "I took the one less traveled by, And that has made all the difference". Here RF seems to suggest that taking the road not taken made all the difference in his present success.

The second and more beautiful interpretation follows on reading the whole poem. One then realizes that what RF actually talks about is a bit deeper - that although he's inclined to believe that "The road less traveled" was the better path, it might well be that the other "Well worn path" led him to greater heights. RF here reasons that this tendency is actually an aspect of human fallacy where we tend to (incorrectly) convince ourselves that our current situation is the best, disregarding where the other paths may have led us.

The poem then ends with a tone where he finally concedes to this fallacy, since he likes to take pride in having taken the unconventional path. What lies ahead of me is similar. It's on the various choices I have, and my not being able to fix on a particular university. While it'd be great to know the outcomes at the end of each path, perhaps taking the unconventional path has a beauty in itself. San Diego, here I come!