邀请报告摘要
报告题目：Recent progress on random graph matching problems
报告人：丁剑（北京大学）
摘要: A basic goal for random graph matching is to recover the vertex correspondence between two correlated graphs from an observation of these two unlabeled graphs. Random graph matching is an important and active topic in combinatorial statistics: on the one hand, it arises from various applied fields such as social network analysis, computer vision, computational biology and natural language processing; on the other hand, there is also a deep and rich theory that is of interest to researchers in statistics, probability, combinatorics, optimization, algorithms and complexity theory.
Recently, extensive efforts have been devoted to the study for matching two correlated Erdős–Rényi graphs, which is arguably the most classic model for graph matching. In this talk, we will review some recent progress on this front, with emphasis on the intriguing phenomenon on (the presumed) information-computation gap. In particular, we will discuss progress on efficient algorithms thanks to the collective efforts from the community. We will also point out some important future directions, including developing robust algorithms that rely on minimal assumptions on graph models and developing efficient algorithms for more realistic random graph models.
This is based on joint works with Hang Du, Shuyang Gong, Zhangsong Li, Zongming Ma, Yihong Wu and Jiaming Xu.
报告题目：Algebra, combinatorics and cryptography
报告人：王华雄（新加坡南洋理工大学）
摘要: Algebra and combinatorics play crucial roles in the field of cryptography. Algebraic structures, such as groups, rings, and fields, form the foundation of many cryptographic algorithms. For example, the RSA encryption algorithm relies on properties of prime numbers and modular arithmetic, both of which are rooted in algebra. Elliptic curve cryptography (ECC) is another application that uses the algebraic structure of elliptic curves over finite fields to create efficient and secure cryptographic schemes. Combinatorics, the study of counting, arrangement, and combination, is essential for analyzing and designing cryptographic protocols. It helps in understanding the complexity and security of these protocols. For instance, combinatorial designs and permutations are used in the construction of block ciphers like the Data Encryption Standard (DES) and Advanced Encryption Standard (AES). The synergy of algebra and combinatorics provides robust tools for developing and analyzing cryptographic systems.
In this talk, I will present several concrete examples to illustrate how the interplay between algebra and combinatorics enriches cryptography in the constructions of cryptographic schemes such as secret sharing and secure multiparty computation.
报告题目：零误差计算
报告人：冯勇（中国科学院重庆绿色智能技术研究院）
摘要: 符号计算获得准确值,一些领域如自动推理需要准确值, 人们就采用符号计算来获得.由于符号计算存在中间结果膨胀等问题使得其计算的效率不高,解决问题的规模不大等劣势,已成为制约这一领域发展的瓶颈.数值计算有计算效率高、解决问题规模大的优势, 然而数值计算获得的是近似值,近似计算的结果与准确值之间有一个间隙.研究采用有误差的数值计算来获得无误差的准确结果就具有重要的理论价值和应用价值.采用数值计算获得准确值又称为零误差计算.本报告首先回答哪类数可以开展零误差计算:可以归结为一致离散集合中的数可以开展零误差计算,即有非零隔离界的数集.这是“数”可以零误差计算的一个充要条件.以此为基本出发点,分析了代数数零误差计算的最低理论.该理论就是近似代数数恢复其准确值的必要的误差控制,但是这一理论因算法条件的限制,往往不能保证成功恢复出代数数的准确值.因此,本报告将给出采用PSLQ算法进行代数数零误差计算所需的误差控制,与基于LLL的算法相比,关于代数数次数的依赖程度由二次降低为拟线性.最后,本报告也将探讨零误差计算未来的研究趋势.
报告题目：Fast Fourier Transform via automorphism groups of rational function fields
报告人：邢朝平（上海交通大学）
摘要: The Fast Fourier Transform (FFT) over a finite field $\mathbb{F}_q$ computes evaluations of a given polynomial of degree less than $n$ at a specifically chosen set of $n$ distinct evaluation points in $\mathbb{F}_q$. If $q$ or $q-1$ is a smooth number, then the divide-and-conquer approach leads to the fastest known FFT algorithms. Depending on the type of group that the set of evaluation points forms, these algorithms are classified as multiplicative (Math of Comp. 1965) and additive (FOCS 2014) FFT algorithms. In this talk, we provide a unified framework for FFT algorithms that include both multiplicative and additive FFT algorithms as special cases, and beyond: our framework also works when $q+1$ is smooth, while all known results require $q$ or $q-1$ to be smooth. For this new smooth $q+1$ case, we show that if $n$ is a divisor of $q+1$ that is $B$-smooth for a real $B>0$, then our FFT needs $O(B\cdot n\cdot\log n)$ arithmetic operations in $\mathbb{F}_q$. Our unified framework is a natural consequence of introducing the algebraic function fields into the study of FFT.
报告题目：Symbolic approach to combinatorial relations
报告人：杨立波（南开大学）
摘要: In recent years symbolic computation algorithms have been proven to be powerful tools for solving longstanding open problems in combinatorics, such as George Andrews' and David Robbins' $q$-TSPP-conjecture and Ira Gessel's lattice path conjecture. In this talk, I will present some combinatorial relations via symbolic approach, including some identities in enumerative combinatorics, some congruences in combinatorial number theory, and some inequalities in analytic combinatorics.
报告题目：四色问题与子图覆盖
报告人：范更华（福州大学）
摘要: 1976年，数学史上有着重要影响的四色问题在计算机的帮助下被解决了，这是数学发展史上的一个标志性事件，开启了使用计算机解决数学问题的时代。数学家寻求四色定理的纯推理证明仍在继续。我们将简要介绍与四色问题相关的若干图论著名问题，如哈密顿圈问题、整数流理论、子图覆盖等，同时简述图论在芯片设计EDA软件中的某些应用。
报告题目：Recent progress on graph chromatic thresholds and graph homomorphism thresholds
报告人：上官冲（山东大学）
摘要: In this talk I will give a brief introduction to graph chromatic thresholds and graph homomorphism thresholds, and survey some recent progress. In particular, I will discuss how they are related to discrete geometry and the theory of VC dimensions.
报告题目：无量词非线性公式可满足性问题的求解方法
报告人：李昊坤（华为2012可信费马实验室）
摘要: 非线性公式的可满足性问题不仅是理论研究的热点，也是程序验证中的一个核心问题。本报告专注于介绍无量词非线性公式的求解方法，包括利用多项式的弦结构优化圆柱代数分解（CAD）的投影序列，通过单胞腔投影操作符更有效地与冲突驱动的子句学习（CDCL）策略结合，以及使用局部搜索算法快速寻找解。报告最后还将介绍求解超越方程和混合三角多项式的方法。
报告题目：结构化网格生成中的关键问题及其计算共形几何解决方案
报告人：郑晓朋（大连理工大学）
摘要: 网格生成对于高速、高精度仿真非常重要，是CAD\CAE一体化的瓶颈问题之一。结构化网格具有存储资源省、计算精度高、收敛速度快等优点，但其自动化生成一直是个巨大的挑战。本报告针对结构化四边形网格和六面体网格，分别分析其自动化生成的关键难题，给出基于计算共形几何的相关理论、算法和解决方案。
结构化四边形网格生成的奇异点分布合法性和合理性是其自动化高质量生成的关键。本报告介绍奇异点分布的Abel-Jacobi理论，该理论首次从根本上解决了奇异点合法性问题；本报告进一步介绍融合了Ricci Flow参数化、叶状结构和最优传输密度控制的结构化四边形网格自动化生成算法流程。
结构化六面体网格生成是网格生成领域的“圣杯”问题。表面四边形网格约束下的六面体网格生成是一类具有巨大工程应用价值的方法，其六面体网格存在性已被菲尔兹奖得主Thurston等数学家证明，但其普适算法仍是开放问题。本报告基于四边形和六面体网格拓扑变换给出一套自动化算法，该算法在施耐德金字塔等表面约束耦合复杂的上百个模型上测试成功。
报告题目：Symmetric structures in the Bruhat order
报告人：高奕博（北京国际数学研究中心）
摘要: The Bruhat order encodes algebraic and topological information of Schubert varieties in the flag manifold and possesses rich combinatorial properties. In this talk, we discuss some interrelated stories regarding the Bruhat order: self-dual Bruhat intervals, minimal exponents in the Kazhdan-Lusztig polynomials, Billey-Postnikov decompositions and automorphisms of the Bruhat graph. This is joint work with Christian Gaetz.
报告题目：Quantifying low rank approximations of third order symmetric tensors
报告人：胡胜龙（杭州电子科技大学）
摘要: In this talk, we present a method to certify the approximation quality of a low rank tensor to a given third order symmetric tensor. Under mild assumptions, best low rank approximation is attained if a control parameter is zero or quantified quasi-optimal low rank approximation is obtained if the control parameter is positive. This is based on a primal-dual method for computing a low rank approximation for a given tensor. The certification is derived from the global optimality of the primal and dual problems, and is characterized by easily checkable relations between the primal and the dual solutions together with another rank condition. The theory is verified theoretically for orthogonally decomposable tensors as well as numerically through examples in the general case.
报告题目：Linear codes from Boolean functions with high (fast) algebraic immunity
报告人：唐春明（西南交通大学）
摘要: In the talk, we propose a new parameter to measure the resistance of a Boolean function to fast algebraic attack. We also introduce the notion of fast immunity profile and show that it informs both on the resistance to standard and fast algebraic attacks. Further, a coding-theory approach to the characterization of perfect algebraic immune functions is presented. Via this characterization, infinite families of binary linear complementary dual codes (or LCD codes for short) are obtained from perfect algebraic immune functions. Moreover, two methodologies for constructing minimal binary codes from sets, Boolean functions and vectorial Boolean functions with high algebraic immunity, are proposed. More precisely, a general construction of new minimal codes using minimal codes contained in Reed-Muller codes and sets without nonzero low degree annihilators is presented. The other construction allows us to yield minimal codes from certain subcodes of Reed-Muller codes and vectorial Boolean functions with high algebraic immunity.
报告题目：Quantum advantage for near-term and fault-tolerant quantum computers
报告人：袁骁（北京大学前沿计算研究中心）
摘要: Quantum computer have the potential to solve classically intractable problems. However, realizing a universal quantum computer is challenging with current technology. Before having a fully-fledged quantum computer, a more realistic question is what we can do with current and near-term quantum hardware. In this talk, I will first review the quantum algorithms that are designed for near-term and fault-tolerant quantum computers and discuss the challenges and possibilities to realize quantum advantages. Then, I will propose to focus more on the early-fault tolerant era and discuss what we should do next to achieve quantum advantage.
报告题目：控制系统可达性分析
报告人：薛白（中国科学院软件所）
摘要: 控制系统广泛存在于航空航天、智能驾驶、智能生产与制造等安全攸关领域，这些系统的失效将带来灾难性后果。因此，确保安全攸关控制系统可靠工作是计算机科学、控制理论及应用数学的重要挑战。基于微分方程等数学模型计算系统可达集的可达性分析是确保这些安全攸关控制系统可靠工作的重要方法之一。此报告主要跟大家分享我们在控制系统可达性分析方面的工作。