Sign In

Communications of the ACM

Communications of the ACM

Why Doesn't ACM Have a SIG for Theoretical Computer Science?

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."


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

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.