SIGACT is an international organization that fosters and promotes the discovery and dissemination of high quality research in theoretical computer science (TCS), the formal analysis of efficient computation and computational processes. TCS covers a wide variety of topics including algorithms, data structures, computational complexity, parallel and distributed computation, probabilistic computation, quantum computation, automata theory, information theory, cryptography, program semantics and verification, machine learning, computational biology, computational economics, computational geometry, and computational number theory and algebra. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.Theoretical computer science in Europe has a much different balance, putting as much or even more emphasis on automata and logic as it does on algorithms and complexity. So from that point of view (a view shared by Moshe who has strong ties to CS logic) SIGACT does not cover the full range of TCS.
The term "theoretical computer science" just doesn't have a universal meaning. Neither definition is right or wrong, though we all have our biases.
Why does TCS have such a different meaning in Europe and the US? A different research culture and relatively little mixing. Very few North Americans go to grad school, take postdocs or faculty positions in Europe and very few Europeans go the other way, and those that did tended to do algorithms and complexity. Until we started to see web-based archives in the mid 90's, distribution of research between the Europe and US went quite slowly. Things have changed since but by then the different notions of TCS have been set.
SIGACT fully acknowledges that it doesn't do a good job covering the logic community and it has always strongly supported SIGLOG, the special interest group for logic and computation.
I would love to see joint events between SIGACT and SIGLOG. LICS should be part of FCRC with STOC and Complexity or hold a co-located meeting in other years. But SIGACT does do a great job representing the theoretical computer science community in North America.
Another question: why is there even such a subject as theoretical computer science?There are subjects called theoretical physics and theoretical chemistry, but these contrast with strong experimental traditions. In CS the experimental tradition is weak. Its roots are in mathematics and electrical engineering. I am not aware of "theoretical mathematics" or "theoretical electrical engineering".
ReplyDeleteSIGACT and SIGLOG cooperate quite well. Joint events between STOC and LICS would be great. It is clear that the CCC and EC joint events with STOC even outside of FCRC have kept good connections between the communities.
ReplyDeleteAs an example of the connections SIGACT and SIGLOG like to foster, the SIGACT chair has always been an ex officio member of the (large organizing committee for LICS. For a more direct current connection, I am a member of the PC for LICS 2016 in NYC. See the Call for papers.
One comment on the CACM version of Moshe's column: There was an error in discussing the words for the acronym SIGACT in the original Windows on Theory post that got discussed but all that Moshe did was to fix the one word, not the implication he drew from it. Is Moshe really claiming that "Algorithms and Computation Theory" represents a narrow view of TCS?
ReplyDeleteI would like to point out that computational topology which is by now quite an established area has many ingredients as any other theoretical areas mentioned. It's based on a synergy between the classical mathematical topic of topology and algorithms. It is continuing to sip into various areas of applications spawning the area of topological data analysis. For some reason, I dont see it mentioned in the discussions of theoretical computer science...so I take this opportunity to bring it up.
ReplyDeleteOne problem with the term "theoretical computer science" is that its definitions rarely mention what TCS is not about. This often confuses people about what TCS really is.
ReplyDeleteThe SIGACT mission statement offers two seemingly contradictory definitions for TCS. One defines it as the formal analysis of computation, while the other lists some of the topics TCS supposedly covers. Yet the list includes topics that do not fit under the first definition or even under computer science. For example, while most algorithmic research is formal/mathematical in nature, there is also a strong experimental tradition in algorithmics. Computational biology is just computational biology, which is as much a subfield of computer science as experimental science is a subfield of statistics.
Of course, people are supposed to understand that the list of topics only means the formal/mathematical aspects (of the computational aspects) of the listed topics, but it is easy to miss that, if you are not already familiar with theoretical computer science.
Regarding the discrepancy between "European TCS" and "American TCS," as I see it, the roots go back to old times when TCS was not even on the horizon. For example, European philosophers always liked to think about the big questions of human existence, as well as the fundamental fabric of knowledge. At the same time, a characteristically American stream in philosophy was pragmatism, that has never got much traction in Europe.
ReplyDeleteWhy is this so? I think, it is ultimately rooted in history. A very long part of European history was spent in feudalism, which is a rigid system, where the social position and opportunities of an individual are primarily determined by birth. Feudalism is a fundamentally non-pragmatist society, also cemented by religious dogmas. While feudalism was a lengthy part of European history, leading to the still alive heritage of non-pragmatic thinking, it has never existed in the U.S. As a result, American thinking, which evolved exclusively under capitalism, tends to be more pragmatic, than the European line of thought.
In a sense, the TCS discrepancy can be viewed as a modern manifestation of these old differences. For example, algorithms (and complexity, which is ultimately also about algorithms) represent the pragmatist (American) approach. After all, in an algorithm one has to achieve something tangible, under resource constraints. At the same time, the more foundations-oriented European thinking naturally leans toward logic, often with no explicit algorithmic goals.
I saw these differences from first hand experience, because I grew up in Europe, but have been living in the U.S. for quite some time now.
A broader question: why is ACM so dominated by North American people and attitudes? While there have been ACM Presidents (and other office bearers) from Eurpoe/UK, East Asia, etc, they are still unsual, and the bulk of the organization seems to address US-local views and needs. We ought to make ACM a truly international professional society.
ReplyDeleteACM is dominated by North American people, because it's not only an international society, but also a North American regional society. Those two functions don't fit too well in the same organization.
DeleteIn order to make ACM truly international, it should drop its regional activities and establish a separate society for them. Alternatively, ACM could become a truly regional society, while creating a new umbrella organization for the computing societies around the world.
Of course, the fact that we don't already have an international umbrella organization strongly suggests that there's no need for one.