Computing Applications

Why Doesn’t ACM Have a SIG For Theoretical Computer Science?

  1. Article
Communications Editor-in-Chief Moshe Y. Vardi

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.


Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More