FOCS 2010

The FOCS 2010 website is already up. This promises to be a very interesting conference.

A Simple Encoding Proof

In this post, I discuss a nice and simple example of an encoding proof, showing that maintaining partial sums require Ω(lg n) time per operation.

Go ahead and read the lecture notes in [PDF]. Or, if you prefer a more visual exposition, try the [PPTX] or [PPT] presentation. (These were extracted from my thesis and job talk.)

If you are teaching a data structures course, you should consider teaching this. (It's already done at MIT by Erik and UIUC by Jeff.) I feel it's quite improper to teach data structures without some lower bounds; this is akin to teaching algorithms without NP-completeness. Now, if you're going to teach a lower bound, this is probably the easiest you'll ever get (certainly teachable to undergrads), and it does prove something very interesting: that binary trees are optimal for aggregation-type problems.

Now, for a bit of amusing history. This result was the very first paper I ever wrote, back in SODA'04. In the fall of my freshman year, I asked a friend if there were any cool theory problems left to solve, and he suggested P vs NP as quite interesting. I googled up some useful definitions, and worked on it for several months -- unfortunately without much success :)

In the second semester, I convinced Erik to pay me to do theory research -- this is called exploitation of a confused young faculty by a freshman. Expecting that I should publish something to retain my job, I decided to work on simpler lower bound questions, which (amazingly!) were still said to be open on some internet pages. In particular, my google searches had revealed Miltersen's survey on cell-probe complexity, which said that an Ω(lg n) bound was a big challenge.

Arrogant as I am, I didn't let such things intimidate me, and I proved the bound. Of course, I hadn't heard of such things as entropy at the time, but I had learned about Kolmogorov complexity from Sipser's book, which I was reading to develop background on P vs NP. The concept was obvious: you simply count strings of length n and n-O(1), and conclude that there exist incompressible strings. Thus, my proof was in terms of incompressible strings. (A referee comment later suggested that the authors should learn the useful concept of entropy, so I read up on Wikipedia and changed the terminology in the paper.)

I then came to Erik to explain the proof (which didn't go well at all, since I was essentially just standing in front of a blackboard and saying "It's obvious!"), and to ask about writing a paper. He explained that there are these theory conferences "STOC" and "FOCS" and one on algorithms/theory with a more practical focus, called "SODA." He did not elaborate on the relative rankings of these, but he didn't have to, since the situation was obvious.

I decided to be bold and submit to "SODA." My paper was unfortunately all about theory, but it was about an important practical problem, and I had a very good lower bound for it, so maybe it would make the cut even in the top conference, which cared about practically-important research. If it was rejected, I would have to resign and just publish it along with all the purely-theoretical crap that probably fills these "STOC" and "FOCS" conferences.

The rest is history. I went to Romania during the summer, and had to finish the paper over my parents' 56K modem connection. It got accepted. At the conference, some people said "amazing" and others had no clue what an augmented binary tree was. And, for some reason, 6.5 years later, I am still doing theory...

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.

Labs vs Academia

The topic of the day seems to be labs vs academia (sparked by this, and indirectly by Muthu, picked up by Michael Mitzenmacher and Jon Katz). I thought I would contribute my own perspective, since I've been in labs for about a year, and went through university/lab and lab/lab transitions recently.

Location. For those of us with families, location is one of the main factors. It is not easy to get a job in a top lab, but it is much easier than in a top university, simply because a lot more people go through the lab system (see below). Consider the three prime markets: NY, Bay Area, and Boston.

• In the Bay Area, Berkeley / Stanford weren't interested in interviewing me, but IBM gave me jobs (both a temporary and a full-time one, which was great).
• In the NY area, Princeton / NYU / Columbia weren't interested, but, again, ATT gave me a job.
• In Boston, the problem remains unsolved since MSR New England is not in the mood to hire young people. But arguably there are many more non-top-but-good universities, so this compensates (around San Francisco, for instance, this alternative is entirely lacking).

For me, location made the decision between IBM and ATT (since California tries quite hard to keep foreign medical doctors away).

To see the difference between the chance of getting a job in labs vs universities, think about the numbers: IBM, ATT, and MSR Silicon Valley were willing to hire in theory (and they did) on my particular year, but among the top universities only MIT did.

As for the non-prime locations, there is a wide range between almost-prime and really-avoid. I had offers from some almost-prime ones (Atlanta and San Diego), and I think I would've been happy with them.

However, I want to add that I don't buy Jon Katz's argument that non-prime locations are cheaper. Think about what you want; the cost depends very much on your utility function. For me, things that matter include flight time (and cost) to Europe, availability of Romanian/Eastern European wine and food, and closeness to mountains (the worst thing about NY). Things that don't matter include the price of houses in suburbs.

Career prospects. Let me make this explicit: the chance that you will grow old in a lab is slim. Think of your lab career as a 5-year postdoc, and be prepared to reapply to faculty jobs.

Sure, labs will go through a great deal of effort to tell you that this is not true. But look around: the vast majority old people in labs are either the big founder-of-the-group types, or people who are post-faculty positions (they had one and left). The number of people who go through the lab system is significantly higher than the number of people who stay (which is great for young job seekers, as I mentioned above).

I am not sure what causes this empirical fact, but I can offer some hypotheses:

• Tradition and culture encourage you to leave for universities at some point;
• Labs reliably go through periods of instability, where things turn really bad, and most of the group leaves. Some labs never recover, while others recovered quite successfully, but with a significantly changed group (see IBM Almaden and ATT).
• If you spend too many years in a lab, there is a danger that you fade into TCS oblivion. (You get integrated more into practical groups, and stop being a theorist; you lose contact with the recent trends; etc.)
• The perspective of having students seems much more attractive once you get tired of the nitty gritty details and would like to delegate some.

Thus, my recommendation to job seekers is to consider labs as very high risk venture, compared to a job in a university. On the one hand, if you choose the lab option, you will most likely seek to move to a university later, so make sure that your track record stays very competitive. On the other hand, if you choose a university, CS departments are exceedingly friendly and rumour has it that tenure is easy to come by (even if your record as Assistant Professor is one notch lower than it was as a PhD student, when you were hired --- as someone put it, "people who get jobs at top places are brilliant, while people who get tenure at top places are very good").

Freedom for in-depth work. If you're reading the discussion above as saying that a university job is always better, you're missing the fact that "risk" is always two-sided. The one aspect where labs excel is the ability to do in-depth work.

As faculty, you have to worry about your classes, your students, and your grants. These will slowly push you to be more stable, reliable, and risk-avoiding (turning you from brilliant to very good). No matter how insensitive you are, chances are you will care about your students at least a little bit, and you will think twice before hanging their life paths on some super-risky venture. (Not to mention that you have to train them before they can join you on said super-risky venture.) And ignoring the students is also hard to do in practice; they drain a lot of mental energy from you.

In a lab, you have to worry about not getting fired, and nothing else. Theory-wise, you can take large risks if you care to (you're not affecting anybody else), and you don't owe anybody any significant share of your brain.

In-breadth work. As I showed above, labs are much better for in-depth, risky, theoretical work. How about if you fancy yourself doing non-theoretical work? The situation is exactly the opposite.

Labs are the ideal place to collaborate on standard problems with people across Computer Science. There are many people in the lab doing practical things. You get brownie points for working with them, and they are very interested in working with you (I think they also get brownie points). They don't have an empire of students that they can't really leave; they have time for you. Their problems make sense, i.e. you won't dismiss them as "practice" (as someone put it, in universities, most of "practice" doesn't apply to practice, which is a big turn-off for some theoreticians who try to stick their heads outside theory). You can question their model as much as you like, since lab people have the real data, and they are open to revising their understanding of the world if you see that data in a different light.

But if you want to go broader and riskier, you're out of luck. You simply cannot work in theoretical linguistics, both because there's nobody around you whom you can talk to, and because nobody in the management wants to hear about you doing this. And you cannot even work on anything too non-standard in computer science -- companies are surprisingly risk averse and slow. (You may remember the story of a theory guy who came up with the Google page-rank scheme around the same time; he was in an industrial lab, while the Google founders were at a university. Which of them turned this into a billion-dollar product?)

Thus, if you fancy yourself as revolutionary outside theory, go for a university (and start by getting tenure). If you want to solve really cool problems inside a bigger system, a lab is the place to be. In a university, you will simply never hear about those problems, and in a start-up you will not face them. (A start-up has to do one thing very well, and other things less than horribly; they don't have much variety for deep thinkers.)

Salary. If that matters a lot for you, I have bad news. Salaries in labs are really not what they're rumoured to be. They are, indeed, higher than in universities, but only marginally so. From the data points I have, this seems to hold true at any level (e.g. comparing middle age lab people with Associate Professors.)

In fact, be prepared to negotiate for any salary advantage. My initial offer was equal to the initial offer I got for a 9-months salary at a university! It got increased significantly after I laughed them off. (I heard a very good phrase that I recommend: "I certainly prefer to come to your place on intellectual grounds alone; but my wife would find it very strange that I am refusing this other job with such nice benefits." -- somehow HR people never argue with the stereotype of a wife interested in money :)

Intellectual honesty. In some sense, the lab offers you a great feeling of intellectual honesty: you have seen the real problems (even if you don't work on them). You have informed opinions on what is really important outside theory, and you may get to do such work yourself.

But the labs can also be awful on the same grounds of intellectual honesty. You have to ask for permission and IP-clearance before you publish anything. If you do anything that might be interpreted as important, there is a risk that you are forced to patent it (a horrible thing from my own ethical perspective, due to the way patents are abused and misused in the US). And if you want to write a library for the world to use, chances are it will be very hard to release it.

Personal freedom and appreciation of your work. People complain about boring faculty meetings, and other such annoyances in the life of a professors. Well, labs are worse. There are, for instance, the unbelievably ridiculous things, like hour-long mandatory courses on the effectiveness of sending polite emails to coworkers. As opposed to a professors, whose relation to the university is more like a member in a coop, in a lab there are people above you who have no respect for you or your time.

Then there are the moderately ridiculous things, like cutting coffee to save money. Again, it comes down to the fact the decisions are made by people who don't know you or have any respect for you.

Finally, there is the issue of travel. Faculty may complain (rightly) about the horrors of periodic begging for grants, but it is nowhere are demeaning as begging for every single trip you want to make (whether your lab should pay, or some external source is paying). I'm not saying travel approvals are harder to write -- they are much easier than grant proposals; but their periodic, and insignificant nature makes them demeaning. (This issue is especially bad during times of economic hardship. Muthu once mentioned a deal of the form "add $15K to my salary and I'll never file a reimbursement form." In certain times, the deal you get at labs is really like "we'll add $0 to your salary, and you never file a reimbursement form.")

Of course, objectively things are not bad. We have high enough salaries to afford coffee, and even all scientific travel when it comes to that (it's tax deductible, so it's half the dollar cost to you). It's all about the fact that somebody far above you sees no difference between your job and a dishwasher's.

There are probably many aspects of the lab vs. university comparison that I missed, so feel free to comment or ask.

SODA / Data Structures

The SODA list of accepted papers, with abstracts, is here.

Here are the clear data structures papers:

• Fully-Functional Succinct Trees (Kunihiko Sadakane, Gonzalo Navarro)
  
  
• On the Cell Probe Complexity of Dynamic Membership (Ke Yi, Qin Zhang)
  
  
• Data Structures for Range Minimum Queries in Multidimensional Arrays (Hao Yuan, Mikhail J. Atallah)
  
  
• A locality-sensitive hash for real vectors (Tyler Neylon)
  
  
• Deletion Without Rebalancing in Balanced Binary Trees (Siddhartha Sen, Robert E. Tarjan)
  
  
• Cache-Oblivious Dynamic Dictionaries with Optimal Update/Query Tradeoff (Gerth Stølting Brodal, Erik D. Demaine, Jeremy T. Fineman, John Iacono, Stefan Langerman, J. Ian Munro)
  
  
• Cell-probe lower bounds for prefix sums and matching brackets (Emanuele Viola)
  + A Lower Bound for Succinct Rank Queries (Mihai Patrascu)
  
  
• Applications of Forbidden 0-1 Matrices to Search Trees and Path Compression-Based Data Structures (Seth Pettie)

The following are also data structures papers, though they can be seen as stradling two areas:

• A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs (Aaron Bernstein) -- the main contribution is better preprocessing time of a data structure
  
  
• Counting Inversions, Offline Orthogonal Range Counting, and Related Problems (Timothy M. Chan, Mihai Patrascu) -- improves the preprocessing and offline times of some data structures
  
  
• Highway Dimension, Shortest Paths, and Provably Efficient Algorithms (Ittai Abraham, Amos Fiat, Andrew Goldberg, Renato Werneck) -- distance oracles are a very important topic in data structures; this paper is more about modelling, though.
  
  
• On the Exact Space Complexity of Sketching and Streaming Small Norms (Daniel M. Kane, Jelani Nelson, David P. Woodruff) -- whenever you talk about streaming and care about time complexity, this is clearly a data structure; if you solve the problem with k-wise independent hash functions, even more so.
  
  
• The 1+β Choice Process and Weighted Balls-into-Bins (Yuval Peres, Kunal Talwar, Udi Wieder) -- more on the power of two choices, though the process is probably unrealistic in a data structures context.
  
  
• Regular Expression Matching with Multi-Strings (Philip Bille, Mikkel Thorup) -- stringology is close enough :)
  
  
• Fast distance multiplication of unit-Monge matrices (Alexander Tiskin) -- also stringology.

I find the number of papers to be on the low side. There are a couple of rejected papers where I may disagree with the wisdom of the PC, but overall I think the numbers just reflect the fact that the field is old, and progress comes hard.

Disclaimer: Note that this list is not so closely correlated with my interests. There are data structure papers that I am not interested in, and many non-data-structures papers that I am interested in (even among my own papers, only half can be found above).