本周日（4月3日）晚上19:00，学堂112，王修涵同学、郑舒冉学姐会分享自己的工作，时长约为一到两小时。
王修涵：Constant Approximating Parameterized k-SetCover is W[2]-hard
王修涵是姚班2019级本科生。本次seminar他将会介绍他和任轩笛、孙奕灿，以及他们的导师林冰凯在参数不可近似性方面的工作。k-SetCover是一个很基础的问题：给定集合U的n个子集，询问是否能否选出k个子集使得它们的并为U？在多项式时间内，假设P≠NP，近似比为ln(n)的贪心算法是最优的；在参数时间(f(k)poly(n))内，这个问题是经典的W[2]-hard问题。一个自然的问题是，k-SetCover的任意常数近似版本是否也是W[2]-hard的呢？本次talk将会介绍如何使用极值图(Threshold Graph)来解决这个问题。同时，在非参数的意义下，这种方法也可以避开PCP定理来证明多项式时间内o(log(n)/loglog(n))的近似比上界，即使已知答案不超过O(log^2(n)loglog(n))。
郑舒冉：The Limits of Multi-task Peer Prediction
郑舒冉是姚班2013级本科生，现在是哈佛大学的博士生。本次seminar 她将介绍她在计算经济学方向关于peer prediction 的工作。信息和数据是AI最根本的驱动力，而信息和数据很多时候是靠人工获得的，比如机器学习的数据标记(data labeling)，交易平台的商品打分(product review)，学术会议的同行评议(peer review) 等等。在这些问题中，人们提供的信息往往难以验证真实性或是准确性。Peer prediction 研究的问题就是当设计者无法直接验证信息的质量时，如何从人们手中获取真实的信息。本次seminar她将介绍与 Yiling Chen 和 Fang-Yi Yu 合作的关于peer prediction基础理论的工作。
Make IIIS Great Again!
