Algorithms and Logic Group

Category: Seminars

  • 2023 UESTC Algorithms and Logic Workshop

    会议详情见：https://mp.weixin.qq.com/s/r4w5K4WzHxY3ia1_QuBuzA

  • 尹一通：计算采样的理论基础（Theoretical Foundations of Computational Sampling）

    Yitong Yin (Nanjing University) Time: 16:20-17:20 (Time in Beijing) November 30, 2023 (Thursday) Venue: Binnuo Coffee Abstract: 蒙特卡罗法（Monte Carlo methods）是与计算机同一时期诞生的二十世纪最重要的科技产物之一。这一方法利用随机采样来高效计算原本传统确定性方法难以计算的量。它的发现拓展了人类高效计算的边界，深刻地影响了人们对计算本质的理解。在这一计算优越性的帮助下带来的科学新发现也塑造了人们今天对客观世界的认识。 本报告将系统介绍报告人近年来在计算采样理论、以及现代蒙特卡罗算法的设计与分析等方面取得的系统性的重要进展，包括：刻画高位概率分布可高效采样条件的“计算相变”定理；马尔可夫链蒙特卡罗（MCMC）采样的并行与分布式算法和局部与动态算法等。 Speaker Bio: 尹一通，南京大学教授，新基石研究员；本科毕业于南京大学，博士毕业于耶鲁大学；博士毕业后在南京大学工作至今，目前担任南京大学理论计算机科学团队负责人。尹一通的研究领域为理论计算机科学，主要研究兴趣包括：随机算法、计算采样，数据结构、并行与分布式计算理论等。在JACM、SICOMP、STOC、FOCS、SODA等理论计算机科学的重要期刊与会议发表论文五十余篇。主持国家重点研发计划项目“数据科学的若干基础理论”，获国家自然科学基金-优秀青年科学基金支持，曾获CCF/IEEE CS青年科学家、CCF优博导师、中创软件人才奖、教育部新世纪人才、南京大学青年五四奖章等荣誉。

  • Fang Kong: Bandit Learning with Side Information

    () Time: 16:20-17:20 (Time in Beijing) November 29, 2023 (Wednesday) Venue: 518, Research Building 4 Abstract: Speaker Bio: Fang Kong is currently a Ph.D. candidate in the John Hopcroft Center for Computer Science, Shanghai Jiao Tong University. She is also a member in Wu Honor Ph.D. Class in Artificial Intelligence. Fang received her B.S. degree […]

  • Bakhodyr Khoussainov: On Finitely Presented Expansions of Semigroups, Groups, and Algebras

    () Time: 15:00-16:00 (Time in Beijing) November 22, 2023 (Thursday) Venue: Online, Tencent Meeting: 486-877-316 Abstract: Speaker Bio: Bakh Khoussainov，教授，新西兰院士，电子科技大学计算机学院全职教授（我国西部地区引进的第一位发达国家的院士），目前担任电子科技大学算法与逻辑团队主任。他长期从事理论计算机科学中计算与逻辑领域的研究工作，2005年被新西兰最顶尖权威的学术组织——新西兰皇家学会评选为新西兰皇家学会院士，被评价为“在逻辑与理论计算机科学领域的领先专家，工作涉及对可计算性和复杂性理论的深入和非常广泛的研究”。2019年获得德国洪堡研究奖，该奖项旨在授予在基础研究、理论创新、学科引领等方面上取得了卓越成就的研究者。同年他还获得伦敦数学学会与新西兰数学学会联合授予的唯一Aitken Lecturer称号，该荣誉称号每两年仅授予一名最具杰出贡献的新西兰数学家（截至目前仅有包括美国工业与应用数学学会会士（SIAM Fellow）Hinke Osinga教授在内的5位研究者获此殊荣）。2017年他因其对于奇偶博弈问题的突出贡献荣获CCF A类会议ACM STOC 2017年最佳论文奖。他还曾获得新西兰数学学会研究奖，此奖项为新西兰数学领域最高奖，每年仅颁发给一名新西兰数学家，该奖项还曾颁发给包括美国数学学会会士G. Martin, R. Downey教授（AMS Fellow）, M. Conder教授（AMS Fellow）等优秀数学家。

  • 曹皖林: 形式化技术及其应用

    Speaker: 曹皖林（美国德州农工大学） Time: 10:20-11:20 (Time in Beijing) November 17, 2023 (Friday) Venue: 518, Research Building 4 Abstract: 软硬件系统开发包括不断地进行优化和验证，形式化方法在这个过程中被广泛应用。本讲座结合芯片开发过程中的最常见逻辑表达方式和分析手段，介绍形式化技术。具体包括以下内容：– 设计的网表表达– BDD 及其应用– 逻辑的计算与近似– 实例：低功耗优化– 讨论：布尔代数、NP问题、抽象及计算 Speaker Bio: 曹皖林，美国Texas A&M 大学博士，合见工业软件集团 fellow。研究兴趣包括：形式化方法，EDA与FPGA工具开发。

  • Claire Hanen: Fixed Parameter Tractability of scheduling dependent typed tasks with time windows

    Speaker: Claire Hanen (Sorbonne Université – LIP6) Time: 14:00 (UTC) November 15, 2023 (Wednesday) Venue: Online,  Zoom Meeting： Meeting ID: 981 3280 2131 Passcode: 130657 Abstract: This talk discusses the parameterized complexity of scheduling problems, assuming precedence constraints, time windows and typed tasks resource constraints. We recall the usual parameters used for scheduling problems and […]

  • Zile Jiang: Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming

    Speaker: Zhile jiang (Aarhus University) Time: 16:20-17:20 (Time in Beijing) November 10, 2023 (Friday) Venue: 518, Research Building 4 Abstract: Cut games are among the most fundamental strategic games in algorithmic game theory. It is well-known that computing an exact pure Nash equilibrium in these games is PLS-hard, so research has focused on computing approximate […]

  • Ton Kloks: Excluding a long double path minor 

    Speaker: Ton Kloks (National Tsing Hua University ) Time: 10:20-11:20 (Time in Beijing) November 10, 2023 (Friday) Venue: 518, Research Building 4 Abstract: This is a paper from 1994.  (In my opinion this paper is a work of art.)   The paper proves Robertson’s conjecture on well-quasi-orders by topological minors for classes of graphs that are closed […]

  • Ton Kloks: Excluding a long double path minor 

    Speaker: Ton Kloks (National Tsing Hua University ) Time: 10:20-11:20 (Time in Beijing) November 3, 2023 (Friday) Venue: 518, Research Building 4 Abstract: This is a paper from 1994.  (In my opinion this paper is a work of art.)   The paper proves Robertson’s conjecture on well-quasi-orders by topological minors for classes of graphs that are closed […]

  • Huairui Chu: FPT Approximation Using Treewidth

    Speaker: Huairui Chu (Nanjing University ) Time: 16:00-17:00 (Time in Beijing) October 25, 2023 (Wednesday) Venue: 518, Research Building 4 Abstract: Treewidth is a useful tool in designing graph algorithms. Although many NP-hard graph problems can be solved in linear time when the input graphs have small treewidth, there are problems which remain hard on […]