登录
首页
vwin德赢AC米兰官网网址当前版本:2022年11月
ACM通信
为什么ACM没有一个理论计算机科学团体?
维基百科将理论计算机科学(TCS)定义为“一般计算机科学和数学的分支或子集，专注于计算的更抽象或数学方面。”这种对TCS的描述似乎相当直截了当，不清楚为什么它的解释应该有地理差异。然而在1992年，当尤里·古列维奇有机会花几个月时间访问一些欧洲中心时，他在题为“欧洲的逻辑活动令人惊讶的是，计算机科学，尤其是理论计算机科学，在欧洲和美国是如此的不同。(在古列维奇之前的是E.W.迪克斯特拉，他写了一本EWD Note 611“因为大西洋有两面。”)
TCS在美国(更普遍的是北美)和欧洲之间的这种差异通常被业内人士描述为“卷A”vs。卷B，指的是理论计算机科学手册，出版于1990年，简·范·莱文担任编辑。手册包括A卷，重点是算法和复杂性，B卷，重点是形式模型和语义。换句话说，卷A是算法理论，卷B是软件理论。北美的TCS倾向于相当多的卷A，而欧洲的TCS倾向于包括卷A和卷b。Gurevich的报告侧重于卷b类型的活动，有时被称为“欧洲理论”。
古列维奇在发现大西洋两岸TCS之间的明显差异时表示惊讶，他写道:“现代世界正在迅速发展成为一个地球村。”然而，美国和欧洲之间的TCS差距相当大。要了解这一点，只需将两个北美顶级TCS会议的程序进行比较——ieee计算机科学基础研讨会(FOCS)和ACM计算理论研讨会(STOC)与欧洲顶级TCS会议——自动机、语言和编程(ICALP)。尽管它的名字有点不合时宜，但ICALP今天有三个轨道，覆盖范围相当广泛。
TCS在北美和欧洲之间是如何产生如此明显的分歧的?这种划分在20世纪80年代之前并不存在。事实上，20世纪70年代FOCS和STOC会议记录的目录显示(从今天的角度来看)b卷的内容惊人地高。在20世纪80年代，TCS在北美的活动水平增长，超过了每年两次为期三天的单轨会议的能力，这导致了当时被称为“卫星会议”的启动。摆脱“卫星”主题使FOCS和STOC能够专门化，并将注意力集中在TCS上。但这种狭隘的关注反过来又影响了北美的TCS。
令人惊讶的是，“欧洲理论”一词在某种程度上带有贬义，暗示着对欧洲TCS的狭隘和深奥的关注。从我主编的位置上通信在美国，今天的TCS谱系比FOCS和STOC计划中揭示的要广泛得多。问题不再是A卷vs B卷，北美vs欧洲(或世界上其他新兴的TCS中心)，而是FOCS和STOC的狭窄焦点与TCS范围的扩大之间的差距。与欧洲理论计算机科学协会不同的是，ACM没有针对TCS的特殊兴趣小组(SIG)。ACM确实有SIGACT，一个算法和计算理论的特殊兴趣小组，但它的狭隘焦点已经在它的名字中体现出来了。2014年ACM成立了SIGLOG，“致力于逻辑和计算的进步，以及计算机科学中广义的形式化方法”，有效地正式了TCS在ACM内部的划分。
这个讨论不只是社会学的兴趣。在过去的几年里，北美TCS社区一直在讨论对目前举办这两个会议的方式进行更改的可能性，考虑将FOCS和STOC合并为一个持续时间更长的年度会议。波阿斯·巴拉克2015年5月的一篇博客文章题为将STOC 2017变成“理论节”。＂
我非常喜欢FOCS/STOC的建议方向，但我也希望看到北美TCS社区在缩小其研究议程方面表现出更深层次的反思，首先是本文标题中提出的问题:为什么ACM没有理论计算机科学的SIG ?
Moshe Y. Vardi，主编
数字图书馆是由计算机协会出版的。版权所有©2015 ACM, Inc.
评论
杰夫Tansley
“TCS在北美和欧洲之间是如何产生如此明显的分歧的?这种划分在20世纪80年代之前并不存在。＂
哦，是的。我年纪大了，还记得60年代末70年代在爱丁堡的CS。我们在理论(CCS等)方面享有国际声誉，后来在操作系统、硅编译器和人工智能等实际应用方面也享有国际声誉。由于精通后者，我多次前往美国和欧洲，但不仅是学术部门，还有工业部门。我印象最深的是，在欧洲，计算机科学源于数学系，而在美国，工程系要重要得多，与工业联系更密切。在那个年代，实用的计算机要花很多钱。它仍然是新的，董事会和理事会更容易说它只是数学(因此很便宜)。爱丁堡与曼彻斯特和剑桥是欧洲少数几所将计算机科学列为科学/工程学科并能够获得适当资金的学校之一。
当然，现在的理论和实践稍微更加融合了，但我建议，如果你在美国的商业卓越性中搜索一番，并将其与相关理论联系起来，你就会找到你的解释。我心中的愤世嫉俗者说，在美国，理论是有用的，而在欧洲，理论是有趣的。
显示1评论