本周六上午 10:00 - 12:00，我们将在学堂 112【线下】给大家带来金策学长和林纯凯教授的报告。两位同学的报告分别与近似算法和博弈论相关。在两场报告之间，同学们可以吃零食 and/or 自由交流。
报告 1 摘要
金策是姚班 2016 级（计科 60）学长。本次 seminar 他将介绍他与合作者凤维明合作的工作“Approximately counting knapsack solutions in subquadratic time”。#Knapsack 是一个很基本的问题：给定 n 个物品的体积和一个容积 T，计数有多少种选择物品的方案使得总体积不超过 T。由于这个问题是 #P 完全的，人们一般关心它的近似算法（输出在真实结果的 1±ϵ 倍即可）。Dyer 在 2003 年提出了一个 Õ(n^2.5 + n^2ϵ^-2) 的算法。本次 talk 中将会介绍如何利用近年算法领域的进展，将这一思路改进到 Õ(n^1.5ϵ^-2)。该论文发表于 SODA2025。论文链接：https://arxiv.org/abs/2410.22267
报告 2 摘要
林纯凯（Chun Kai Ling）是新加坡国立大学计算机科学系的助理教授。博弈论已成为多智能体决策的主要工具之一，其应用范围从休闲游戏中超过人类的表现（如扑克、星际争霸、战术棋、外交）到安保巡逻的最优调度。与单智能体相比，多智能体环境更加丰富，智能体表现出诸如欺骗、胁迫和串通等策略行为。在本次报告中，他将首先介绍双人零和博弈中的纳什均衡等基本博弈论概念。随后，他将简要概述一些有趣的应用，包括他最近在最优巡逻和争夺物流方面的工作。最后，他将分享他最近在多防御者安全博弈和联盟结构学习方面的工作，这些论文都由他和指导的姚班本科生合作完成。
欢迎全体同学参加~
Make IIIS Great Again!
