ITCS 2015

It might’ve been there for a while (it definitely should :-)), but I only just noticed: the list of papers accepted to ITCS 2015 is out! There were 45 accepts out of 159 submissions, a record rate for ITCS and a level of selectivity, 28%, comparable to that of STOC or FOCS (which typically accept slightly under twice as many papers, and have less than twice as many submissions). I had the pleasure and honor to serve on this year’s program committee (how else do you think I’d get a paper in?), and I was truly impressed by the overall quality of submissions. We could easily have accepted twice as many papers and still claim a spot for ITCS as a top-tier conference in the theory of computation. If so, why didn’t we? Giving an answer requires to think through which purpose we want ITCS, and more generally our constellation of theory (or theory-friendly) conferences, to serve. The question is being increasingly actively debated, though it has already been on the table for a while (and even featured on this blog…); I think it is an important one, and I’d like to share some thoughts.

STOC and FOCS have been giving rhythm to any decent theorist’s academic year for immemorial times (well, almost — as Dick Lipton reminded us in his Knuth award prize at FOCS, some of us do remember the time when the first editions of theory conferences were making their apparition). Their respective Spring and Fall deadlines are so much entrenched that I was recently asked by a graduate student how one could come up with a new 6-month project every 6 months, and make sure to wrap it up by the next deadline? Of course in practice most people work on many projects in parallel, and decide which have a decent chance of being brought to a (reasonable?) state of completion by deadline time a few weeks (hours?) before the deadline. Nevertheless, these “flagship” conferences are there to constantly remind us of our bi-yearly sacrificial duty. The longer one has been going through the process, the harder it is to imagine any changes to the model: Wouldn’t any reduction in the rhythm affect our productivity and the speed at which ideas spread in the community? To the opposite, wouldn’t any increase in rhythm lead to a serious risk of exertion? Isn’t the actual system just right?

Of course not — indeed, I don’t know anyone who’d claim the current model is good. But I don’t know any two researchers who’d agree on how to change it either. Any substantial proposal seems to immediately run into a large amount of resistance — in the form of a barrage of “what about…?”, or “what if…?” — that it is clear any change will have to be extremely gradual. The difficulty is exacerbated by the additional level of inertia imposed by the professional societies, ACM and IEEE, that administer STOC and FOCS respectively. In this respect the recent proposal by Boaz Barak and Omer Reingold had good chances behind it: Boaz and Omer put forward a very concrete proposal that carefully avoided any changes to the backbone structure of STOC and FOCS, preserving submission deadlines, independent committee evaluation, rough numbers of accepted papers, etc., and instead focused on the format of the actual event, in substance proposing a single yearly week-long “theoryfest” to replace the current bi-yearly 3-day gatherings. Unfortunately, from the echoes I’ve had from Saturday’s meeting at FOCS it looks like even this moderate change  is proving too much for the community to take, and the background grumble is likely to overtake the energetic spike proposed by Boaz and Omer.

ITCS, in contrast, should be largely free of such accumulated inertia. The conference series is still in its blooming youth: the coming edition, to be held in January at the Weizmann institute in Israel, will be the 6th instantiation of the series. It is not attached to any professional society (though it does seem to be loosely affiliated with ACM’s SIGACT), and is instead run by a steering committee made of prominent members of the theory community. Since its inception ITCS has been in permanent soul-searching mode: is there space for yet another theory conference? Wouldn’t the debate over a possible merge of STOC and FOCS indicate quite the opposite, that we theorists already have too many venues in which to express ourselves?

I would argue that there is, and that searching for this space can play an important role in defining the future of theory. Irrespective of changes in the format of STOC or FOCS, ITCS can continue to occupy a special niche: the “conceptual” niche (I don’t like the word — it is too overloaded — but I can’t think of a better one). ITCS is not there to wipe off the excess production that didn’t make it to its big sisters. It is different, not only in its selection process but also, and just as importantly, in the format of the event itself. It should affirm this difference by continuing to build the reputation it has started to earn as a small, friendly, innovative conference in which discussions take a prominent part, the program is light and single-track, and the presentations lead to lively discussions between the participants. Not everyone needs to go to ITCS every year — but, given the chance, most would go, and have a pleasant experience. You might not get to learn about all the recent hot results: theoryfest is made for that. But you’ll be exposed to the pulse of the community, emerging research directions you might not have been exposed to otherwise (for instance, because you went to the other parallel session, the one with talks on your favorite area…).

There is a broader picture to keep in mind with respect to the place of theory within the CS landscape at large. By its nature our field is bound to have its relevance regularly questioned: are we looking at the “right” problems? And even if we are, are the kind of answers we bring relevant? Or has theory lost any contact with applications? ITCS could play an important role in addressing these questions. As a “conceptual” conference it is there precisely to bring to light promising avenues and novel directions in which our theoretical ideas and concepts may find stimulation and application. Vitality of the conference will be a sign that theory is able to permanently re-invent itself. Many of us strongly believe that the language we speak is universal; the question then is only whether we’re able to use that language effectively and bring it to bear on the problems that our peers across the sciences care about.

If I am to judge of ITCS’s vitality by the quality of this year’s submissions I have no reason to be worried about the future of theory. As already mentioned, the crop was excellent, and decisions were difficult. I was also impressed at how seriously the “mission” of ITCS was taken into account during the reviewing process. The PC chair, Tim Roughgarden, put a strong emphasis on selecting papers that fit the single sentence in the ITCS call for papers that seeks to distinguish it from other conferences:

ITCS (previously known as ICS) seeks to promote research that carries a strong conceptual message (e.g., introducing a new concept or model, opening a new line of inquiry within traditional or cross-interdisciplinary areas, or introducing new techniques or new applications of known techniques).

This is not to say that strong submissions should be rejected if their “conceptual message” was not apparent. This would be a mistake, for who are we to judge of the presence, and even more so future importance, of a new concept? Only time will tell. But given the large number of strong submissions, difficult decisions had to be made, and in many cases the discussion did seriously take into account what we perceived as the conceptual novelty, or appeal, of a submission. The debate was often extensive; I can assure you that most submissions received very careful attention.  I wish the authors, or even the community at large, could get precise feedback on the discussions, which had the benefit of raising awareness, at least among PC members, of the above quote from the CFP.

We also had some discussions on the format of the conference; because these discussions happened after the formal publication of the CFP I’m not sure we can expect any big changes to the format this year, but I hope that they may lead to improvements in later years. Some of the suggestions that were floated around included having invited talks, varying the length of contributed talks, and having a poster session, possibly preceded by short 3-4 minute “advertisements” of the posters by their authors. Personally I think this is an excellent idea, and I hope it gets implemented in a later edition.

To get back to my opening comment — why did we accept so few papers, if the submissions were so good? Well, if you’re angry your paper got rejected, I can only promise that the accepted ones were at least as good — come and check them out! Indeed, in my mind (I am not pretending to speak for the whole PC here!) the main reason is this: ITCS will be single track, it will be relaxed and friendly, and all presentations will be of high quality. We had to make decisions; some of them were right, some were wrong, and many could have been done either way. But we had to make them, and made them for you. So we hope to see you in January 2015 in Israel, and that you’ll enjoy hearing the talks as much as we enjoyed reading and debating the papers!

About Thomas

I am a professor in the department of Computing and Mathematical Sciences (CMS) at the California Institute of Technology, where I am also a member of the Institute for Quantum Information and Matter (IQIM). My research is in quantum complexity theory and cryptography.
This entry was posted in Conferences and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s