Friday, November 2, 2007

A Numbers Game

I have said before that I believe theory/CS is a numbers game. During a few discussions sub vino, I was challenged on this issue. Two main points seemed to emerge:

  • What matters is your best result (L).
  • STOC/FOCS get 10-15 obvious accepts, and a heavy tail of competent papers, among which it's hard to choose. If we care about making STOC/FOCS a quality measure, why not accept just those 10-15 papers?
One of my main points is that I don't actually trust ourselves to get either of these 2 schemes to work. The first degenerates into the power of public hype and recommendation letters, since none of us will actually solve P vs NP (or any other result that is universally considered important). The second degenerates into a bloody political struggle, since the top few places depend too much on randomness.

I have seen enough examples arguing for pessimism, mostly while I was acting as a reviewer. But since I can't actually talk about those, let me give 2 personal examples.

Predecessor. In STOC'06, Mikkel and I had our predecessor lower bound. The main claim to fame of this paper is that it was the first lower bound to separate linear and polynomial space.

When it comes to such a claim, in my opinion, it doesn't actually matter if you remember anything from the data structures class you took in college. It doesn't matter if you know that the bound is showing optimality of a very influential data structure from FOCS'75. It doesn't matter if you know this was one of the most well-studied problems in data-structure lower bounds, and people were actually betting the previous lower bound was tight.

No. Somebody comes and tells you that we've been toiling at this lower bound game for more than 20 years, and we haven't yet managed to show that a data structure with space n10 is sometimes better than one with space O(n). Now, they tell you, such a bound is finally here, and a vast array of problems from Algorithms 101 have switched from unapproachable to hopefully solvable. That should be a worthy result.

How did it feel from the inside? This was a paper we had worked on for 2 years. Just the conceptual understanding that we needed to develop felt like one of the longest journeys I have ever embarked on. And in the end, it was actually a clean result, which indeed needed conceptual developments, but not so much technical pain! Mikkel, who never ceases to amaze me with his youthful optimism, was betting on a best paper award. I was of course at a university, and had a better estimator of the community hype factor. I knew that Irit's PCP was unbeatable for an award, but I was still convinced our paper would go down with a splash.

The actual outcome? Moderately positive reviews. Nobody took notice. And we weren't even invited to the special issue, which was a genuine shock for us.

Range Counting. In STOC'07, I had a lower bound for 2D range counting. After the predecessor paper, I quickly decided this was the next big goal in the field. Range queries are very, very well-studied, play a crucial role in our understanding of data structures and geometry, and are a major bridge to worlds outside theory, such as databases (see this irrefutable argument). Armed with some appreciation of the techniques in the field, this also felt like a make-or-break problem: we were either going to solve it, or get stuck again for 20 years.

Though I like to look at cell-probe lower bounds, range counting has a life of its own. This class of problems was studied from the dawn of computer science, way before our understanding of models crystallized. People have been proving many excellent lower bounds for range queries in the so-called semigroup model: each input point is associated with weights from a semigroup; the goal is to compute the sum in a "range" (rectangle, circle, wizard's hat etc), using only the semigroup addition. In this model, we obtain a good understanding of geometry: it is enough to characterize a partial sum of a subset of points by the extreme points in a few directions. Addition only allows us to "build up" subsets, so we need to understand composability of constant-dimensional shapes, dictated by such extreme points.

While the bounds for semigroups were making very nice progress, we remained clueless about even the slightly stronger group model, where subtractions are allowed. This is the gap between understanding low-dimensional geometry and understanding computation (a very high-dimensional, unstructured space, such as the n-dimensional space of linear combinations). Proving bounds in the group model became the first lower-bound question in the surveys of Pankaj Agarwal and Jeff Erickson. Thus, the group model seemed hard enough; never mind the cell-probe model, which is significantly stronger than a model with additions and subtractions.

About a year after predecessor (I had the final critical insight one week before STOC), I managed to show an optimal lower bound for 2D range counting in the cell-probe and (of course) the group model. Again, it does not seem to me like a paper where you need to be an expert to understand that something interesting is happening. Citing from the abstract:
Proving such bounds in the group model has been regarded as an important challenge at least since [Fredman, JACM 1982] and [Chazelle, FOCS 1986].
It seems to me that whenever somebody claims to address a challenge from JACM'82 and FOCS'86, the only possible answers are:
  • You are lying.
  • The paper is wrong.
  • It seemed like an interesting problem back then, but things have changed and we no longer care. (... and I don't see this applying to range queries.)
  • Yes, this is a very good paper.
The actual outcome? Lukewarm reviews: "seems like an interesting result, and there is a comma missing on page 7". No student paper award, which again I was expecting because my hype-meter was well-aware of Sergey's paper. (In another great proof of our intellectual maturity, this otherwise nice paper might go down in history for using Mersenne primes, rather then understanding something about locally decodable codes. Oh well, those who can't put primes in their abstracts might as well stick to cannabis.)

Finally, the paper was not invited to the special issue. By this time, it was not something that had never crossed my mind; it was just a disappointment.


Conclusion. You should work on major open problems. If you solve them, it makes for papers which are reject-proof (well, almost). But don't count on that "one big result" plan, as you may be in for a nasty surprise. As a community, we are reliable enough to get some kind of average right, but we're not doing so well on L.

So when you get your first STOC/FOCS paper, go open the champagne or light up the cigar. You are officially part of the game. Now, it's time to play.

Next round: November 19.

24 comments:

Anonymous said...

So, to summarize:

My papers are great.

I'll be looking for a job soon.

Why won't the community notice me?

MiP said...

Oh, I don't think I have such big problems being noticed, wouldn't you say? For one, you're reading my blog.

The only advice is to treat it as a numbers game: prove something, smoke your cigar, regroup, go on. If you've done one great thing, it may not be enough, and it's no excuse to stop anyway.

D. Eppstein said...

Regardless of whether we could stack the committee in such a way that it correctly selected the "true" top 10-15 papers (here defined as papers by you and me and papers that cite yours and mine), would doing so be a good idea?

If one's reputation is determine solely by one's single best paper (which I doubt), would it be healthy for the field to get rid of all those people who are steady contributors but never going to get a top-10 paper?

And is the purpose of STOC papers really only to get another ticket in the reputation lottery? Shouldn't we be thinking more about the progress of knowledge, and less about what others think of us?

MiP said...

would doing so be a good idea?

No, I don't think so. In retrospect, it's true that we don't remember more than 2*15 papers from 1975. But there's too much noise to be able to select them ahead of time. That's the whole point of theory, we're doing long-range research and we don't always know what's going to happen.

The purpose of STOC/FOCS papers is not to build reputation, it is to solve problems. But incidentally, the community wants to select the best problem solvers to give them money, students, tenure etc. So we won't actually be able to dissociate them completely.

Anonymous said...

D. Eppstein and Mihai reach the same conclusion. One is reasoning from the community planning perspective, the other gives advice to selfish agents, who will reach the same equilibrium.

Anonymous said...

>> In another great proof of our intellectual maturity, this otherwise nice paper might go down in history for using Mersenne primes, rather then understanding something about locally decodable codes. Oh well, those who can't put primes in their abstracts might as well stick to cannabis <<

This was clearly the best part :)

Anonymous said...

I am shocked that such nice papers were not even invited to special issue.

It goes to show how quickly TCS community forgets long standing open questions and begins to define new ones.

Anonymous said...

I actually find Mihai's attitude quite commendable. Anyone who has had good papers rejected due to poor refereeing will testify to how exasperating this process can be. It is nice to see that Mihai has decided to move on to producing more papers, instead of getting frustrated with the process and the community.

Anonymous said...

Hi Mihai. A friend pointed me to this post, and my comment is the following:

You are right in many of the things you're saying. However, it is not possible for someone to believe that this post is uncorrelated with the fact that (i) you are now looking for a job and (ii) there is at least one other candidate in the market whose work has been (at least so far) more influential than yours.

MiP said...

Anonymous, you are thinking on too small a scale :) If I'm going to stick around theory, the real plan is to influence the opinions of this community on a 40-year time scale, not for this year.

Anonymous said...

Anonymous, who is this other candidate you speak of?

MiP said...

Yes, I was also wondering who the unnamed magic candidate is...

Anonymous said...

Mihai, I think as it was discussed in Lance's blog, it seems H-number (i.e. the number i that at least i of you papars have i citations) and the maximum citations are good measures. Whare are yours? Are they high comparing to other applicants this year? Of course this number is dependent to the competitivness of your field of research also.

MiP said...

Anon, I am not sure how to objectively compute the h-number. Google Scholar? That yields 6, I believe.

In any case it seems a more sensible criterion for old people, who have had enough time to gather lots of citations, and make this a stable measure. If you're written a paper 2 year ago (a very good case for a graduating PhD!), how many citations do you expect to have?

Anonymous said...

Many good papers written two years ago do have a lot of citations, actually. Examples -- Dinur's PCP (33), Khot-Vishnoi(47), Arora-Lee-Naor(44). These are all papers from FOCS/STOC'05, I believe.

Anonymous said...

What's with the Mihai-haters?

Paul Beame said...

Somebody comes and tells you that we've been toiling at this lower bound game for more than 20 years, and we haven't yet managed to show that a data structure with space n^10 is sometimes better than one with space O(n).
I wouldn't sweat too much over your STOC 2006 paper's reception by the PC. It is an excellent paper and provides an extremely clever and new way of thinking about these problems (that are obviously important to me personally). That conference had a phenomenal program with many excellent papers. You mentioned Irit's paper but didn't mention Guruswami-Rudra's solution of a nearly 50-year old problem of optimal list-decoding, or Daskalaskis-Goldberg-Papdimitriou finally getting hardness results for computing Nash equilibria. There were papers that solved major open problems in quite a few areas.

The point should not be that you can't rely on PCs to recognize the quality of your best work beyond accepting it. The point should be that there is no guarantee that somebody else won't produce something else that's great that people will like better than yours. You shouldn't rely on awards. However, really good work won't have any problem getting accepted. People in the field will also recognize its quality after it is presented - there is a remarkably strong consensus in theory in this regard when compared with any other area of CS.

PCs for conferences like STOC or FOCS must be broad-based and there is a matter of taste in choosing best papers - sometimes it is obvious and there is overwhelming consensus but often it is a matter of choosing from among many excellent papers - often papers that do not have an overlap in expertise among their reviewers.

Anonymous said...

What's with the Mihai-haters?

Dude, it's hard not to be when the guy is so arrogant...

Anonymous said...

Look, Mihai has done some things that nobody thought were possible, both in the lower bounds he's proved, and in the kind of career he's had. We are actually curious (for instance, why does he feel the need to publish so much?), and it's good that he is willing to speak openly.

Dude, it's hard not to be when the guy is so arrogant...

You're just coming across as an envious and frustrated student. Good researchers are comfortable enough with themselves to show respect to others.

MiP said...

Paul,

The point should not be that you can't rely on PCs to recognize the quality of your best work beyond accepting it.

I still think that is a valid point, and it is good career advice to not count on one "great publication". You yourself give reasons why one great paper might not be enough:

The point should be that there is no guarantee that somebody else won't produce something else that's great that people will like better than yours.

So ultimately, it seems we agree on the conclusion, but maybe not the wording. :)

Luca said...

While we are on the subject of STOC 2006 papers that would have won the best paper award in almost any other conference, Barak-Rao-Shaltiel-Wigderson had the first progress in 25 years in explicit constructions of Ramsey graphs.

Just what was going on in the Summer of 2005?

Anonymous said...

I think what gets to a lot of people is Mihai's public embrace and enthusiam for the "gamesmanship" aspect a theoretical computer science career. Of course might just be that he is public about what a lot of people think in private. But, it is certainly true that a lot of people find the whole "it's a game whose goal is to rack up STOC/FOCS count" somewhat distasteful. (Such people tend to work in areas where pickings are few and progress is relatively slow.)

Mihai probably does not need advice on the job market, but that does not stop The Anonymous Internet. I would suggest that he prepare for his interviews by training himself to talk about how his work connects to "real world computing problems", and to drop any mention of being passed up for awards or gaming the STOC/FOCS publication race.

MiP said...

Anonymous, thanks for the advice! Concentrating on the broader impact in job interviews has always been the plan. As you say, part of it is the gamesmanship (that is the right game to play for interviews), but more importantly, I actually care about the role of TCS inside CS, and have enough strong opinions on the issue.

Such people tend to work in areas where pickings are few and progress is relatively slow

This is a symptom of a highly fragmented community, where everybody thinks his field is harder, more noble etc. The real difference is not the field, it's more the attitude and personality. I mostly work in lower bounds, the field of slow progress --- but when I can't prove the bound I want, I just try to switch to another interesting problem.

Anonymous said...

You are definitely as bad as your worst talk. When I go to a FOCS/STOC talk and the author clearly hasn't put any effort into the presentation, then yes I look poorly at the author's future work.

Not trying to be negative, but just putting another aspect on the FOCS/STOC game (which is itself just one part of the larger get-me-a-job game, as others have pointed out).