Theory@Nanjing 2017

• Friday, May 26, 2017.

• Location: 南京大学 计算机科学与技术系 （南京大学仙林校区常州楼）Room 230 在线地图

Workshop Program
9:00 am -- 9:50 am	Shiteng Chen (陈世腾) 中科院软件所	Title: Circuits with composite moduli Abstract: TBA
10:00 am -- 10:50 am	Jane Gao (高普) Monash University	Title: Uniform generation of random regular graphs Abstract: We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler REG for [math]\displaystyle{ d }[/math]-regular graphs. REG can be implemented such that each graph is generated in expected time [math]\displaystyle{ O(nd^3) }[/math], provided that [math]\displaystyle{ d=o(n^{1/2}) }[/math]. Our result significantly improves the previously best uniform sampler, which works efficiently only when [math]\displaystyle{ d=O(n^{1/3}) }[/math], with essentially the same running time for the same [math]\displaystyle{ d }[/math]. We also give a linear-time approximate sampler REG*, which generates a random [math]\displaystyle{ d }[/math]-regular graph whose distribution differs from the uniform by [math]\displaystyle{ o(1) }[/math] in total variation distance, when [math]\displaystyle{ d=o(n^{1/2}) }[/math]. If time permits, I will describe how to use this new method to generate uniformly random graphs with power-law (with exponent below 3) degree sequences.
11:00 am -- 11:50 am	Heng Guo (郭珩) University of London	Title: Uniform Sampling through the Lovász Local Lemma Abstract: We propose a new algorithmic framework, called "partial rejection sampling", to draw samples exactly from a product distribution, conditioned on none of a number of bad events occurring. Our framework builds (perhaps surprising) new connections between the variable framework of the Lovász Local Lemma and some classical sampling algorithms such as the "cycle-popping" algorithm for uniform spanning trees by Wilson. Among other applications, we discover new algorithms to sample satisfying assignments of [math]\displaystyle{ k }[/math]-CNF formulas with bounded variable occurrences. Based on joint work with Mark Jerrum and Jingcheng Liu.
Lunch Break
2:00 pm -- 2:50 pm	Pan Peng (彭攀) University of Vienna	Title: Estimating Graph Parameters from Random Order Streams Abstract: We develop a new algorithmic technique that allows to transfer some constant time approximation algorithms for general graphs into random order streaming algorithms. We illustrate our technique by showing that in random order streams, one can approximate the number of connected components of the input graph [math]\displaystyle{ G }[/math] with an additive error of [math]\displaystyle{ \epsilon }[/math][math]\displaystyle{ n }[/math]; [math]\displaystyle{ (1+\epsilon) }[/math]-approximate the weight of the minimum spanning tree of an input graph with bounded maximum edge weight; and [math]\displaystyle{ (1+\epsilon) }[/math]-approximate the size of a maximum independent set in planar graphs, with constant space complexity that only depends on [math]\displaystyle{ \epsilon }[/math] and is independent of the size of the input graph. Based on joint work with Christian Sohler.
3:00 pm -- 3:50 pm	Richard Peng (彭泱) Georgia Tech	Title: Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees Abstract: We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs. By Kirchhoff's matrix-tree theorem, this quantity is the determinant of a graph Laplacian minor, or equivalently, of any SDDM matrix. Our analyses utilize this combinatorial connection to bridge between statistical leverage scores / effective resistances and the analysis of random graphs by [Janson, Combinatorics, Probability and Computing `94]. This leads to a routine that in quadratic time, sparsifies a graph down to about n} edges in ways that preserve both the determinant and the distribution of spanning trees (provided the sparsified graph is viewed as a random object). Extending this algorithm to work with Schur complements and approximate Cholesky factorizations leads to algorithms for counting and sampling spanning trees which are nearly optimal for dense graphs. Work joint with David Durfee, John Peebles, and Anup B. Rao, manuscript available at https://arxiv.org/abs/1705.00985.
4:00 pm -- 4:50 pm	Chihao Zhang (张驰豪) CUHK	Title: FPTAS for Counting Proper Colorings on Cubic Graphs Abstract: Graph coloring is arguably the most exhaustively studied problem in the area of approximate counting. It is conjectured that there is a fully polynomial-time (randomized) approximation scheme (FPTAS/FPRAS) for counting the number of proper colorings as long as [math]\displaystyle{ q\ge \Delta+1 }[/math], where [math]\displaystyle{ q }[/math] is the number of colors and [math]\displaystyle{ \Delta }[/math] is the maximum degree of the graph. The bound of [math]\displaystyle{ q=\Delta+1 }[/math] is the uniqueness threshold for Gibbs measure on [math]\displaystyle{ \Delta }[/math]-regular infinite trees. However, the conjecture remained open even for any fixed [math]\displaystyle{ \Delta\ge 3 }[/math] (The cases of [math]\displaystyle{ \Delta=1, 2 }[/math] are trivial). In this paper, we design an FPTAS for counting the number of proper 4-colorings on graphs with maximum degree 3 and thus confirm the conjecture in the case of [math]\displaystyle{ \Delta=3 }[/math]. This is the first time to achieve this optimal bound of [math]\displaystyle{ q=\Delta+1 }[/math]. Previously, the best FPRAS requires [math]\displaystyle{ q\gt \frac{11}{6}\Delta }[/math] and the best deterministic FPTAS requires [math]\displaystyle{ q\gt 2.581\Delta+1 }[/math] for general graphs. In the case of [math]\displaystyle{ \Delta=3 }[/math], the best previous result is an FPRAS for counting proper 5-colorings. We note that there is a barrier to go beyond [math]\displaystyle{ q=\Delta+2 }[/math] for single-site Glauber dynamics based FPRAS and we overcome this by correlation decay approach. Moreover, we develop a number of new techniques for the correlation decay approach which can find applications in other approximate counting problems.