Late last Friday night, after reaching SF airport to take a red-eye to Atlanta, I peeked at my email and found a one-liner from Noam, asking if I wanted to join as a co-blogger. In no time I found myself sending the reply “Happy to join”, then I boarded my flight and immediately snoozed off. After a couple of hours, I woke up sweating and full of anguish: How had I taken this relatively big step with so little thought? Do I have the time, do I have ideas, do I have ways of talking about them, how will I be judged by people, and do I need to put myself through this? Then I was reminded of my (very positive) ventures with Noam, my mind calmed down, and I slipped back into deep slumber.
The year is 1998 or 99, the venue is STOC or FOCS; here is my 30 second conversation with Noam:
Me: I hear you are working in economics these days. How does a top-notch complexity theorist make such a big change?
Noam: That is where the future lies!
Fast forward to March 2001. My book on Approximation Algorithms is almost ready to go to the publishers. I do not want to work in this area anymore — the big problems I wanted to solve in recent years, Steiner tree and asymmetric TSP, have not yielded despite a huge investment — and I can see the BIG VOID approaching! I have already written a paper in game theory but I know so little about the area. Even worse, I can’t seem to understand what game theory papers are really talking about. If only I could gather 5 top experts in the area andhave them tell me about their work …
I soon realize that many other people are in the same boat! So I approach Fred Roberts, Director of DIMACS, with a proposal for a workshop. He is excited and immediately commits generous funding. I know a few potential speakers, but to make it a good event I will need to find a suitable co-organizer. The choice is obvious — Noam — and he agrees! And the workshop ends up being a big success and plays a key role in getting AGT started. (One small gripe: DIMACS still hasn’t listed the co-organizers in alphabetical order.)
Fast forward to December 2005. A publishing rep visits and asks which book I would like to write next. I tell her it would be on AGT but I don’t know enough to write a complete book, and what is more, no one else does either! The rest of the conversation goes something like this (the “….” represent switches in the person speaking):
Rep: You should produce an encyclopedia on AGT …. You will be the Editor-in-Chief and you will have (innumerable) editors, subeditors, reviewers …. The encyclopedia will have extensive bibliographies on all aspects. …. We will make sure every library gets a copy. …. You will get x% of the total sales.
Me: We need an edited book, with chapters written by many top experts working on different aspects of AGT …. I will need to find 2 or 3 well-chosen co-editors …. The chapters should expound the main ideas in the clearest possible manner using simple settings and relegate more complex developments to exercises. They should provide only the absolutely essential references and not be structured as surveys but as pedagogical tools …. If we do a really good job, just about every CS Dept. will be using it for a semester-long course. …. No one should get royalties, not even the co-editors. Instead the price of the book should be set as low as possible and the book should be made available online.
As you can see, we were on completely different wavelengths! But the conversation had already set me in motion, and an obvious choice of co-editor was Noam!
My stance and my creed: My work sits at the extreme “A” end of AGT&E. Fortunately, a lot has happened at that end over the last ten to twelve years and that is what I will mostly talk about.
I consider our theory of algorithms and computational complexity sacrosanct and I believe we need to carefully maintain its integrity. My recent guest posts reflect this, e.g., on Galactic P and Galactic PTAS and on the class FIXP, and so does my recent paper on non-bipartite matching, in which I have made a special point of not sparing myself. Of course, I can’t claim that my viewpoint is the right one, and I will always seek extensive discussion from you all. Hope you will participate.