本周六下午 14:00-16:00，我们将在学堂 112【线下】给大家带来王一川、马耀华同学的报告。报告内容与计算复杂性、密码学相关。在报告前后，同学们可以吃零食 and/or 自由交流。
报告 1 摘要
王一川是姚班 2021 级（计科 12）本科生，他的主要研究方向是计算复杂性理论，曾在理论计算机科学会议 CCC、SODA 上发表论文。本次 seminar 他将带来关于电路复杂度下界中的算法方法（the algorithmic method）的科普讲座。在电路复杂度下界的研究中，人们试图先证明较弱的电路无法计算某些函数，再逐步加强到一般的电路。在 1980 年代，人们先后证明了 AC0 电路（常数深度，允许非门以及多个输入比特的与门、或门）、AC0[2] 电路（额外允许多个输入比特的 MOD2 门）的电路下界。然而，整个领域接下来在 AC0[6] 电路（额外允许多个输入比特的 MOD6 门）停滞了二十余年，直到 2010 年 Ryan Williams 的突破。Williams 提出了一种全新的证明电路复杂度的方法 the algorithmic method，证明了 NEXP 无法被 ACC0 电路（额外允许多个输入比特的“MOD 常数”门）计算。本次讲座将为大家科普 the algorithmic method，向大家介绍理论计算机科学的一些现代思想。
报告 2 摘要
马耀华是姚班 2021 级（计科 12）的本科生，他的主要研究方向为理论密码学。在本次 Seminar 中，他将分享在卡内基梅隆大学 Elaine Shi 研究组春研期间与同学代晨昕（计科 12）共同完成的关于程序混淆 (indistinguishability obfuscation) 的研究。程序混淆是现代密码学中的尖端科技，被誉为“现代密码学中的瑞士军刀”，在函数加密（functional encryption），多方安全计算（multi-party computation），简洁非交互式论证（SNARG）等领域中有着广泛应用。此前对程序混淆的研究大多着眼于其可行性，在运行效率方面都有着较大的多项式因子，难以投入实际应用。在本工作中，基于程序间短形式逻辑的等价性证明（succinct functional equivalence proof）的存在性假设，他们提出了首个近线性（quasi-linear）的程序混淆算法，并给出了多个该算法的应用。本工作已被 Eurocrypt 2025 接收，论文链接：https://eprint.iacr.org/2025/307
欢迎全体同学参加~
Make IIIS Great Again!
