成电讲堂

2月26日，美国加州大学伯克利分校计算机科学系（EECS）与数学系教授文卡塔桑·古鲁斯瓦米（Venkatesan Guruswami）做客成电讲坛，作了题为“参数化不可近似性假设”的讲座，并与同学们进行了探讨交流。

讲座伊始，他详细阐述了参数化不可近似性猜想（Parameterized Inapproximability Hypothesis, PIH）的背景和核心内涵，认为PIH是针对约束满足问题（CSP）提出的一个重要假设，不存在一种固定参数可解（FPT）算法，能够区分可满足实例与无法满足一定比例约束的实例。这一假设的提出，为参数化复杂性理论的研究提供了新的视角和挑战。

接着，他概述了指数时间假设（Exponential Time Hypothesis, ETH）证明的核心思想，并详细解析了证明方法的两大步骤。他首先识别出一种具有高度结构化、ETH难解的CSP，并基于Hadamard码构建了“并行近似PCP”（parallel PCP of proximity）验证方法，以常数可靠性对上述两种约束进行验证。他还简要提及了后续的改进工作，这些改进利用基于Reed-Muller码的PCP，得到了接近最紧的运行时间下界，进一步验证了ETH的正确性。

随后，他深入介绍了理论计算机科学中的具体问题及相关主题，包括装箱问题、多项式优化、纠错码以及P vs. NP问题等。他以装箱问题为例，详细讲解了如何将物品装入容量为一的箱子中，并使用的箱子数量最少，这是一个NP完全问题，其开放性问题是能否使用一个额外的箱子来解决它。在多项式优化方面，他介绍了在单位球面上寻找多项式的最大值的问题，并指出对于三次多项式，目前已知的最佳算法只能找到一个与最优值相差一定因子的值。在纠错码方面，他从简单的奇偶校验码开始，逐步发展到更复杂的情况，如处理比特删除和翻转，并探讨了如何改进处理两次删除的编码的开放性问题。最后，他讨论了P vs. NP问题，即易于验证的问题（NP）与易于解决的问题（P）之间的关系，并探讨了这一问题对于优化或自动化创造力的潜在影响。

最后，他探讨了人工智能与理论计算机科学和数学的关系，认为随着人工智能技术的不断发展，其对于理论计算机科学和数学的影响日益显著，希望同学们深入思考如何用人工智能推动理论计算机科学和数学实现更好的发展。