CCF走进高校第1240场

敬请关注

由中国计算机学会（CCF）主办，CCF理论计算机科学专委、广东工业大学承办的CCF走进高校活动，将于2025年4月11日在广东工业大学召开，敬请关注。

会议时间：2025年4月11日15：00—17：45

会议地点：广东工业大学计算机学院工学一号馆2楼学术报告厅

报告题目：Theoretical Foundations of Computational Sampling

报告摘要：理论计算机科学的一个宗旨，是系统地解释与刻画计算问题因何而易、又因何而难，从而理解计算的本质与界限。如何依特定概率分布生成随机样本，即采样问题，是一类经典的计算问题。早在计算机诞生之初，冯·诺依曼等人便提出了蒙特卡罗法，通过随机采样高效估算难以确定的物理量。随着计算机科学步入数据与智能科学的新时代，从高维概率分布中高效采样已成为这一时代的基石性计算需求，在各类智能化计算任务中发挥着至关重要的作用。从高维吉布斯分布中采样，由于其计算复杂性展现出类似物理相变的临界现象，因而受到理论计算机科学领域的关注。本报告将探讨吉布斯分布采样的“计算相变”（computational phase transition）现象，以及约束满足解采样的“局部引理”（local lemma）——这两者分别刻画了成对（pairwise）与高阶（high-order）相互作用变量采样的计算临界现象。

嘉宾简介：

尹一通，南京大学计算机学院教授，新基石研究员，南京大学理论计算机科学团队负责人。尹一通本科和博士先后毕业于南京大学和耶鲁大学，主要研究领域为理论计算机科学，尤其是算法与计算复杂性理论，在JACM、SICOMP、STOC、FOCS、SODA等理论计算机科学重要期刊与会议发表论文数十篇。主持国家重点研发计划项目、国家自然科学基金优青项目等，获CCF/IEEE CS青年科学家、CCF优博导师等荣誉，目前担任CCF理论计算机科学专委副主任。

报告题目：Half-integral Solutions of Linear Systems

报告摘要：我们以几个经典的组合优化问题为例，来说明线性规划半整解的存在性和应用。

嘉宾简介：

操宜新，香港理工大学计算学系的副教授，2012年博士毕业于德州农机大学。在2014年回国之前，他在匈牙利科学院做了两年的研究员。他的研究兴趣包括算法图论，细粒度复杂性和算法设计，组合优化。他的研究得到了香港研究资助委员会（RGC）和国家自然科学基金（NSFC）的支持。目前主要学术兼职包括中国计算机学会理论计算机科学专业委员会常务委员和中国运筹学会数学规划分会理事和图论组合分会理事。

报告题目：Dimension Reduction beyond Classic Johnson-Lindenstrauss Bound

报告摘要：经典的Johnson-Linndenstrauss (JL)降维可以将一般的n个欧氏空间中的点映射到O(log n/ eps^2)维并使得任意两点之间的距离保持在原来的(1 + eps)倍，且该维数被证明是紧的。然而，即使降维到log n维，很多计算问题仍无法显著逃避高维带来的复杂性。近期，有一系列研究针对具体的计算问题绕过了该降维下界，并利用降维技术得到了新的算法结果。我们计划介绍这方面的进展，并介绍两个高度相关的、放宽的降维设定及其结果：1. 中等降维，旨在考虑常数近似而不是1 + eps近似下的维数权衡；2. 考虑高维数据的内蕴维度，并降维至内蕴维度（的某个函数）。我们将在报告最后提出若干公开问题。

嘉宾简介：

姜少峰，现任北京大学前沿计算研究中心助理教授、北京大学博雅青年学者。他曾在芬兰阿尔托大学担任助理教授、以色列魏茨曼科学院任博士后研究员。他的研究方向主要为理论计算机科学，侧重大数据算法、近似算法和在线算法。

CCF微信公众号，欢迎关注