报告题目一：马尔可夫链的并行化

报告人：尹一通

报告时间：2026年4月27日 上午8:30

报告地点：行政北楼202会议室

报告简介：马尔可夫链是求解高维采样问题的经典算法框架，在统计推断、高维积分、复杂系统模拟等关键应用中发挥着基础性作用。此类马尔可夫过程具有固有的串行特性——长期以来，针对此类串行过程，如何实现高效并行化始终是悬而未决的关键挑战；而对于复杂系统的模拟、推断与学习，此类计算任务是否具有“本质串行性”，更是关乎人工智能领域并行计算发展前景的关键科学问题。在本报告中，我将介绍我们近期提出的马尔可夫过程并行化新方法：对于单点动态系统（single-site dynamics）马尔可夫链，在满足相关性衰减的渐进 Dobrushin 条件下，构建了马尔可夫链的通用高效并行化算法。这一发现从理论上改变了长久以来人们对于马尔可夫过程难以并行化的认识，相关成果发表于JACM 2025。

报告人简介：南京大学计算机学院教授，研究领域为理论计算机科学，主要研究兴趣包括随机算法、计算采样理论、数据结构、并行与分布式计算理论等，在JACM、SICOMP、STOC、FOCS、SODA等理论计算机科学重要期刊与会议发表论文数十篇。入选新基石研究员，主持国家重点研发计划和自然科学基金优青等项目，获IEEE-CS青年科学家等荣誉，指导博士生获CCF优博以及入选CCF博士学位论文激励计划。目前担任南京大学理论计算机科学团队负责人。

报告题目二：Computation by First-order Logic

报告人：陈翌佳

报告时间：2026年4月27日 上午8:30

报告地点：行政北楼202会议室

报告简介：First-order logic (FO) is central to mathematical logic. However, its role in computer science is limited due to its restricted expressive power. On ordered structures, this limitation corresponds to the computation model known as uniform AC⁰ circuits, which are much weaker than polynomial-time Turing machines — the prevalent model in computer science. Nevertheless, recent research shows that on certain natural structures (e.g., trees of bounded height), FO can in fact capture problems that are NP-hard in general. In this talk, I will explain a few such results. Moreover, I will introduce recent efforts connecting FO with homomorphism counts, which have proven important for diverse applications including graph algorithms, complexity theory, and graph neural networks.

报告人简介：上海交通大学计算机学院教授，主要研究兴趣为计算机与数学的交叉领域，包括逻辑、算法与计算复杂性。目前担任《Logic Methods in Computer Science》和《Theory of Computing Systems》两本国际期刊编委，并多次担任计算机科学逻辑领域的旗舰国际会议LICS的程序委员。曾获微软青年教授奖，理论计算机国际会议ICALP及图论国际会议WG最佳论文奖。

报告题目三：Pricing with a Hidden Sample

报告人：唐志皓

报告时间：2026年4月27日 上午8:30

报告地点：行政北楼202会议室

报告简介：We study prior-independent pricing for selling a single item to a single buyer when the seller observes only a single sample from the valuation distribution, while the buyer knows the distribution. Classical robust pricing approaches either rely on distributional statistics, which typically require many samples to estimate, or directly use revealed samples to determine prices and allocations. We show that these two regimes can be bridged by leveraging the buyer’s informational advantage: pricing policies that conventionally require the seller to know statistics such as the mean, $L^\eta$-norm, or superquantile can, in our framework, be implemented using only a single hidden sample. We introduce hidden pricing mechanisms, in which the seller commits ex ante to a pricing rule based on a single sample that is revealed only after the buyer’s participation decision. We show that every concave pricing policy can be implemented in this way. To evaluate performance guarantees, we develop a general reduction for analyzing monotone pricing policies over $\alpha$-regular distributions, enabling a tractable characterization of worst-case instances. Using this reduction, we characterize the optimal monotone hidden pricing mechanisms and compute their approximation ratios; in particular, we obtain an approximation ratio of approximately $0.79$ for monotone hazard rate (MHR) distributions. We further establish impossibility results for general concave pricing policies and for all prior-independent mechanisms. Finally, we show that our framework also applies to statistic-based robust pricing, thereby unifying sample-based and statistic-based approaches.

报告人简介：上海财经大学计算机与人工智能学院副院长、长聘副教授，研究领域为理论计算机科学与计算经济学，聚焦非完全信息下的算法设计，涵盖在线算法、机制设计等。其成果发表于Journal of the ACM、SIAM Journal on Computing等顶级期刊，并在理论计算机三大会议STOC/FOCS/SODA及计算经济学两大会议EC/WINE发表论文20余篇。现任上海市理论计算机科学专业委员会副主任、中国计算机学会理论计算机科学专业委员会副秘书长。