交叉信息院本科生获评2022计算理论年会最佳学生论文,多位师生、校友论文被接收
2024/04/28
近日,计算机科学领域顶级国际会议第54届ACM计算理论年会(STOC 2022 54th Annual Symposium on the Theory of Computing)官网公布,清华大学交叉信息研究院师生及校友共有7篇论文被接收,其中计科班(简称“姚班”)91班范致远、计科92班李嘉图与杨天祺三位同学共同完成的论文“伪随机函数的精确复杂性与计算复杂性理论中自举现象的黑盒自然证明障碍”(The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity)被大会接收,并获评最佳学生论文。
伪随机函数(pseudorandom functions)是无法与随机函数区分开的函数族。它作为密码学许多构造的起点,是密码学的基础。因此构造高效的伪随机函数在理论及应用中有多种意义。该论文研究了伪随机函数的电路复杂性,在多个重要的电路复杂性类中对伪随机函数给出了紧的上界与下界。例如证明了在一般电路中,若多项式大小的电路可计算的伪随机函数存在,则存在一个仅需大约2n个门的电路族即可计算的伪随机函数。同时,该研究无条件地证明了计算任何伪随机函数至少需要2n-2个门。

论文插图:两层线性阈门电路
这些上下界结果为电路复杂性理论提供了新的理解,也解释了为何一些广为相信的猜想难以被证明。特别地,针对目前电路复杂性理论中存在的“自举现象”(bootstrapping phenomena),该研究指出,要想从这些现象推出P vs NP等重要开放问题的答案,还需要一些全新的证明思路。
ACM计算理论年会(STOC)是理论计算机科学领域最顶级的国际会议,在整个计算机科学领域享有崇高的声望,并被公认是难度最高的会议之一。STOC2022将于意大利罗马召开,本次会议共接收论文投稿457篇,录用135篇,接收率约为29%。
文章来源清华大学新闻,分享只为学术交流,如涉及侵权问题请联系我们,我们将及时修改或删除。
-
2026年1月高含金量国际学术会议合 12-12
-
第四届金融科技与商业分析国际学术会议 686
-
2026年第十一届复合材料与材料工程 1453
-
2025年机器视觉、智能成像与模式识 2126
-
2025年智能光子学与应用技术国际学 3284
-
2026年机械工程,新能源与电气技术 3476
-
2025年计算机科学、图像分析与信号 3917
-
2025年材料化学与燃料电池技术国际 3633
-
2026年交通数字化、人工智能与韧性 12-19
-
2026年社会文化与公共管理国际会议 12-19
-
2026年人文地理与语言研究国际会议 12-19
-
2026年社会发展与经济发展国际会议 12-19
-
2026年光伏材料、光电转换与可再生 12-19
-
2026年可持续发展与数字化社会国际 12-19
-
2026年管理科学、语言与教育国际会 12-19
-
2025年两院院士增选有效候选人2672
-
2025最新JCR分区及影响因子7552
-
好学术:科研网址导航|学术头条分3540
-
2025年国际期刊预警名单发布!3510
-
2025年中科院期刊分区表重磅发13412
-
中国科协《重要学术会议目录(207866
-
吉林大学校长张希:学术会议中的提4517
-
中国科大提出电化学一体化驱动策12-19
-
中国科大实现电泵浦片上集成高亮度12-19
-
西北农林科技大学【陕西新闻联播】12-19
-
中国科大实现片上非相干泵浦高品质12-19
-
中国科大中性原子量子计算研究成果12-19
-
炔烃远端C-O键的不对称活化转化12-19
-
研究揭示叶片内生真菌分子功能多样12-19
-
科研人员提出柑橘黄龙病防控新策略12-19
-
华中科技大学脑研究所 23326

-
北京麦迪卫康广告有限公司 21225

-
全国医药技术市场协会 17966

-
FEA 8195

-
全国卫生产业企业管理协会抗菌产业 21157

-
沈阳博思教育咨询有限公司 23044

-
自动化所 8229

-
北京鸿腾瑞达广告 2192

-
河湖生态大会组委会 23248

-
国防科大计算机学院 18404

-
新疆光大旅行社 18157

-
北京国科企研信息咨询中心 2327

-
2016年教育科学与人类发展国际 2121

-
江苏省岩土力学与工程学会 18446

-
清华大学机械工程学院 18504

-
辽宁省医学会学术部 18156

-
中国广东东莞 18164

-
中国化 学会 21335

-
上海英致商务咨询有限公司 24069

-
Focussend 24039

















740









































