[Boaz’s note – this is another in the series of personal posts on STOC/FOCS reform, this time from Moshe Vardi, a renowned theoretical computer scientist who is also the editor in chief of the communications of the ACM. See also the discussion that’s still going on in the comment section of Omer Reingold’s post, as well all discussions under this tag.]
Why Doesn’t ACM Have a SIG for Theoretical Computer Science?
Moshe Vardi
Wikipedia defines Theoretical Computer Science (TCS) as as the “division or
subset of general computer science and mathematics that focuses on more
abstract or mathematical aspects of computing.” This description of TCS
seems to be rather straightforward, and it is not clear why there should be
geographical variations in its interpretation. Yet in 1992, when Yuri
Gurevich had the opportunity to spend a few months visiting a number of
European centers of research center, he wrote in his report, titled “Logic
Activities in Europe” that “It is amazing, however, how different computer
science is, especially theoretical computer science, in Europe and the US.”
(Gurevich was preceded by E.W. Dijkstra, who wrote an EWD Note 611 “On the
fact that the Atlantic Ocean has two sides.”)
This different between TCS in the US (more generally, North America) and
Europe is often described by insiders as “Volume A” vs “Volume B”, referring
to the Handbook of Theoretical Computer Science, published in 1990, with
Jan van Leeuwen as editor. The Handbook consisted of two volumes: Volume A,
focusing on algorithms and complexity, and Volume B, focusing on formal
models and semantics. In other words, Vol. A is the theory of algorithms,
while Volume B is the theory of software. North American TCS tends to be
quite heavily Volume A, while European TCS tends to encompass both
Volume A and Volume B. Gurevich’s report was focused on on activities of
the Volume-B type, which is sometimes referred to as “Eurotheory”.
Gurevich expressed his astonishment to discover the stark different
between TCS across the two sides of the Atlantic, writing that
“The modern world is quickly growing into a global village.”
And yet the TCS gap between the US and Europe is quite sharp. To see it,
one only has to compare the programs of the North American premier TCS
conferences–IEEE Symposium on Foundations of Computer Science (FOCS)
and ACM Symposium on Theory of Computing (STOC)–with that of Europe’s
premier TCS conference, Automata, Languages, and Programming (ICALP).
In spite of its somewhat anachronistic name, ICALP today has three tracks
with quite a broad coverage.
How did such a sharp division arose between TCS in North America and Europe?
This division did not exist prior to the 1980s. In fact, the tables of
content of the proceedings of FOCS and STOC from the 1970s reveal an
surprisingly (from today’s perspective) high level of Volume-B content. In
the 1980s, the level of TCS activities in North America grew beyond the
capacity of two annual single-track three-day conferences, which led to the
launching of what was known then as “satellite conferences”. Having shed
“satellite” topics, allowed FOCS and STOC to specialize, developing a
narrower focus on TCS. But the narrow focus of STOC and FOCS, the two
premier North American conferences, in turn has influenced what is
considered TCS in North America.
It is astonishing therefore to realize that the turn “Eurotheory” is
used somewhat derogatorily, implying a narrow and esoteric focus for
European TCS. From my perch as Editor-in-Chief for Communications, today’s
spectrum of TCS is vastly broader than what is revealed in the programs of
FOCS and STOC. The issue is no longer Volume A vs Volume B or Northern
America vs Europe (or other emerging centers of TCS around the world),
but rather the broadening gap between the narrow focus of FOCS and STOC
and the broadening scope of TCS. It is symptomatic indeed that unlike
the European Association for Theoretical Computer Science, ACM has no
Special Interest Group (SIG) for TCS. ACM does have SIGACT, a Special
Interest Group for Algorithms and Complexity Theory, but its narrow focus
is already revealed in its name [Paul Beame comments below that SIGACT stands for “Algorithms and Computation Theory” -B.].
This discussion is not of sociological interest only. The North
American TCS community has been discussing over the past few years
possible changes to the current way of running its two conferences,
considering folding FOCS and STOC into a single annual conference of
longer duration. A May 2015 blog entry by Boaz Barak is titled “Turning
STOC 2017 into a ‘Theory Festival'”. The proposal is focused on changing
the conference from the standard recitation of fast-paced research talks,
to a richer scientific event, with invited talks, workshops and tutorials,
social activities, poster and rump session, and the like.
I like very much the proposed directions for FOCS/STOC, but I’d also like to
see the North American TCS community show a deeper level of reflectiveness
on the narrowing of their research agenda, starting with the question posed
in the title of this editorial: Why doesn’t ACM have a SIG for Theoretical
Computer Science?
Windows On Theory 
Moshe, thanks for raising this issue.
I must admit that our committee isn’t yet grappling with it. We are imagining occasional invited talks in what you would call theory B, but realistically most would be in fields with strong overlap with theory A: COLT, PODS, PODS, CRYPTO, KDD, etc. Doing full justice to theory B would be a whole different game.
I have been at ICALP only a couple of times in recent years. Do the audiences for the A and B tracks mix much?
Also, have you looked into whether there is a difference in research cultures in other subfields of CS? CS depts don’t seem to hire many European PhDs, even outside of theory, so I suspect the Atlantic ocean has two sides there as well.
Sanjeev Arora
When you have conference with parallel tracks, people do attend talks from different tracks to some extent, but also attend plenary talks, and get to know each other in social events.
Moshe: There is an important correction to your note: The ACT in SIGACT stands for “Algorithms and Computation Theory”, NOT “Algorithms and Complexity Theory” as your post claims. Indeed the two ACM Transactions journals that have been founded by SIGACT are ACM Transactions on Algorithms and ACM Transactions on Computation Theory. (Until the 1990’s, the ACT stood for “Automata and Computability Theory” somewhat like the archaic ICALP title.) The typical STOC conference has much more than algorithms and complexity theory papers.
One thing that has happened over the years is that some focus areas of TCS have developed strong relationships with areas of application. I would say that a higher fraction of the strong conferences most related to Theory B topics have gravitated to connections with their application areas, including conferences such as POPL, PODS, CAV. (PODC which SIGACT co-sponsors with SIGOPS has a mix of both Theory A and Theory B aspects.) With a focused conference like PODS, there is a great value in being close to applications and the co-location with SIGMOD works very well. Obviously, when some of these conferences were created or spun off from STOC/FOCS, it did pull those researchers along with them.
Thanks for catching my error regarding the meaning of SIGACT!v
Thanks Moshe for a very thought-provoking post.
It’s probably worth pointing out that (as you know) a new SIG on “Logic and Computation” — ACM SIGLOG — has recently been launched, broadly representing Volume-B Theory, with LICS as flagship conference. It’s probably fair to say, sadly, that these two “Theory” communities are not mixing together terribly well at the moment, despite there being a rich potential (in terms of shared or related problems and techniques) for them to do so. I wonder what the way forward might be?
Thanks, this was useful info. I suppose the “amicable separation” is now official.
Just to be clear: LICS was solely an IEEE conference for many years. It was sponsored by the same TC as FOCS and CCC. After a lot of work both in lobbying by TCMF and LICS leadership of IEEE officialdom to let it happen, and on the ACM side to make it work, LICS finally became jointly sponsored by ACM SIGACT in 2012.
The goal of those working on the change from both sides, Moshe and myself included, was always for the creation of ACM SIGLOG. The problem at ACM was a chicken and egg problem: A SIG without a flagship ACM conference was not an option, but a conference could not become jointly sponsored without a sponsoring SIG. SIGACT acted as a foster parent in this case and we strongly lobbied to allow for the creation of SIGLOG last year.
This was not a matter of any recent separation. CCC (originally Structures) was created in the same year as LICS, 30 years ago. SODA was created 25 years ago. Attendees of CCC and SODA continued to remain involved in STOC and FOCS, but, by 6 years later, in my first time on a STOC/FOCS PC, there were precious few Theory B submissions to the conference.
SIGACT has been very supportive and instrumental in the establishment of SIGLOG. Given the current focus of SIGACT, establishing SIGLOG seems the right thing to do.
Let me state some theses, and justify them later:
1. I actually think that the separation between the TOC and TOP communities,
where P stands for programming and C for computation,
is quite natural and justifiable.
(I prefer this terminology rather than “A” and “B”),
2. I agree with Moshe that TCS should mean the combination of both.
3. Needless to say, (1) does *not* imply that TOP be underrepresented in the USA.
Both parts of TCS should be well represented in CS depts.
An interesting question is what is the reason for (3),
whereas Europe does not suffer from that under-representation.
4. FOCS/STOC should be devoted to TOC.
The single TOP sessions that existed in STOC/FOCS in early 1980s were not a good idea; they did not make these venues a true TCS (i.e., they were TOC venues with a “symbolic” representation of TOP). Both TOC and TOP are better without such a lip-service for (non-existing) “unity”.
I assume (1) is the item requires most justification, since (4) follows from it, whereas (2) & (3) merely state obvious claims (about orthogonality of various things).
To discuss (1), one should ask what is a “research community”, what are its borders, and what do these borders serve. These are fundamental questions in the philosophy and sociology of science. If you consider them seriously, you can guess how I am going to justify (1): I claim that it is better to view TOC and TOP as separate/bordering research communities rather than one community (with two sub areas). This definition is not a matter of insignificant semantics; it is operational — indicating how the research groups should interact. In any case, borders are drawn according to interests (i.e., research interests); that is, what are the founding questions etc. The answers are not derived from abstract philosophical considerations but rather from the social reality. The fact that almost all members of TOC are not too interested in TOP, and vice versa, is the key fact. Of course, one can claim that this is an artifact of the reality of separation, but the point is that communities are divided and get merged by the research interests of their members. So currently we have two separate communities, and maybe in the far future they will be merged. Till that time, thesis (4) holds…
Note that the question that I raised was not whether FOCS/STOC should encompass TOP. Rather, I asked why we do not have a SIG for TCS. Right now SIGACT sees itself defined in terms of FOCS/STOC, but I don’t see why this should be the case.
Your question and/or concerns were not totally clear to me. It seemed to me that you raised several issues re TOC/TOP/TCS.
In any case, if SIGACT claims to cover TCS, then it should cover both TOC and TOP. If it only covers TOC, then it may want to change its arcaia name in order to reflect that, and regardless of the name a SIG for TOP would be in place. In short, there are two options:
1. A SIG for TCS, as we both agree it should be define (TOC+TOP); or
2. A SIG for TOC and a SIG for TOP.
Personally, I think option 2 is better.
I think it would make sense to have an umbrella super SIGTCS with three SIGs under it: SIGALG, SIGTOC, SIGTOP.
This maps well to SODA, STOC/FOCS, LICS.
It is worth noting that when I got involved with FOCS/STOC in 1981, the phrase “Theory of Computing” was interpreted very broadly, as the theory that underlies all computational phenomenon. Just take a look at proceedings from the 1970s and you will see many papers about verification, databases, and the like. As TCS grew, and FOCS/STOC narrowed its scope, even the phrase “Theory of Computation” got redefined. Because SIGACT defines itself in terms of FOCS/STOC, SIGACT narrowed its scope too. SIGLOG was an effort to give TOP (though, I’d prefer TOSS–Theory of Software and Systems) a SIG representation. The question is why TCS should be balkanized. In fact, TOC and TOSS do not encompass all of TCS. Do we believe that balkanization of theory SIGs is the desired state?
I don’t think TCS is balkanized. I think the current institutional divide represents a real divide, and a merge is possible and advisable only when reflecting a reality. That is, grassroots (or actual research level) come first, and building formal frameworks come second, although it helps the grassroots identification.
This is also how CS grow out of EE and/or MATH, resp.
This is how TCS split into TOP and TOC,.
When and why this split occurred and deepened is a very interesting question.
In any case, by 1983 (when I started attending FOCS/STOC) the split was a clear fact.
Specifically, by 1983 (if not before), FOCS/STOC were mainly/practically TOC venues, both by the contents of the program and by the composition of the audience (and the PC). At that time there were 1-2 sessions of TOP, which were practically avoided by the vast majority of the attendees (who were TOC guys).
Looking at the 1981 proceedings (of FOCS/STOC), I see a dominance of TOC, but with a noticeable representation of TOP papers. Interestingly, it seems that these TOP papers did not appear in a separate sessions, a practice was solidly in effect already in 1983.
[My claim re 1981 is based on the proceeds, so it is a bit speculative, but starting 1983 I can offer a view of a person who attended almost all events for more than a decade (as far as I recall I missed at most 2-4 out of the 30 that took place in 1983-98).]
Here is one example why the divide is bad for the field: http://cacm.acm.org/magazines/2014/3/172516-boolean-satisfiability/fulltext
Moshe,
I agree with the general point that it is high time many of us looked at real-life complexity of a host of supposedly hard problems. But I don’t think this example illustrates the point you are making.
I suppose you will classify Machine learning under theory A (since logic went out of it some decades ago) and a significant fraction of practical ML consists of solving supposedly intractable problems (like learning deep nets from labeled examples) at large scale.
I do like the idea of having a few theory B invited talks in the new theory festival, to see what possibilities of idea exchange exist today.
Sanjeev
Sanjeev, you will be surprised with the current amount of logic in ML, but if the HB had been published today, it’d probably have a third volume, focusing on the theory of data.
I maintain my main point: Areas split and merge according to the actual interests and activities of the researchers, not according to administrative decisions.
Motivated by the current exchange, I’ve placed a short opinion on my own website;
see http://www.wisdom.weizmann.ac.il/~oded/tcs.html
Thanks Oded for the interesting piece, even though I disagree to a certain extent with your classification; in particular, you seem to be confusing the SIGLOG/LICS community (TOP in your terminology) with SIGPLAN/POPL. There is some overlap of interest between SIGLOG and SIGPLAN, but also vast differences. Have a look, for example, at the list of accepted papers for LICS 2015, taking place next month in Kyoto:
http://lics.rwth-aachen.de/lics15/accepted
Just to give a flavour, the first three papers on that list are the following:
* Michael Blondin, Alain Finkel, Stefan Göller, Christoph Haase and Pierre McKenzie. Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-Complete
* Krishnendu Chatterjee, Monika Henzinger and Veronika Loitzenbauer. Improved Algorithms for One-Pair and k-Pair Streett Objectives
* Tomasz Gogacz and Jerzy Marcinkowski. The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable.
You can see that there is a strong algorithmic/complexity-theoretic theme here; would these kind of results not potentially be of interest to the SIGACT/FOC/STOC/SODA community? My sense is that the answer is yes, and in fact a lot of the techniques used are similar or related. Yet we have two (or more) fairly hermetic communities barely talking to each other…
This being said, Sanjeev’s suggestion to have a few Theory-B invited talks in the new theory festival is very encouraging. The converse is also happening, for instance Piotr Indyk will be invited speaker in Kyoto, Joan Feigenbaum was invited speaker at LICS 2012, and Ryan Williams will be speaking at CSL in Berlin in September.
I am aware of the difference. There are sub-areas in each field/discipline.
The question is when it is correct to talk of areas within a field,
and when it is correct to talk of different fields.
This is not a matter of names but rather an attempt to describe reality by using names (or notions). This translates to very concrete questions like whether one should have a truly joint/shared venues or just guest lectures of one field in its sibling field.
What I or you personally are interested in is relevant to the discussion only as a reflection of what our communities are interested in. So let’s not talk of you and me but rather of communities (or else we’ll get reactions such as Moshe, which I hope was actually a joke).
Seriously. Imagine that you have a joint TOC+TOP venue tomorrow (or next month). I’m note sure what TOP guys will do, but I’m quite sure what TOC guys will do. This can be inferred from what TOC guys did in the early and mid 1980s [see my previous comment…].
N.B.: I said tomorrow or next month (and could have said next year), but i avoided to say ten years from now. Fields are not static. They change all the time. Maybe in ten years, we’ll have TOC+TOP united to a single field. Maybe TOC will split farther, ditto re TOP. This is far too speculative to discuss now. When we get there, we’ll act accordingly. That is, the organizational form will change if the reality will change, and such changes do have a re-enforcing power….
N.B.: I avoided the question of whether what I called TOP is actually SIGLOG+SIGPLAN; for sure your expertise on this is far superior. But as a TOC guy, I can say that I believe that my view of them as something *outside* TOC reflects the view of the TOC community. This does not contradict the possibility that some members of TOC (not many — I’d guess) may be interested in the papers you listed. Some members of TOC are interested in Game Theory, others are interested in Quantum mechanics, etc. (The computational aspects of GT and QM (i.e., CGT and QC, resp) are part of TOC, but GT and QM are not…)
Here is a nice example where logic and ML combine: https://code.facebook.com/posts/1648953042007882?pnref=story
Nice. In general I agree we should be interested in learning more about theory B.
Oded, we get it. You have no interest in our work. This is too bad, as we are very interested in your work!
I did not say that!
I was talking about communities, not about myself.
What I am interested or uninterested is not of public interest.
(E.g., I’m currently not interested in Cryptography at all.., although it is part of TOC…)
I forgot to add a 🙂 to my last comment. It was not too serious!
As you know, I am a “YEKE” (*), you always have to mark jokes for me.
*) For those not knowing the term — it refers to a specific group of Israelis who are alleged to be slow at getting jokes…
Oded, for a nice (IMHO) interaction of TOC and TOP, building on your own work, see http://www.cs.rice.edu/~vardi/papers/dac14a.pdf