本周日（11月28日）下午三点到五点，学堂112，范致远、武弘勋同学会分享自己的工作，时长约为一到两小时。
范致远：The Exact Complexity of Pseudorandom Functions
范致远、李嘉图和杨天祺是姚班2019级本科生。本次seminar范致远将介绍他们在密码学与计算复杂性理论中的工作。伪随机函数(pseudorandom functions)是无法与随机函数区分开的函数族。作为密码学许多构造的起点是密码学的基础，构造高效的伪随机函数在理论及应用中有多种意义。他们最近的工作研究了伪随机函数的电路复杂性，在多个重要的电路复杂性类中对伪随机函数给出了几乎紧的上界与下界。这些上下界结果为电路复杂性理论提供了新的见解，也刻画了一些障碍。本次talk中，他们将主要介绍在一般电路(general circuits)下的结果，包括如何在 2n+o(n) 的电路复杂度内构造伪随机函数（假设伪随机函数存在），以及一个与之相对应的 2n-O(1) 的下界证明。
武弘勋：Element Distinctness, Birthday Paradox, and 1-out Pseudorandom Graphs
武弘勋是计科80本科生。本次seminar将会介绍在春研期间，他和陈立杰（计科30）、金策（计科60）两位姚班学长，以及他们的导师Ryan Williams合作的工作。Element Distinctness 问题是一个很基础的计算问题：给出只读的 n 个数，如何判断它们是不是两两不同？在比较模型（Comparison Model）下，姚先生 [Yao88] 证明了时间复杂度 S 和空间复杂度 T 的最优tradeoff为 ST = O(n^(2 ± o(1)))。而在RAM模型（读入支持随机只读访问）下，假设 Random Oracle 存在，[BCM13] 证明了存在一个算法可以超越这个比较模型的最优tradeoff，它的时间空间 tradeoff 为 ST^2 = Õ(n^3)。其中最有趣的Open Problem是，在 RAM 模型下，当空间限制为 Õ(1) 的时候，不假设 Random Oracle，是否能做到 Õ(n^(3/2)) 的时间复杂度？本次talk中，将会介绍如何利用伪随机性来取代 Random Oracle, 从而解决这个 Open Problem。同时对于 Subset Sum 问题，[BGNV18] 假设 Random Oracle 存在，提出了一个多项式空间，O*(2^(0.86n)) 时间的算法。这个构造同样也可以取代其中的 Random Oracle 假设。
Make IIIS Great Again!
