学　术

成电讲坛 “ 信息·科学 ” 系列讲座

主 题：参数化不可近似性假设

主 讲：文卡塔桑·古鲁斯瓦米 Venkatesan Guruswami（加州大学伯克利分校计算机科学系[EECS]与数学系教授，ACM、IEEE、AMS会士）

时 间：2月26日（周三）16:30-17:30

地 点：清水河校区 学生发展中心201报告厅

主 办：大学生文化素质教育中心

承 办：计算机科学与工程学院（网络空间安全学院） 

讲座简介：

　　参数不可近似性猜想（Parameterized Inapproximability Hypothesis, PIH）是计算机科学领域的一个非常重要的难题。针对约束满足问题（CSP），参数化不可近似性猜想（PIH）断言，不存在一种FPT算法，能够区分可满足实例与无法满足1%约束的实例。PIH在参数化复杂性理论中扮演着类似于PCP定理的角色，并衍生出许多不可近似性结果。本次报告将首先介绍PIH的背景和描述，然后概述最近提出的指数时间假设（Exponential Time Hypothesis, ETH）证明的核心思想。这一证明方法主要包含两大步骤。第一步是识别出一种具有高度结构化的、ETH难解的CSP，其变量取向量值，且约束条件要么是平行的，要么是线性的。随后，基于Hadamard码的“并行近似PCP”（parallel PCP of proximity）以常数可靠性对这两种约束进行验证。我们还将简要提及后续的改进工作，这些改进利用基于Reed-Muller码的PCP，可以得到接近最紧的运行时间下界。例如，利用这些改进可以证明，在ETH假设下，求解n个顶点的k-clique问题的常数因子近似算法，需要至少n^{k^{1-o(1)}}的时间。

主讲人简介：

文卡塔桑·古鲁斯瓦米（Venkatesan Guruswami），现任加州大学伯克利分校计算机科学系 (EECS) 与数学系教授，同时担任西蒙斯计算理论研究所高级科学家。文卡特教授本科毕业于印度理工学院马德拉斯分校，随后在麻省理工学院获得博士学位。他的研究领域涵盖编码理论、约束满足、近似优化和计算复杂性等多个方向，目前担任《Journal of the ACM》期刊主编，并曾担任计算复杂性基金会主席。他的学术成就斐然，先后荣获普雷斯伯格奖、西蒙斯研究奖、古根海姆奖、帕卡德奖和斯隆奖等多项殊荣，同时获得ACM优秀博士论文奖和印度理工学院马德拉斯分校杰出校友称号。他是美国计算机协会（ACM）、国际电子电气工程师学会（IEEE）和美国数学学会（AMS）三大国际权威学术机构的会士。

参与方式：

学院领票

注意事项：

1. 现场签到时，需在扫码后点击“签到”选项，待显示“签到成功”才视为完成一次签到。

2. 讲座后，出勤数据将于1—2个工作日内在飞书【应用-成电讲坛】更新。如有任何疑问，欢迎在【飞书-消息，搜索“成电讲坛服务台”】进行留言。

3. 请最晚于讲座开始前五分钟进入现场。