约束满足问题（constraint satisfaction problem, CSP）是计算机科学关注的一类基本的计算问题。例如经典的可满足性判定（SAT）问题——这一人类已知的首个NP完全问题，即是约束满足问题的一个特例。约束满足解空间的几何性质，关系到与约束满足问题相关的诸多计算问题的计算复杂性。在本次讲座中，我们将介绍：作为约束满足问题解的存在性的充分条件“Lovasz局部引理”、约束满足解空间的连通性、以及对约束满足解的快速采样算法之间的联系。

约束满足问题（constraint satisfaction problem, CSP）是计算机科学关注的一类基本的计算问题。例如经典的可满足性判定（SAT）问题——这一人类已知的首个NP完全问题，即是约束满足问题的一个特例。约束满足解空间的几何性质，关系到与约束满足问题相关的诸多计算问题的计算复杂性。在本次讲座中，我们将介绍：作为约束满足问题解的存在性的充分条件“Lovasz局部引理”、约束满足解空间的连通性、以及对约束满足解的快速采样算法之间的联系。

Given an arbitrary graph G, can you find a sparse graph that approximates G in some sense? We will survey a beautiful line of work, starting with the celebrated notion of cut-approximator in the works of Karger and Benczur-Karger. Intuitively, one tries to approximate the "connectedness" of a given graph. As a special case, if one tries to approximate a complete graph with a d-regular graph for a constant d, such sparsifiers are known as the expander graphs, and it has found applications in networking, coding theory, analysis of algorithms and many more . Besides expanders, we will also discuss a powerful generalization of cut-approximator known as spectral approximations. It turns out that one can find spectral approximations for every weighted graph very efficiently, and this has been a useful and versatile (algorithmic) primitive for many problems in graph theory and beyond.

Given an arbitrary graph G, can you find a sparse graph that approximates G in some sense? We will survey a beautiful line of work, starting with the celebrated notion of cut-approximator in the works of Karger and Benczur-Karger. Intuitively, one tries to approximate the "connectedness" of a given graph. As a special case, if one tries to approximate a complete graph with a d-regular graph for a constant d, such sparsifiers are known as the expander graphs, and it has found applications in networking, coding theory, analysis of algorithms and many more . Besides expanders, we will also discuss a powerful generalization of cut-approximator known as spectral approximations. It turns out that one can find spectral approximations for every weighted graph very efficiently, and this has been a useful and versatile (algorithmic) primitive for many problems in graph theory and beyond.

Richard Peng (彭泱) is an associate professor in the Cheriton School of Computer Science at the University of Waterloo. He is known for fast algorithms for solving graph structured linear systems, and his current research revolves around the design, analysis, and implementation of efficient algorithms. Richard was a recipient of the 2011 Microsoft PhD Fellowship, an NSF CAREER Award, and the 2021 ACM-SIAM Symposium on Discrete Algorithms Best Paper Award.

Richard Peng (彭泱) is an associate professor in the Cheriton School of Computer Science at the University of Waterloo. He is known for fast algorithms for solving graph structured linear systems, and his current research revolves around the design, analysis, and implementation of efficient algorithms. Richard was a recipient of the 2011 Microsoft PhD Fellowship, an NSF CAREER Award, and the 2021 ACM-SIAM Symposium on Discrete Algorithms Best Paper Award.

Partial rejection sampling (PRS) is an algorithm which bridges approximate counting/sampling and Lovasz local lemma. We will explain how PRS works, show its correctness, and discuss a formula for its expected running time in some special but very useful cases. With this technique, we will give a fully polynomial-time randomised approximation algorithm for all-terminal network reliability. Time permitting, we will cover a few other related applications as well.

基于时间距离与拓扑距离的连通性模型