姚班本科生再次于顶级会议STOC发文

2017年06月30日 浏览次数: 0

计算机科学领域顶级国际会议第49届ACM计算理论年会（STOC 2017，49th Annual Symposium on the Theory of Computing）6月19日-23日在加拿大蒙特利尔召开。交叉信息院计科30班王若松、占玮两位同学参与完成的论文《Exponential Separations in the Energy Complexity of Leader Election》被大会接收，并获邀作大会口头报告及海报报告。

在很多由电池供电的无线网络设备中，能量往往是最稀缺的资源。研究表明，无线网络设备大部分能量被用于发送和接收数据包。该论文研究了一种特殊的无线网络模型——电台网中算法的能量复杂度，通过算法设计证明：电台网中各个基础问题确定性算法能量复杂度取决于发送消息的设备是否有碰撞检测能力，而对收听消息的设备的碰撞检测能力并不敏感；与之相反的，确定性算法的时间复杂度取决于收听消息的设备的碰撞检测能力，而对发送消息的设备的碰撞检测能力并不敏感。

该论文是王若松和占玮访问密歇根大学期间在Seth Pettie教授指导下完成的，其他合作者包括Seth Pettie教授的二年级博士生Yi-Jun Chang和博士后Tsvi Kopelowitz。ACM计算理论年会（STOC）是理论计算机科学领域最顶级的国际会议，在整个计算机科学领域享有崇高的声望，并被公认属于难度最高的会议之一。STOC2017共接收论文投稿2590篇，录用638篇，接收率约为24.63%。

版权与免责声明：本网页的内容由收集互联网上公开发布的信息整理获得。目的在于传递信息及分享，并不意味着赞同其观点或证实其真实性，也不构成其他建议。仅提供交流平台，不为其版权负责。如涉及侵权，请联系我们及时修改或删除。邮箱：sales@allpeptide.com