# Department Seminars & Colloquia

2022-07
Sun Mon Tue Wed Thu Fri Sat
1 2
3 4 1 5 6 7 8 9
10 11 12 13 14 15 16
17 18 1 19 1 20 21 22 23
24 25 26 27 28 29 30
31
2022-08
Sun Mon Tue Wed Thu Fri Sat
1 1 2 3 4 5 6
7 8 1 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31

You can get notification if you subscribe the calendar in Google Calendar or iPhone calendar etc.

This talk will highlight recent results establishing a beautiful computational phase transition for approximate counting/sampling in (binary) undirected graphical models (such as the Ising model or on weighted independent sets). The computational problem is to sample from the equilibrium distribution of the model or equivalently approximate the corresponding normalizing factor known as the partition function. We show that when correlations die off on the infinite D-regular tree then the Gibbs sampler has optimal mixing time of O(n log n) on any graph of maximum degree D, whereas when the correlations persist (in the limit) then the sampling/counting problem are NP-hard to approximate. The Gibbs sampler is a simple Markov Chain Monte Carlo (MCMC) algorithm. Key to these mixing results are a new technique known as spectral independence which considers the pairwise influence of vertices. We show that spectral independence implies an optimal convergence rate for a variety of MCMC algorithms.
Host: Sang-il Oum     English     2022-06-20 14:20:56
Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its “expectation-threshold,” which is a natural (and often easy to calculate) lower bound on the threshold. In the first talk on Monday, I will introduce the Kahn-Kalai Conjecture with some motivating examples and then briefly talk about the recent resolution of the Kahn-Kalai Conjecture due to Huy Pham and myself. In the second talk on Tuesday, I will discuss our proof of the conjecture in detail.
Host: Sang-il Oum     English     2022-06-22 06:13:29
Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its “expectation-threshold,” which is a natural (and often easy to calculate) lower bound on the threshold. In the first talk on Monday, I will introduce the Kahn-Kalai Conjecture with some motivating examples and then briefly talk about the recent resolution of the Kahn-Kalai Conjecture due to Huy Pham and myself. In the second talk on Tuesday, I will discuss our proof of the conjecture in detail.
Host: Sang-il Oum     English     2022-06-22 06:14:40
We call an order type inscribable if it is realized by a point configuration where all extreme points are all on a circle. In this talk, we investigate inscribability of order types. We first show that every simple order type with at most 2 interior points is inscribable, and that the number of such order types is $\Theta(\frac{4^n}{n^{3/2}})$. We further construct an infinite family of minimally uninscribable order types. The proof of uninscribability mainly uses Möbius transformations. We also suggest open problems around inscribability. This is a joint work with Michael Gene Dobbins.
Host: Sang-il Oum     English     2022-06-22 06:16:23
We show a flow-augmentation algorithm in directed graphs: There exists a polynomial-time algorithm that, given a directed graph G, two integers $s,t\in V(G)$, and an integer $k$, adds (randomly) to $G$ a number of arcs such that for every minimal st-cut $Z$ in $G$ of size at most $k$, with probability $2^{−\operatorname{poly}(k)}$ the set $Z$ becomes a minimum $st$-cut in the resulting graph. The directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set, whose parameterized complexity status was repeatedly posed as open problems: (1) Chain SAT, defined by Chitnis, Egri, and Marx [ESA'13, Algorithmica'17], (2) a number of weighted variants of classic directed cut problems, such as Weighted st-Cut, Weighted Directed Feedback Vertex Set, or Weighted Almost 2-SAT. By proving that Chain SAT is FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph H, if the List H-Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable. Joint work with Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström.
Host: Sang-il Oum     English     2022-06-20 14:22:21