## Quid ITCS?

Earlier this week I attended the fifth edition of the ITCS (“Innovations in Theoretical Computer Science”) conference, which took place over the course of three days in a beautiful, stately auditorium inside the Field center on the Princeton University campus. This was my first time attending the conference and, given the noise that surrounded the series’ launch just a few years ago, I was quite eager to finally experience it first-hand.

ITCS was created with great fanfare just a few years ago: initially named ICS, the first two installments, in 2010 and 2011, were held at Beijing’s famous Tsinghua university; one of their noted features was that an author of each accepted paper got a free ticket to the conference, including airfare, hotel, etc. The first ICS had an ambitious call for papers, emphasizing “research that carries a strong conceptual message (e.g., introducing a new concept or model, opening a new line of inquiry within traditional or crossdisciplinary areas, or introducing novel techniques or novel applications of known techniques)”, together with a substantial steering committee to back it up. Much was made at the time of ICS’s purposefully distinctive focus (as opposed to STOC, FOCS, or other TCS conferences sometimes decried as “too technical” or “narrow-minded”), and I remember heated debates on the blogosphere (see e.g. herehere or here for a sample and further links). Given such high expectations, I was curious: had the conference lived up to its promise?

A digression on conflicting publication venues

The reason for my attendance this year could be taken as a positive sign that it had. While the two papers I presented at the conference fall squarely within the realm of TCS, my co-authors and I strongly felt that the results should be publicized to a wider audience as well (in our case to theoretical physicists). ITCS, as opposed to STOC or FOCS, allowed for this possibility. Before explaining this, let me briefly describe the papers in a way that I hope makes it clear why we think it worthwhile to make the results accessible, not only to the TCS community, but also to researchers in physics:

The first paper provides the first complete proof of security for a cryptographic protocol for key distribution having the distinctive property that, although the protocol relies on quantum mechanics to achieve unconditional security (this would be impossible classically), the proof of security holds even in a setting where all the quantum devices used in the protocol are untrusted (they could even have been designed by the adversary!). The proof is based on ideas from computer science (such as randomness extractors or techniques borrowed from the analysis of parallel repetition of multiplayer games), but the end result has a strong bearing on our understanding of a phenomenon known as monogamy entanglement. The latter has received a lot of interest recently, and plays a role in areas ranging from the study of phase transitions in condensed-matter physics to the theory of black holes.

The second paper introduces a polynomial-time algorithm for a problem of interest in many-body physics: computing the ground state of a 1D gapped local Hamiltonian. The algorithm builds upon widely used techniques in computer science (dynamic programming; convex optimization and semidefinite programming; matrix-valued concentration bounds) but the end result, beyond its (probably impractical) use as an algorithm for the simulation of physical systems, demonstrates important properties of gapped systems that go beyond the celebrated “area law” that they have been shown to exhibit.

My co-authors and I thus strongly felt that, although the results should be published in a TCS venue (we are computer scientists, and we — though I should really only speak for myself — view these results as results in, made possible by, and of interest to computer science), they should also be publicized to the appropriate audience in physics. How could this be done? In computer science we are used to publishing an initial version of our results in conference proceedings, with the infamous “full version” eventually submitted to a journal (I will not get into the debate of whether this traditional distinction is still relevant…see this post by Sanjeev Arora for a recent discussion). In physics, papers are published directly in a journal; conferences are reserved for short, often invited, presentations, and do not have published proceedings. These differences lead to differences in copyright and priority handling: TCS conferences strongly insist that the submitted material has not appeared (nor even been submitted) elsewhere, while TCS journals are willing to publish minor updates on conference papers. In contrast, physics journals tend to have extremely restrictive copyright policies. To make a long story short (see this post by Umesh Vazirani for more), we were stuck: publication in a TCS conference is all but incompatible with publication in a Physics journal (such as Science or Nature), irrespective of how you do it (believe me, we tried!). Unless…one would treat the TCS conference as what it is, a conference, and not a publication, by submitting (and presenting) the full paper, but only publishing a very short one-page abstract in the proceedings (pointing to a full version of the paper from the arXiv). While STOC and FOCS do not currently allow this, ITCS has been explicitly permitting the publication of very short abstracts since last year. So we submitted to ITCS…and, even though the process of unentangling ACM’s copyright policies was by no means straightforward, we eventually found a workable solution — and I got to attend the conference!

Impressions from this year’s ITCS

1. The format

The first thing that struck me, as a presenter, is that the program seemed quite dense: there were four 90-minute sessions per day, each consisting of four 20-minute talks together with a 10-minute introduction by the session chair. This meant, first, that the schedule went on from 8:30am till 5:30pm each of the three days (including a welcome 2-hour lunch break), and second, that each talk was allotted 20 minutes, including questions and switching of speakers. In other words, I better prepare for a 15-minute talk — and still somehow manage to carry the “conceptual message” across!

Why such a crammed schedule? The CFP for the first ICS explicitly stated that “the total number of papers will be around 30, so as to allow for ample time for open and one-on-one discussions and exchanges of ideas.” In fact, the first PC barely kept in line with this requirement, as 39 papers were accepted to the conference. Since then the sentence has disappeared from the CFP, and this year there were 48 accepted papers (roughly the same count as last year). Although this only represents an additional 10 papers, it’s 20 more than the initial CFP called for. (Admittedly, the original ICS CFP also called for a conference spread over two and a half days, a requirement which seems never to have been implemented.) For comparison, STOC or FOCS typically accept around 70-80 papers, and have two tracks; ITCS has a single track. So the average load is similar — but STOC or FOCS don’t have an explicitly stated goal of “allowing for ample time for open and one-on-one discussions and exchanges of ideas”.

The space inside the Fields institute

In spite of the overloaded schedule, the fact that there was a single track did give ITCS a more relaxed feel than multiple-track conferences. It’s hard to pin down why exactly, but the difference is significant. Maybe it’s simply that it’s so much more pleasant to be able to simply walk into the designated conference room trusting (hoping) that the PC has done a good job and one is about to hear interesting work. No worrying about what is going on in the other room, and should I switch, and risk being caught up in one of the incessant hallway discussions — discussions which are certainly an integral part of the conference, but maybe there can be time for both! Even though total participation was fairly low (around 80 registrants or so), the talks were well-attended. The long coffee and lunch breaks allowed for ample discussion time; it helped they were held in a very nice 3-4 loosely divided rooms (together with a smallish “library”) with chairs, couches, and tables organized in various configurations which made it possible to comfortably accommodate all kinds of conversations and group sizes. Compared to the generic STOC ballroom-, or worse, corridor-style break area this was a big plus of the conference.

Another distinctive feature of ITCS are the 10-minute introductions given by session chairs at the beginning of each four-paper session. The chairs allocated those 10 minutes in more or less creative ways: while some simply distributed their minutes to the speakers, allowing a little extra (much needed) time for questions, others attempted a more in-depth introduction, including slides, to place the session’s papers in context. Some of these presentations were good, but not all were successful. It is not always easy to warm up the audience to yet another topic in such short time; being in the audience I also felt some impatience at hearing the results themselves, and found it difficult to not let my mind wander during the introduction. Maybe those could be kept shorter, to just 2-3 minutes for presenting the topic of the session; instead of a lengthy introduction it might be more beneficial if the chair placed his or her efforts into coming up with good questions to stimulate discussion after the presentations. (I’m not blaming the session chairs…some of the introductions were quite helpful; it’s not an easy task.)

2. The talks

Now, this is all good, but what about the talks themselves? ITCS’s main claim to fame lies in the following two sentences of its CFP:

“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). ITCS welcomes all submissions, whether aligned with current theory of computation research directions or deviating from them.”

The above statement is the only part of the CFP that relates to the content of submissions (as opposed to formatting guidelines). Since the second sentence has essentially zero content (either ${x}$ or ${\neg x}$…), we are left hanging on the first. I wonder if the statement is purposefully elliptic; note that it does not even state what is desired of submissions, but only what the conference “seeks” to achieve. If this happened to be the first time I encountered ITCS I could be forgiven for being puzzled at the conference’s scope, and for being hesitant as to whether I should submit my results there. In contrast, the CFP for this year’s STOC clearly states “submissions presenting original research on the theory of computation are sought. Topics of interest include but are not limited to:”, followed by a long list of topics.

Now for the real question: did the program of this year’s ITCS achieve its stated goal of “promoting research that carries a strong conceptual message”? I’ll let you have a look at the program and judge for yourself. I have mixed feelings. On the positive side, a solid fraction of the results did have a twist to them that is less often seen in STOC/FOCS papers. Some papers, such as “Cryptogenography” by Brody et al. or “Building one-time memories from isolated qubits” by Liu, introduced a new model (the setting for the former paper is that one among a group of cooperating players holds a secret bit, and the goal is for the group to openly communicate in a way that any eavesdropper can learn the secret bit, but not the identity of its holder; the latter paper introduces a model of security in which the eavesdropper is not allowed to make entangling operations — a requirement presumably enforced physically by choosing an implementation for the OTM scheme that makes such operations highly impractical). Others, such as “Non-commutative arithmetic circuits with division” by Hrubes and Wigderson, obtained interesting results by studying an unconventional extension of a well-studied problem; such “outside-the-box” approaches can help put current efforts in perspective. Yet others suggested new approaches to hard problems; for instance “Tree Codes and a Conjecture on Exponential Sums” by Moore and Schulman suggests a path towards solving an important open question in interactive coding, but provides no “concrete” results. There was even a session devoted to results with application to, or motivated by, the physical sciences, including “Attribute-Efficient Evolvability of Sparse Linear Functions” by Angelino and Kanade, or “Rate-independent computation in mass-action chemical reaction networks” by Chen et al.

These are all results that I believe would easily fit in STOC or FOCS in terms of quality, but may not eventually make it because of the lack of, either concrete technical progress on a well-known problem deemed important by the community (such as some of the papers introducing novel frameworks whose long-lasting impact is hard to measure), or direct relevance to a well-circumscribed area (such as the papers inspired by the physical sciences). These are the papers that, if one is to follow the CFP, should make the meat of ITCS. The corresponding talks were among the best; it was sometimes (though not always) apparent the speaker knew very well he or she had to “defend her turf”, i.e. find the correct words for promoting the conceptual message of the paper. This led to interesting, fresh talks, and lively discussion sessions.

Those only accounted for about half the papers (by my count…) presented at the conference though. The other half struck me as consisting of much more conventional results, which would more naturally find their place at STOC, FOCS or SODA. I don’t want to point to any specific papers, and in any case I have nothing against them; most were very good results anyways. They would easily fit in any top TCS conference…any but ITCS? I was not on the PC, and unfortunately there was no (publicly announced) business meeting, so I don’t know how the requirement for a “conceptual message” was taken into account when making acceptance decisions; it would be interesting to have some inside information about this. Was there a target number of accepted papers, and if so what was it — did it get exceeded? How much weight was conceptual novelty given in the decisions? If it was taken into account, what was the rationale behind accepting this “second batch” of papers? Do they have some novelty that I simply am not seeing? The point here is not to criticize the work of the PC or the papers themselves, but to pose to question of “how far” ITCS is willing to go in sticking with its stated goals. Was there a compromise, and if so why? Could the program not be made much shorter, while still keeping a high-quality conference, that many would willingly attend (and perhaps even more so than are induced by accepting yet more papers)?

Why do we go to conferences?

Thinking through my experience with ITCS, the question I am brought back to is a most basic one: why do I go to conferences? What do I expect out of them? After all, it takes quite some effort to attend: the travel, the costs, etc. Here are some seemingly obvious answers: 1. to hear about exciting new research in TCS that I may not have heard about otherwise; 2. to have the ideas driving this research explained to me in a clear and insightful way by select speakers; 3. to catch up with the remainder of the community over pleasant social events such as a dinner, coffee breaks, rump session, etc.; and 4. as a result of 1.-3., to emerge from the conference with i) the refreshing feeling of belonging to a dynamic research group that is constantly re-inventing itself, and ii) research ideas!

What is unfortunately much less obvious is whether any of these goals are being kept in mind when shaping our conferences; for that matter it is unclear, at least to me, what their actual goals are (if any!). This is at least one merit of the ITCS CFP: it states an explicit goal for the conference, “ITCS seeks to…”. I’ll end this post by describing some thoughts, or suggestions, as to how one could make progress towards achieving the four goals stated above. For the fun of it I’ll express my suggestions in the present tense, as if I was describing an already existing “dream” conference which I’ll call “XTCS”.

1. Single track.

One of the distinctive features of XTCS is its relatively small program, organized around a single track of talks. The CFP makes it clear that this small number of accepted talks is the result of a design decision, rather than out of necessity (e.g. too few good submitted papers). There are many benefits to having a small program. One of the main such benefits is the indirect pressure it puts on the PC: less accepted talks means a higher strain on “getting it right”. As an attendee, it means I can trust that the SC and PC have put together a strong, pointed program, and divided it into coherent sessions; the speakers, assured of a broad audience, have carefully prepared their talks; their public is curious and focused. Even if I can’t immediately parse the title of the talks I still attend most of them. At XTCS the chance that I will discover a new topic, a new conceptual idea, a new bridge between areas, is much higher — and this is precisely because there are fewer, better-selected talks.

In addition, XTCS has a small number of specially selected (either taken from the best submissions or by invitation) longer talks, perhaps 45-minute or an hour-long. These talks are one of the main reasons I attend the conference: they are guaranteed to be of high quality and present novel ideas; they are the kind of talks that no paper-reading can replace. Similar to some of the “prize talks” at STOC or FOCS (indeed I was surprised to discover that ITCS did not have a single such broader talk, apart from the after-dinner talk by Peter Winkler), these can be given by reputable speakers from our field, as well as by speakers from neighboring fields who have something to tell us. Selecting such talks is the business of the SC; in fact it is one of their most important tasks in putting a successful conference together: identify novel ideas, promising directions, that will shape the future of the field.

2. Computation as a lens

XTCS has a purposefully broader scope than other conferences in theoretical computer science. This is in keeping with the “computation as a lens on the sciences” motto that is increasingly adopted, in various guises, by TCS communities (see e.g. Berkeley’s Simons institute mission statement). If anything, this motto best embodies the future of our field; XTCS is its conference. Which doesn’t mean that “purely TCS” papers should be excluded; only that papers accepted to the conference will be required to have a bearing outside of themselves. For instance, a paper whose main result is “we prove that the permanent does not have polynomial-size circuits” might not be accepted, whereas a paper claiming “we show that not all efficiently verifiable assertions can be efficiently decided” might be. The example is a a bit extreme and I don’t mean it to be taken literally, but I chose it for two reasons: first, to emphasize that an “application to the physical sciences” is by no means necessary, and second, that even though the difference is only one of formulation, formulation matters (after all, a conference is all about presentation!). Here the second formulation emphasizes the significance of the result; the first focuses only on the technique that is used to obtain it.

Another way XTCS encourages inter-disciplinarity and avoids being overly self-centered is by remaining as international as possible. XTCS strives to avoid the kind of “inner circle” complaints that are sometimes made about STOC or FOCS (be they justified or not), and keeping its audience as geographically diverse as possible helps. The reason I have most often heard for locating a conference in the US are the travel costs, but I don’t think this is really justified: accommodation can be cheaper in Europe (depending on location), and the extra cost in terms of airfare remains reasonable; compared to the total cost of attending it represents perhaps a 20 or 30% increase. Financial support for students is a priority: registration costs can be increased for faculty, and decreased for students and postdocs.

3. Community building

In addition to the importance of the wording used in the CFP, which is given more prominence than at “traditional” conferences, XTCS takes a few small but concrete steps towards reinforcing the sensation of a “TCS community”. One such step is the organization of the sessions, in which the chair is given a slightly more important role than usual: she is responsible for saying a few words, either about the importance of each work, or about the session’s topic as a whole, and for asking pointed questions that will encourage discussion. There may even be a “rump session” in which students are encouraged to present their latest results, and throughout which one is generally encouraged to discuss half-baked ideas. The rump session can be paired with a poster session around which more serious discussions can be pursued.

Ample time is given to coffee breaks and lunches. The conference location is chosen carefully so as to allow for interactions ranging from casual discussion to focused research discussions. Large hotels in city centers are avoided (to avoid the crowd dispersing too easily); university halls are preferred (this can also help keep the costs down).

4. Submission format and proceedings

Submissions to XTCS are short; perhaps three to five pages. This forces the authors to present the main point of their research in an accessible way. The five-page abstract should be accompanied by a more technical version of the paper, which can be a pointer to the arXiv. Accepted papers are required to have their full version made available online by the time of the conference. XTCS has no published proceedings. Instead, it has a well-maintained website which lists each year’s accepted papers, together with their five-page abstracts and pointers to the online version.

Will you come to XTCS?