2019-12-30 | Kuan Yang: Fundamental Graph Algorithms for Distributed Networks

2019-12-30   

Abstract

We give the first efficient algorithm to approximately count the number of solutions in the random k-SAT model when the density of the formula scales exponentially with k. The best previous counting algorithm was due to Montanari and Shah and was based on the correlation decay method, which works up to densities (1+o_k(1))2logk/k, the Gibbs uniqueness threshold for the model. Instead, our algorithm harnesses a recent technique by Moitra to work for random formulas. The main challenge in our setting is to account for the presence of high-degree variables whose marginal distributions are hard to control and which cause significant correlations within the formula.

 

Time

12月30日  14:00-15:00

 

Speaker

Kuan Yang is a fourth-year Ph.D. candidate in the Department of Computer Science at University of Oxford, supervised by Prof. Leslie Ann Goldberg and Prof. Andreas Galanis. Before coming to Oxford, he obtained the bachelor degree in Computer Science from Zhiyuan College at Shanghai Jiao Tong University.

He is interested in many aspects of theoretical computer science, discrete probability and combinatorics. Currently he mainly works on designing and analysing approximate counting and sampling algorithms.

 

Venue

信息管理与工程学院602

上海财经大学(第三教学楼)

上海市杨浦区武东路100号