Abstracts

Counting Complexity and Phase Transitions Reunion

Monday, June 5th, 2017

The Interpolation Method
1:30 pm – 2:30 pm
Speaker: Alexander Barvinok, University of Michigan

I'll describe a general way to efficiently approximate the partition function in a complex domain, provided it has no zeros in a slightly larger domain. Examples include (multi-dimensional) permanents counting (hypergraph) perfect matchings and hafnians counting perfect matchings in general (non-bipartite) graphs, graph homomorphism partition function and its refinements, (hypergraph) matching polynomial, etc. Although typically the method results in quasi-polynomial algorithms, Patel and Regts have shown that the algorithms can be made genuinely polynomial time on bounded degree graphs. In most cases, the interpolation approach matches or appears to outperform the correlation decay method, although until recently the interpolation approach was lagging behind the correlation decay method in the notable case of the independence polynomial of a graph. The recent proof by Peters and Regts of the Sokal conjecture implies that both approaches produce the same approximation (Weitz' bound) for the independence polynomial.

PDF icon The Interpolation Method
The Ising Partition Function: Zeros and Deterministic Approximation
2:30 pm – 3:00 pm
Speaker: Jingcheng Liu, UC Berkeley

We study the problem of approximating the partition function of the ferromagnetic Ising model on graphs and hypergraphs. Unlike most other deterministic approximation algorithms for problems in statistical physics and counting, our algorithm does not rely on the ``decay of correlations'' property. Rather, we exploit and extend machinery developed recently by Barvinok, and Patel and Regts, based on the location of the complex zeros of the partition function, which can be seen as an algorithmic realization of the classical Lee-Yang approach to phase transitions.

We first show that in combination with the Lee-Yang theorem, the Patel and Regts framework can be used to give the first polynomial time _deterministic_ approximation algorithm (an FPTAS) for the ferromagnetic Ising model partition function in bounded degree graphs that is valid over the entire range of parameters β (the interaction) and λ (the external field), except for the case |λ|=1 (the ``zero-field'' case). A _randomized_ algorithm (FPRAS) for all graphs, and all β,λ has long been known. Our extension of the Patel and Regts approach, however, extends also to the more general setting of the Ising model on hypergraphs of bounded degree and edge size, where no previous algorithms (even randomized) were known for a wide range of parameters (especially in the ``low-temperature'' regime). In order to achieve this extension, we establish a tight version of the Lee-Yang theorem for the Ising model on hypergraphs, improving a classical result of Suzuki and Fisher.

Joint work with Alistair Sinclair and Piyush Srivastava.

PDF icon The Ising Partition Function: Zeros and Deterministic Approximation
Sampling Elements with Fixed Rank in Graded Posets
3:30 pm – 4:00 pm
Speaker: Dana Randall, Georgia Institute of Technology

We show that for certain classes of posets, biased Markov chains that walk along edges of their Hasse diagrams can be used to approximately generate samples with any fixed rank in expected polynomial time. A noteworthy application of our method is sampling restricted classes of integer partitions of n. We give the first provably efficient Markov chain algorithm to uniformly sample integer partitions of n from various natural restricted classes. Related applications include sampling permutations with a fixed number of inversions and lozenge tilings on the triangular lattice with a fixed average height.

Weitz's Algorithm and the Lovasz Local Lemma
4:00 pm – 5:00 pm
Speaker: Piyush Srivstava, Tata Institute of Fundamental Research
The work of Shearer, and of Scott and Sokal, established important connections between the study of the independence polynomial evaluated at negative activities and the Lovasz local lemma. In particular, it is known that the zero free region (known as the "Shearer region") of the independence polynomial around the origin determines the optimal region of applicability for certain forms of the Lovasz local lemma. 
 
Recent results (of Patel and Regts, Galanis, Goldberg and Stefankovic, and of an earlier version of this work) have shown that the Shearer region also defines a "complexity-theoretic" phase transition analogous to the one on the positive activity side established by the results of Weitz and Sly: in particular, evaluating the independence polynomial admits an FPTAS in the Shearer region, but becomes NP-hard outside it. 
 
In this work, we perform an optimal analysis of an adaption of Weitz's correlation decay method inside the Shearer region that allows us to produce a much finer picture of the above transition on the algorithmic side. With this improved analysis, we are also able to show non-trivial applications to problems related to the Lovasz Local lemma. In particular, we give a new sub-exponential time algorithm for testing membership in the Shearer region, and also give a new sub exponential time algorithmic version of the LLL using black box evaluations of the independence polynomial.
 
Joint work with Nicholas J. A. Harvey and Jan Vondrák.

Tuesday, June 6th, 2017

A Complexity Classification of Six Vertex Models as Holant Problems
9:30 am – 10:30 am
Speaker: Jin-Yi Cai, University of Wisconsin-Madison
I will give a dichotomy theorem for all complex valued six vertex models expressed as Holant problems with an (asymmetric) constraint function of arity 4. We also describe a refined classification that show that there is an additional tractable class of problems for planar instances. There is a (non-local) connection between this and spin systems, where the spin values are represented by orientations of loops. Time permitting, I will also describe an extension to the 8-vertex model.  These will be basic building blocks for a full classification theorem on Holant problems on the Boolean domain for all constraint functions that are not necessarily symmetric.
 
Joint work with Zhiguo Fu, Shuai Shao and Mingji Xia
PDF icon A Complexity Classification of Six Vertex Models as Holant Problems
Uniform Sampling through the Lovász Local Lemma
11:00 am – 12:00 pm
Speaker: Heng Guo, Queen Mary, University of London
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 new connections between the variable framework of the Lov\'asz Local Lemma and some classical sampling algorithms such as the "cycle-popping" algorithm for rooted spanning trees by Wilson. Among other applications, we discover new algorithms to sample satisfying assignments of k-CNF formulas with bounded variable occurrences. 
 
Based on joint work with Mark Jerrum and Jingcheng Liu.
PDF icon Uniform Sampling through the Lovász Local Lemma
The Replica Predictions in Random Estimation Problems
2:00 pm – 3:00 pm
Speaker: Florent Krzakala, ENS
Many estimations problems have an interesting structure even in the random case. For instance reconstructing a vector from random linear projections (as in compressed sensing or in coding theory), recovering the low rank structure of a matrix or a tensor polluted by random noise (sparse PCA, planted clique, sub-matrix localisation, clustering of mixtures of Gaussians...) 
 
There are now a number of such estimations problems for which we know how to prove the replica predictions for the mutual information, the MMSE and the phase transitions. I will discuss how recent ideas from statistical physics, mathematical physics and information theory have led, on the one hand, to new mathematical insights in these problems, leading to a characterisation of the optimal possible performances, and on the other to the understanding of the behaviour of approximate message passing, an algorithm that turns out to be optimal for a large set of problems and parameters.
 
Predicting Phase Transitions for Hyper-graph Coloring with the Cavity Method
3:00 pm – 3:30 pm
Speaker: Marylou Gabrié, École Normale Supérieure Paris
For a large class of random CSPs, the satisfiability threshold, corresponding to the critical density of constraints above which no more solution exists, may be predicted by methods from statistical physics. Additionally, such methods revealed the existence of several other phase transitions before satisfiability undergone by the set of solutions, as the problem is increasingly constrained. We apply these technics to a generalization of the coloring problem on random graphs to random hyper-graphs. Given a fixed number of colors, what is the critical density of hyper-edges above which it is not possible to color the hyper-graph without monochromatic hyper-edges? Above which density sampling the set of proper colorings with a Markov chain becomes hard? 
 
This is joint work with Lenka Zdeborova, Guilhem Semerjian, Varsha Dani and Laura Florescu, initiated at the Simons institute during the Counting Complexity and Phase Transitions Program.
PDF icon Predicting Phase Transitions for Hyper-graph Coloring with the Cavity Method
Rapid Mixing of Hypergraph Independent Set
4:00 pm – 5:00 pm
Speaker: Yumeng Zhang, UC Berkeley
Independent sets on hypergraphs can be encoded as 0-1 configurations on the set of vertices such that each hyperedge is adjacent to at least one 0. This model has been studied for its large gap between efficient MCMC algorithms (previously d <(k-1)/2) and the conjectured onset of computational hardness (d > O(2^{k/2}) ), where d is the largest degree of vertices and k is the minimum size of hyperedges. In this talk we provide a percolation approach to this model and show that the Glauber dynamics is rapid mixing for d < O(2^{k/2}), closing the gap up to a multiplicative constant.
 
This is joint work with Jonathan Hermon and Allan Sly.
PDF icon Rapid Mixing of Hypergraph Independent Set

Wednesday, June 7th, 2017

Dichotomy for Real Holant^c Problems
9:30 am – 10:30 am
Speaker: Pinyan Lu, Shanghai University of Finance and Economics
Holant problems capture a class of Sum-of-Product computations such as counting matchings. It is inspired by holographic algorithms and is equivalent to tensor networks. Counting CSP is a special case. Therefore a classification for Holant problems is more difficult to prove. This is so not only because it implies a classification for counting CSP, and the deeper reason is the existence of  more intricate polynomial time tractable problems.
 
We discover a new family of constraint functions which define polynomial time computable counting problems. These constraints do not appear in counting CSP, and no newly discovered tractable constraints can be symmetric. It has a delicate support structure related to error-correcting codes. Local holographic transformations is fundamental in its tractability. We show that this new family supplies the last piece of tractability and its discovery enables us to prove a complexity dichotomy theorem for all Holant problems defined by any real valued constraint function set on Boolean variables and contains two 0-1 pinning functions. Previously, dichotomy for  the same framework was only  known for symmetric constraint functions.  We also prove a dichotomy for a variant of counting CSP as a technical component toward this Holant dichotomy.
 
PDF icon Dichotomy for Real Holant^c Problems
The Complexity of Graph Motif Parameters
11:00 am – 12:00 pm
Speaker: Radu Curticapean, Hungarian Academy of Sciences
We present a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of H-copies (induced or not) in an input graph G, and the number of homomorphisms from H to G.
 
We use the framework of graph motif parameters to obtain faster algorithms for counting subgraph copies of fixed graphs H in host graphs G. Furthermore, we prove a general complexity dichotomy for evaluating graph motif parameters: Given a class C of such parameters, we consider the problem of evaluating a parameter f from C on input graphs G, parameterized by the number of induced subgraphs that f depends upon. For every recursively enumerable class C, we prove the above problem to be either FPT or #W[1]-hard, with an explicit dichotomy criterion. This allows us to recover known dichotomies for counting subgraphs, induced subgraphs, and homomorphisms in a uniform and simplified way.
 
Based on joint work with Holger Dell and Dániel Marx.
Matchings and the Switch Chain
2:00 pm – 2:30 pm
Speaker: Martin Dyer, University of Leeds
The switch chain is a simple Markov chain for generating a perfect matching in a graph. We studied this for classes of  bipartite graphs in a 2016 paper. We will describe some extensions of this work to classes of  nonbipartite graphs.

 

PDF icon Matchings and the Switch Chain
What Can Be Sampled Locally?
2:30 pm – 3:00 pm
Speaker: Yitong Yin, Nanjing University
The local computation of Linial [FOCS'87] and Naor and Stockmeyer [STOC'93] concerns with the question of whether a locally definable distributed computing problem can be solved locally: specifically, for a given local CSP whether a CSP solution can be constructed by a distributed algorithm using local information. In this talk, we consider the problem of sampling a uniform CSP solution by distributed algorithms, and ask whether a locally definable joint distribution can be sampled from locally. Two distributed sampling algorithms and some lower bounds for distributed sampling will be introduced.

 

PDF icon What Can Be Sampled Locally?

Thursday, June 8th, 2017

The Complexity of Counting Generalized Colorings: New Results and Challenges
9:15 am – 10:15 am
Speaker: Johann Makowsky, Technion - Israel Institute of Technology
Let $P$ be a graph property. We look at graph colorings with $k$ colors where each color class induces a graph satisfying $P$. By a result of Makowsky and Zilber (2005) the number of such colorings  $\chi_P(G;k)$ is a polynomial in $k$. We present recent results and open problems on the complexity of evaluating $\chi_P(G;\lambda)$ for various  properties $P$ and (not only integer) values of $\lambda$. 
 
This is joint work with A. Goodall, M. Hermann, T. Kotek and S. Noble which was initiated during last year's program "Counting Complexity and Phase Transitions". See also arXiv:1701.06639v1 [math.CO].
 
Finding Detours is Fixed-parameter Tractable
10:15 am – 11:00 am
Speaker: Ivona Bezáková, Rochester Institute of Technology
We consider the following natural "above guarantee" parameterization of the classical Longest Path problem: For given vertices s and t of a graph G, and an integer k, the problem Longest Detour asks for an (s,t)-path in G that is at least k longer than a shortest (s,t)-path. Using insights into structural graph theory, we prove that Longest Detour is fixed-parameter tractable (FPT) on undirected graphs and actually even admits a single-exponential algorithm, that is, one of running time exp(O(k)) poly(n). This matches (up to the base of the exponential) the best algorithms for finding a path of length at least k.
 
Furthermore, we study the related problem Exact Detour that asks whether a graph G contains an (s,t)-path that is exactly k longer than a shortest (s,t)-path. For this problem, we obtain a randomized algorithm with running time about 2.746^k, and a deterministic algorithm with running time about 6.745^k, showing that this problem is FPT as well. Our algorithms for Exact Detour apply to both undirected and directed graphs.
 
This is joint work with Radu Curticapean, Holger Dell, and Fedor V. Fomin.

 

Order Detection under Pairwise Measurements
11:30 am – 12:30 pm
Speaker: Jiaming Xu, University of Pennsylvania
One of the most pressing challenges in genomics is to reconstruct a long, and contiguous genome sequence from short contigs. Recent work shows that long-range link information contained in Hi-C data and Chicago date can be exploited to recover the correct orders among contigs. In particular, there tends to be higher Hi-C link or Chicago link densities between pairs of two closely located contigs. For studying the problem of ordering contigs based on long-range link information, we propose a planted Hamiltonian path model, where edges on the hidden Hamiltonian path tend to be more heavily weighted than other edges. The goal is to recover the hidden Hamiltonian path from observation of edge weights. We identify the sharp information-theoretic limits of exact recovery and show that a simple greedy algorithm achieves the exact recovery limit within a factor of two.

 

PDF icon Order Detection under Pairwise Measurements