Encoding Proofs

Various fields have various notions of "nice proofs," be they combinatorial, or elementary, or bijective. In TCS, perhaps the correct standard for lower bound proofs should be "encoding proofs." In these proofs, one starts with the assumption that some algorithm exists, and derives from that some impossible encoding algorithm, e.g. one that can always compress n bits into n-1 bits.

A normal lower bound will have a lot of big-bad-ugly statements -- "there are at least A bad sets (cf Definition 12), each containing at least B elements, of which at most a fraction of C are ugly (cf Definition 6)". To deal with such things, one invokes concentrations left and right, and keeps throwing away rows, columns, elements, and any hope that the reader will not get lost in the details.

There are 3 huge problems with this:

1. Most lower bounds cannot be taught in a regular class. But we can't go on saying how problems like P-vs-NP are so awesome, and keep training all our graduate students to round LPs better and squeeze randomness from stone.
   
   
2. The reader will often not understand and appreciate the simple and beautiful idea, as it is too hard to pull apart from its technical realization. Many people in TCS seem to think lower bounds are some form of dark magic, which involves years of experience and technical development. There is certainly lots of dark magic in the step where you find small-but-cool tricks that are the cornerstone of the lower bound; the rest can be done by anybody.
   
   
3. You start having lower-bounds researchers who are so passionate about the technical details that they actually think that's what was important! I often say "these two ideas are identical" only to get a blank stare. A lower bound idea never talks about entropy or rectangle width; such things are synonymous in the world of ideas.

Proofs that are merely an algorithm to compress n bits have elegant linearity properties (entropy is an expectation, therefore linear), and you never need any ugly concentration. Anybody, starting with a mathematically-mature high school student, could follow them with some effort, and teaching them is feasible. Among researchers, such proofs are games of wits and creativity, not games involving heavy guns that one may or may not have in their toolkit.

***

My paper on lower bounds for succinct rank/select data structures was submitted to SODA in extraordinary circumstances. I had been travelling constantly for a month, and the week before the deadline I was packing to move out of California and down with a flu. In the end, the only time I found for the paper was on an airplane ride to Romania, but of course I had no laptop since I had just quit IBM. So I ended up handwriting the paper on my notepad, and quickly typing it in on my sister's laptop just in time for the deadline.

[ You would be right to wonder why anybody would go through such an ordeal. I hate submitting half-baked papers, and anyway I wanted to send the paper to STOC. But unfortunately I was literally forced to do this due to some seriously misguided (I apologize for the hypocritical choice of epithets) behavior by my now-coauthor on that paper. ]

If you have 8 hours for a paper, you use all the guns you have, and make it work. But after the paper got in, I was haunted by a feeling that a simple encoding proof should exist. I've learnt long ago not to resist my obsessions, so I ended up spending 3 weeks on the paper -- several dozen times more than before submission :). I am happy to report that I found a nice encoding proof, just "in time" for the SODA camera-ready deadline. (As you know, in time for a camera-ready deadline means 2 weeks and 1 final warning later.)

The paper is here, if you are interested.

Nobels

Since we've been talking about prizes, let me mention the recently announced Nobel awards for 2009.

In Physics, half the prize goes to two retired researchers from the old Bell Labs, Willard Boyle and George Smith. According to Wikipedia, this is the 7^th time the Nobel prize is won for work done at Bell Labs.

Of course, the Lab is not what it used to be. After the famous AT&T/Lucent split of 1996, AT&T Bell Labs split into Lucent's Bell Labs (currently in a somewhat precarious state), and AT&T Labs, Inc. AT&T Labs experienced massive corporate pain at one point (famously firing an entire machine learning group in one shot), but currently appears to be in good shape (for instance, two machine learning researchers from AT&T were in the team that won the recent Netflix Challenge).

Of course, there is no active Physics research going on today, so the Nobel is only about past glory. But could the Labs win a Turing award for current work? Possibly, although it's certainly not a top contender. At least some baby steps are being taken to turn this place back into a real research lab: Howard Karloff recently bought a ping-pong table.

***

In other news, Herta Müller won the Nobel in literature. She is a Romanian-born Banat Schwab (a German ethnic group in Romania and Serbia). She lived the first 34 years in Romania, and later emigrated to Germany in 1987. Her work focuses on the harsh life under Romanian communism, and so she was not allowed to publish freely before leaving Romania.

In Romania, her work is essentially unknown -- as you might imagine, we have enough Romanian-language authors writing on the same topic, some of which are unquestionably very good.

Follow-up

My previous blog post generated a record number of comments (74 as I write this). Of course, this is not necessarily something to write home about, but I am proud that we might have passed the threshold of 5 intelligent comments to a post.

I pulled away from it due to some travel (which was a good idea anyway), so let me get back with some follow-up observations.

1. Michael Mitzenmacher discussed the post, and the comments there are quite interesting (or depressing, depending on your point of view). I have always said that TCS is headed for bad trouble given how we educate the current generation of students. We will end up with a batch of researchers who have never heard of 90% of the problems at the intersection of TCS and the rest of CS, who successfully turn our discipline into philosophy while day dreaming about turning it into pure mathematics.

As you may see among the comments, there are people who have actually never heard of those problems, yet are fully confident in their comprehensive understanding. When faced with commentators who actually like the problems, there are only two logical conclusions open to them: these guys are either insane, or Mihai himself (two possibilities that are not mutually exclusive, of course).

Now, one cannot take conclusions based on blog discussions too seriously. But I will volunteer anecdotal evidence from a talk at Weizmann: when I asked who knew what a "Voronoi diagram" was, a few sporadic hands came up. (Go try this at home!) The problem: Weizmann is an excellent school, educating many of our future colleagues.

2. Some people asked whether I would have gone to UCSD, had they made me an offer first. This is impossible to tell. I was certainly considering it wholeheartedly, but I didn't even have the answers from all places at the time, so I cannot know how my opinion would have evolved.

Many commentators seem to have missed that the post was about psychology, not logic. I did not explain how (1) UCSD made an offer to Costis implied (2) I rejected UCSD; I explained my perception of (1). Indeed, you are missing some facts that contributed to "(1) implies (2)," at least some of which are not appropriate for blogs --- even by my unorthodox standard.

3. Another thing that I did not comment on (except inside some people's minds) was the work of Costis. If you want to hear his work being put down, you really don't need me; tune in to the appropriate non-blog channels and I can guarantee you won't be disappointed. (This is to be expected for any person who achieved some degree of notoriety at early age, and perhaps got more hype than he had bargained for.)

In fact, my opinion is quite the opposite: I find Costis to be a very deep thinker, both technically and meta-technically. We repeatedly went for beers and I can report no significant disagreements were found, in spite of liberal comments during said encounters :). For example, due to my algorithmic sensibilities, it is quite clear that I consider the complexity of computing Nash to be very important (it is a concrete, central, and structurally-interesting algorithmic question).

4. Many negative comments were knee-jerk reactions, fully reflecting people's frustrations and insecurities. In the US culture, it would be customary to apologize for insulting people's sensibilities (I never figured out whether such apologies are interpreted as sincere, or they are merely correct protocol). Of course, things are rather different in my own culture, and it has never been my priority to tread lightly. So let me offer the typical Romanian advice in such circumstances: "Don't worry; life may be hard, but it passes quickly."

5. Some more commentators found it hard to accept my comments given "my position" (whatever they interpreted my position to be). The most constructive of them told me to look at Hamming's well-known speech so that I may learn "how it is possible to get the considerable benefits of egotism without needlessly pissing people off."

I find this particularly funny, since I once learned the position of a great information theorist, a contemporary of Hamming. It was roughly "Eh, Hamming... He's just arrogant, he never had any really good results."

This reminds me of something that a friend told me a long time ago: "the most crucial ingredient in the greatest paintings is the light bulb in the room; even the work the best painters is quite dull in a dark room."

If you find that your point of view doesn't allow you to see what is being said, perhaps you can try another one temporarily.

5. Finally, let me respond to somebody who seems to write politely and in good faith:

I was on a hiring committee in one of these schools that decided not to interview you. Although I hesitated to post this comment, I think what I have to say will be helpful to your career.

Thank you for the comment; I appreciate the difficulty in writing on such a topic.

The reason we decided against further considering your case was because of your reputation as a very difficult, arrogant, and opinionated person. We even read your blog and found many posts that confirmed this reputation.

I am aware that suggestions of this form were made. Of course, I may point out the significant pitfalls in searching for evidence (in a blog, of all places) for something that you are already biased to believe. I may also point out that the places that actually know me (the labs were I did internships) both made me offers, and a notable fraction of the universities where I interviewed were also interested in hiring me. So the suggestions may be a bit exaggerated, or perhaps there is a high variance in how people perceive me. If for some reason your university finds itself interested in my case, I would consider a conversation at a conference or an invitation for a talk as more reliable courses of action.

At least in our university, a post like this one significantly hurts your chances of getting a job. We don't want to hire a person who writes a blog post insulting their departmental colleagues every time they're not nominated for a fellowship or an award. "I can't believe my department decided to nominate X for a Sloan Fellowship when my research is so much deeper than X's."

If your department has no faculty engaging in the common activity of "bitching and moaning," I am not sure whether I should envy you for your luck, or worry about the hyper-formal environment that you may have in place. It is safe to say that I am not good at keeping rank formation; but it is also fair to say that I choose the battles where I pull out of the formation very selectively.

You're smart, but there are *many* (equally) smart (or smarter) people who are also publicly nice.

It is my hope that I will prove you wrong on this statement.