Communications of the ACM
Home/Magazine Archive/August 2015 (Vol. 58, No. 8)/Why Doesn't ACM Have a SIG For Theoretical Computer.../Full Text
Communications of the ACM
Why Doesn't ACM Have a SIG For Theoretical Computer Science?
Wikipedia defines Theoretical Computer Science (TCS) 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, 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 U.S." (Gurevich was preceded by E.W. Dijkstra, who wrote an EWD Note 611 "On the fact that the Atlantic Ocean has two sides.")
This difference between TCS in the U.S. (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 Volume A, focusing on algorithms and complexity, and Volume B, focusing on formal models and semantics. In other words, Volume 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 activities of the Volume-B type, which is sometimes referred to as "Eurotheory."
Gurevich expressed his astonishment to discover the stark difference between TCS across the two sides of the Atlantic, writing "The modern world is quickly growing into a global village." And yet the TCS gap between the U.S. and Europe is quite sharp. To see it, one only has to compare the programs of the two 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 arise between TCS in North America and Europe? This division did not exist prior to the 1980s. In fact, the tables of contents of the proceedings of FOCS and STOC from the 1970s reveal a 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." Shedding the "satellite" topics allowed FOCS and STOC to specialize and develop a narrower focus on TCS. But this narrower focus in turn has influenced what is considered TCS in North America.
It is astonishing to realize the term "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 Computation Theory, but its narrow focus is already revealed in its name. In 2014 ACM established SIGLOG, "dedicated to the advancement of logic and computation, and formal methods in computer science, broadly defined," effectively formalizing the division of TCS inside ACM.
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.' "
I like very much the proposed directions for FOCS/STOC, but I would 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?
Follow me on Facebook, Google+, and Twitter.
Moshe Y. Vardi, EDITOR-IN-CHIEF
The Digital Library is published by the Association for Computing Machinery. Copyright © 2015 ACM, Inc.
Comments
Jeff Tansley
"How did such a sharp division arise between TCS in North America and Europe? This division did not exist prior to the 1980s."
Oh yes it did. I am old enough to remember CS in the late 1960's 1970's at Edinburgh. We had an international reputation in theory (CCS etc) and later in practical things like OS, silicon compilers and AI. Being versed in the latter resulted in many trips to the US and Europe but not just to Academic departments but industry as well. My overwhelming impression was that CS in Europe grew out of maths departments while in the US engineering departments were lot more prominent and in closer touch with industry. In those days practical computing cost a lot of money. It was still new and a lot easier for Boards and Councils to say it was just maths (and therefore cheap). Edinburgh along with Manchester and Cambridge was one of the few schools in Europe to have CS classified as a Science/Engineering subject and able to get appropriate funds.
Now of course theory and practice are slightly more integrated but I suggest if you trawled through the commercial pre-eminence of the US and correlated this with relevant theory you will find your explanation. The cynic in me says in the US theory was useful whereas in Europe it was interesting.
Displaying 1 comment