Friday, January 27, 2012

Guest post on ITCS by Chazelle

(Requested announcement: Calling all Women PhD Students (and a few undergrads) We will be having our bi-annual Women in Theory (WIT) Workshop this year in Princeton. The dates are June 23-27, 2012. Applications are due on: Feb 29, 2012. Go here for all the relevant information. Hoping to see you in June. From: Shubhangi Saraf, Lisa Zhang, Moses Charikar and Tal Rabin.)

(Guest Post by Bernard Chazelle) Why ITCS?

Thanks to Lance and Bill for their kind hospitality. I am delighted to be here. With the third edition of ITCS (formerly ICS) behind us, I thought it would be good to share a few personal, biased thoughts on the subject -- "personal" because I do not claim to speak for the Steering Committee; "biased" because I happen to chair that august body.

First, let me reach for my big bucket of gratitude. Shafi Goldwasser and Silvio Micali did an amazing job as PC & local chairs and I cannot thank them enough. A big shout-out to both. Toda Raba to Yael Kalai, too, for her great help, and to Omer Reingold, Nir Shavit, and their fellow actors for a fabulous "playback" show. If you missed it, fret not. If future organizing committees have any sense, the Nir-Omer show will soon come to a conference near you.

This year's ITCS had about 100 submissions, roughly a 20% growth from previous years, and 118 registrants. Talk attendance never seemed to dip below 90, a heart-warming figure that would be the envy of many conferences. In Shafi's and Silvio's deft hands, innovation came out swinging in all sorts of endearingly creative ways, from session chairs giving annotated previews of the talks to postdocs and graduating students making 5-min pitches to introduce themselves and their research. Brilliant! After watching the new generation of theorists in action, I can tell you that the future of theoretical computer science looks very bright, indeed!

And the future of ITCS, you'll ask, how bright is that? When I chaired the PC last year, a reviewer's comment struck a chord: "This submission would be good for STOC but might not be innovative enough for ICS." Now, that's the spirit! Of course, plenty of ITCS papers would fit in nicely at STOCS/FOCS. (Apparently, more than a few tried to fit in.) That said, it would take an advanced case of color blindness to miss the contrasting hues between ITCS and the rest. All PC members were instructed to add an innovation axis to their evaluation space, and, by golly, they did! (And when I use the word "golly," you know I mean business.)

STOC/FOCS has been accused of all sorts of dastardly deeds unmentionable on a family blog -- from accepting too few papers to boosting trends to rewarding technical wizardry. No less. STOC and FOCS might be four-letter words to some, but to me they're venerable legacy institutions that serve worthy professional functions, such as allowing junior researchers to trade these four-letter words for Theory Club membership cards. Nothing to sneer at. Over at Michael Mitzenmacher's corner, here, Umesh Vazirani bravely suggested merging STOC and FOCS into one mega-conference --- SFOCS, I guess. Much as I love the idea, beginning with the soothing effect of pronouncing the word SFOCS out loud, I didn't come here for a food fight, so I'll fall back on old New Jersey wisdom and say we cross that landfill when we come to it. Yet definitely something to mull over.

ITCS provides a venue for quality outside-the-box thinking. Not without reason, a few have wondered whether the best place outside the box is inside a new conference. On the plus side, conferences provide ideal platforms to publicize new work and, for younger scholars, increase the visibility of their research. With its particular focus on the uncharted, ITCS offers a welcome new outlet for a glut of quality papers. A conference is a big heads-up, a "breaking news" banner flashing on the Theory Channel. It's also a chance to initiate lasting collaborations and meet extraordinary people in pursuit of extraordinary ideas. It's fun.The downside is that a human being can attend only so many conferences before "their budget glares red and their head bursts in air" (as they say before kick-off at the Super Bowl).

This dichotomy, however, isn't quite right. It ignores the tangled web the online revolution has woven into our lives. Whereas in the past I'd have to go to a conference to hear a new result, this is no longer so. The PDF will come to me. It's a given that attendees at many talks will already know the results, perhaps even the proofs. This has diminished the relative importance of attending a conference while at the same time increasing its reach, and hence its influence. Don't get me wrong. I am not saying ITCS is so cool you don't even have to go. I am saying that, in the age of instant downloads, missing this month's Jay-Z & Kanye West "UGC" gig at the Garden ain't gonna be the heartbreak it would have been in the days of old. So, while I recognize that the burden of extra travel is a drawback and the timing always an issue, our wired world alleviates these concerns somewhat. And if you find this argument too subtle for its own good, well, remember, there's always the Umesh option.

Another worry heard on Theory Street is fragmentation. I don't get that. The sociological makeup of all these conferences is pretty much the same, anyway, so the risk of fragmentation is about as high as that of Dr. Jekyll and Mr. Hyde parting ways -- OK, make that Superman and Clark Kent if you prefer. In fact, this has it exactly backwards. Theory has yet to penetrate many geographical markets. Eurotheory shares a name with our kind, and little else. With Asia a promising growth area for our field, it is of more than symbolic value that ITCS was born in China. All theory conferences today are regional (North America, Latin America, Europe, Asia, etc). Maybe ITCS can be the exception. At any rate, to expand both the intellectual footprint and the geographical reach of Theory is a central goal of this conference.

To close on a personal note, let me get my crystal ball out of its dusty case and tell you what I see. As the new sciences of the 21st century further embrace their algorithmic nature, I see ITCS getting enriched with a growing flow of conceptual imports from physics, biology, economics, etc (and vice-versa). While the letter T was added to ICS for mundane reasons -- an ACM conference had a previous claim on the acronym -- I hope ITCS remains unabashedly theoretical. Yes, you heard right. And as you watch me adroitly duck the tomatoes sure to be hurled my way for this impolitic stand, you might even spot a contradiction or two. I mean, how can computing theory reach out to the sciences without losing its theoretical core? Well, well... Leaving aside the fact that math developed with precisely that sort of outreach, the answer is easy. What the "new" sciences (bio, neuro, socio, and all that) lack more than anything is a conceptual framework. Theoretical computer science can do for them what mathematics did for physics. Why? Because algorithms are the differential equations of the 21st c. They are the language of modern science. That's why. At this point, you expect me to clear my throat and indulge in a tasteful round of name dropping: "Moreover, as Newton and Einstein used to say, blah blah..." (I got that from my physicist friends. Works every time.)

But not today. Truth is, delusion won't help our cause one bit. Neither will diffidence or skittishness, however. These are heady times for computing theory, my friends. Hand wringing over fine tactical points should not distract us from our common goal, which is to allow Theory to expand and flourish, to unite and conquer. ITCS aims to do just that. It is an exciting experiment worthy of your support.

Thanks for your attention and, in a nod to ITCS' roots, a happy Year of the Dragon to all!

Bernard Chazelle


  1. Hi Bernard,
    Since you mention Michael's posts, I was wondering what you thought about the clash in schedule between ITCS and SODA. Do you see this as a problem or a non-issue ? My personal feeling is that the theory community isn't so big that we can afford paper splitting of this nature.

  2. Bernard,

    I agree with you about many of the positive things you describe about ITCS (and thank you for posting about them). Where we diverge, I think, is the issue of "yet another conference". You've definitely acknowledged these issues in your post -- I like very much your whole paragraph "ITCS provides a venue...", which mentions clearly the yet-another-conference issue. I'm definitely not getting the Internet-as-savior motif of the next paragraph, however. I don't think you can have a long-term sustainable conference if people don't come. Yes, the papers will be put on the web (and perhaps videos too), but lack of physical presence diminishes the many other positives of the conference you describe so eloquently throughout the essay (including things like having graduating students present themselves and their work). The ITCS stamp may be useful in getting a paper noticed, but I can put things on arxiv myself, so the main reason to publish it in a conference is to talk about it to a larger audience -- if we can't successfully manage our conference structure, is there a point to having conferences at all?

    ITCS has offered some interesting innovations, that should be incorporated into conferences more broadly. It doesn't change what I see as the fact that theory's conference structure is not helping the field. In my last blog post I talk about the need for some high-level coordination and structure for theory conferences. One can always make the case that yet-another-conference must be a positive (more papers published, another choice of venue to go to, etc.). I don't think that argument is right -- I think the field is becoming fragmented, and less coherent for it. (The ITCS/SODA dates being just one example, as Suresh mentions above.)

  3. Why don't we just co-locate SODA and ITCS. They can still serve there same purposes, have separate review processes, but make it much easier for people's travel. And will make both conferences more robust by helping ensure critical masses.

    1. Colocating SODA and ITCS could actually work. SODA draws a diverse audience, and the intention is for ITCS to be the same, so they could provide the 'conceptual-algorithmic pairing' nicely.

  4. I'm curious - what's the "Umesh option"?

  5. On a lighter note, the Nir-and-Omer Playback show really was great, a big highlight of the conference.
    And it wasn't just cheap laughs about the foibles of academic existence; they used audience stories as improv material, but took a wonderfully surreal approach that challenged us to break out of the headspace of the conference and look at the world in a bigger way. Anyway, you should've been there.

  6. All theory conferences today are regional (North America, Latin America, Europe, Asia, etc).

    Conclusion: Bernard does not think SOCG is a theory conference. (2009 in Aarhus; 2010 in Snowbird; 2011 in Paris; 2012 in Chapel Hill; 2013 in Rio; ...)

    And where was SODA last week?

    1. Right, because a conference (SODA) which is in its 23rd edition and has been held in exactly three countries is such a good counterexample to Chazelle's point.

      It also says something that one of the most "international" theory conferences (SOCG) is held 2/3rds of the time in NorthAmerica and about 1/3rd of the time in Europe and twice in Asia.

      For a real international conference check VLDB, the last 23 editions of which were held in 21 different countries.

  7. Bernard Chazelle asserts: Theoretical computer science can do for [system sciences] what mathematics did for physics.


    If we embrace a system perspective, then perhaps Chazelle's desired evolution can be accelerated by a modest proposal that is cost-free and administratively simple: declare a five-year moratorium on the word "oracle" appearing in STOCS / FOCS / ICTS / SODA submissions.

    Given the considerable practical difficulties that engineers encounter with respect to the purchase, rental, or coding of higher-class oracles, it seems implausible that such a moratorium could result in enduring harm to the global CSE enterprise.

    Conversely, if beneficial effects were evident after five years, then the oracle moratorium readily could be extended, and perhaps other computational topics might be considered for similar moratoriums.