Blog happenings

As you may have noticed, this blog has been on a bit of a hiatus. On the one hand, my expectations for politics-by-blog have decreased to a minimum and my boredom with the theory community has grown. On the other hand, I have not had enough time for exposition-by-blog --- or, better said, I discovered that my thought process is too obsessive and erratic to leave room for regular expository interruptions.

In an attempt to pull myself from the blog hiatus, let me respond to two recent blog posts, one guest post by Mikkel on My Biased Coin, and one post by Lipton.

My own view of Mikkel's post reads like: "Hey, remember that big-big fuss from 1-2 years ago about simplicity as a virtue? How come this was hijacked by people wanting to introduce new models all the time, and didn't help the papers on real algorithmic problems, where simplicity matters the most? Do we need to start our own «Innovations in Real Computer Science» conference, or can we have a session at SODA instead? "

My own favorite example of a book algorithm is the "mod-3" suffix tree construction of [Kärkkäinen, Sanders ICALP'03]. This is an amazingly simple algorithm (much simpler than anything before), and truly feels like the "ultimate" algorithm for suffix tree construction. It also demonstrates a rare property: dividing into 3 parts in a recursive construction can work much better than dividing into 2. This algorithm should (and probably will) be in any Intro to Algorithms course.

So, was this algorithm the Best Paper in STOC/FOCS? Not nearly --- in fact most STOC/FOCS people probably never heard of it. I also know from inside sources that the paper was viewed as somewhat borderline at ICALP (which is not too surprising --- as screwed up as US conferences are, we still don't compare to the European ones).

***

Moving on to Lipton's blog, we notice that most discussion is confused by the difference between running time and some (problem-dependent) optimization function.

Some people claim that they are different because of Moore's law (your slower algorithm will be fast enough soon), or the fact that CPU cost is not as real as, say, the cost of shipping goods around by trucks in your optimization problem. I disagree with both of these views.

It's irrelevant if Moore's law will make your algorithm fast enough in 2 years; by then, the competition may make you bankrupt. And if you really believe in thinking long term, you should probably be working on quantum computers and worrying about the speed of light (we all know that a memory of N bits has diameter at least N^1/3, so memory accesses cannot be "constant time"). Sure, you may not say anything relevant for 50+ years, but then you will finally be avenged --- and you may be as influential as Babbage's computer was in the design of Java. My response to this long run thinking is a well-known quote from economics: "People don't eat in the long run." (Harry Hopkins)

How "real" CPU cost is will vary. If you're compressing Google's logs by 10%, you're likely to save 10% of a pretty big cost, a worthy goal. In time-constrained systems (like ATT routers), this cost is not smooth, but exhibits a phase transition. If you make this algorithm 30% faster, we can provide this extra functionality that competitors don't have, and convince some companies to switch to our network. If not, not. Adding 30% more computing power is essentially not an option.

So, no, the difference between running times and other optimization criteria is not that it is less of a cost. The difference is that we understand running times a whole lot better. Look, we spent decades understanding the usefulness and the shortcomings of asymptotic analysis, refining our computer model (Word RAM + external memory issues), etc. When we talk about running time, we usually know what we're talking about.

On the other hand, every combinatorial optimization problem is a modelling challenge. Constraints are not quite like this, the graph is not quite general, this cost function is not quite right etc etc. Each important problem needs (and deserves) considerable modelling work before our theoretical predictions are as good as we may want.

But what do we do at STOC/FOCS? We model the problem in the simplest way, ignoring applications (which we are largely unaware of). Then, we prove Θ(lg n) approximation bounds (complete with PCP lower bounds) for the dollar cost of shipping goods by trucks (a problem now rebranded with a fancy name). Now just wait for those Amazon guys to come asking about how to improve their 5% approximation, and we can tell them the problem is perfectly understood!

Basically, a lower bound greater than 2 on a dollar cost is a formal proof that your formalization of the problem is wrong.

So, should we get our hands really dirty and look at the problems in such detail? I think if you're going to be passionate about approximation algorithms, you should do it at least a few times. (I, for one, did a lot of performance-oriented programming before my current work on theory of running times...)

I hope that if our approximation algorithms community gets a lot closer to the OR community, good things will happen. On the one hand, they might give us a break with their "understanding the nature of computation" claims, when they realize they have only a vague idea of what computation really is. On the other hand, nice theory might yet be developed which will talk about 3% improvements...

Talks

Update: The 2nd talk is happening 6pm-8pm in Amfiteatrul Pompeiu (= amfiteatrul de la etajul 2).

I am giving two talks in Bucharest this coming week:

• a more practical one at Poly on Monday (December 7) at 6pm in room EC 101 (Fac. Automatică şi Calculatoare)
• a more theoretical one at UniBuc on Friday (December 11). Room and time to be announced here, but it will be earlier in the afternoon.

Abstracts below. Don't forget to vote on Sunday.

1. Funcţii de hash tabulare
   
   Implementarea tabelelor de hash folosind căutare liniară (linear probing) este mai eficientă decât alte implementări dacă funcţia de hash este suficient de alteatoare. Din păcate, linear probing se comportă foarte prost în conjuncţie cu funcţiile de hash bazate pe înmulţire (cele mai folosite în practică), şi ca atare, acest algoritm este deseori evitat.
   
   Voi descrie o funcţie de hash foarte simplă, care este la fel de rapidă ca înmulţirea pe procesoarele actuale, dar se bazează pe indexarea în tabele precalculate. O analiză matematică ne demonstrează că această funcţie garantează timp de rulare constant pentru tabelele de hash.
   
   
2. Rezultate negative pentru structuri de date
   
   Cum demonstrăm că anumite rezultate algoritmice sunt imposibil de obţinut? Spre exemplu, cum demonstrăm că nu există nicio structură de date cu spațiu liniar care poate suporta range queries în timp constant? În acest curs, voi descrie o demonstrație completă a acestui rezultat, trecând prin mai mulți pași simpli, dar interesanți.

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.