本周我们将在【线上】为大家带来任翰林学长关于计算复杂性理论的报告！
任瀚林
任瀚林是姚班2016级毕业生，现为牛津大学博士二年级，导师是Rahul Santhanam，研究方向是计算复杂度理论。本次seminar他将介绍他和合作者们在电路值域回避问题（circuit range avoidance）上的研究成果。 概率方法（probabilistic method）是组合数学中非常重要的技术，很多组合对象的存在性都可以用概率方法证明。最典型的例子是电路复杂度下界（circuit lower bounds）：用概率方法很容易证明非常强的电路复杂度下界。但是，概率方法是非构造性的，也就是说就算我们用概率方法证明了某个组合对象的存在性，我们也并不知道应该如何显式地（explicitly）构造出符合条件的组合对象。最近的研究表明，概率方法可以由电路值域回避问题（range avoidance problem）刻画，如果该问题有高效的确定性算法，那么所有由概率方法推出的存在性证明都可以改造成构造性证明。本次seminar将介绍在解决值域回避问题上的最新进展，以及这些进展带来的电路复杂度中新的推论。
欢迎全体姚班同学参加！
Make IIIS Great Again!
