Monday, March 28th, 2016

9:30 am10:15 am
A homomorphism from a graph G to a graph H is a map from the vertices of G to the vertices of H that maps every edge of G to an edge of H. Graph homomorphisms capture many interesting combinatorial structures such as independent sets and proper colourings. This talk addresses the ``the classification program of counting complexity'' as it applies to the problem of approximately counting graph homomorphisms.
It includes recent work with Andreas Galanis and Mark Jerrum.
10:30 am11:15 am
This talk will focus on connections between phase transitions and the computational complexity of approximating the partition function of spin systems. A principal example of such a connection is in the context of approximating the number of independent sets in graphs of bounded degree, where the uniqueness threshold on the infinite regular tree pinpoints the boundary of efficient computation. 
We will be interested in similar connections for spin systems on bounded degree graphs. Examples of the computational problems we will consider are: 
(i) approximately counting colorings,
(ii) approximately counting independent sets on bipartite graphs (#BIS),
(iii) approximating the partition function of the ferromagnetic Potts model.
Based on the phase transitions of the models, we will discuss hardness results for these problems on bounded degree graphs.
Joint work with: Jin-Yi Cai, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, and Eric Vigoda.
11:45 am12:30 pm

There has been great progress in classifying the approximation complexity of anti-ferro 2-spin systems. We will first review these results, and then talk about some new results regarding ferro 2-spin systems. In particular, we conjecture a complexity transition threshold that is almost tight for ferro systems. We confirm the conjecture for some range of the parameters and provide evidence for the rest. In addition we will show some (hardness) results when going beyond non-negative weights to complex weights.

It includes joint work with Pinyan Lu and Leslie Goldberg. 

2:00 pm2:45 pm
The sparse dense dichotomy of structures takes various forms. It can also be defined in terms of substructure counting. The related integrality theorem may be seen as a tool for defining a proper scaling for convergence  criteria for structural limits.
Joint work with Patrice Ossona de Mendez (Paris and Prague).
2:45 pm3:15 pm

In this light-hearted talk, we will adopt the unconventional viewpoint that a "polynomial time" vs. "probably not polynomial time" dichotomy for a counting problem may not be a stopping point for further research on the same problem. We will survey different ways to classify the problem further by providing faster exponential-time algorithms, or by proving hardness results under hypotheses such as the exponential time hypothesis.

4:00 pm5:00 pm

Computability theory, as developed most notably by Turing, is a successful mathematical theory of the limits of what can be computed. Perhaps remarkably, it does not significantly involve quantities. Theories similarly light on quantitative analysis have also been provided for important issues in the complexity of computation, such as NP-completeness. However, there remain wide areas of computation, such as the evaluation of probabilities, multivariate integration, and the counting of discrete structures, where the objects to be manipulated are inherently quantitative. In this talk we shall focus on this area, in which computational complexity becomes inseparable from quantitative concerns. We highlight counting problems, in which one seeks to compute the number of discrete objects of a certain kind. The number may be exponentially large compared to the size of the objects allowed, but can be written down as a polynomial number of digits. We shall review recent progress that makes it possible to classify a wide range of such counting problems, both exact and approximate, according to their computational difficulty. This classification is sometimes offered in the strong sense of a dichotomy theorem, which classifies according to difficulty not just a single problem but a whole class. Proofs of such theorems exploit a variety of techniques, including holographic transformations.

Light refreshments will be served before the lecture at 3:30 p.m.

Tuesday, March 29th, 2016

9:30 am10:15 am
I will discuss the current understanding of the power of holographic algorithms with matchgates. The focus will be on the Universality of this class of algorithms for those #CSP type problems that are #P-hard in general, yet solvable over planar graphs.
10:30 am11:15 am

The theory of holographic algorithms introduced by Valiant represents a novel approach to achieving polynomial-time algorithms for seemingly intractable counting problems via a reduction to counting planar perfect matchings and a linear change of basis. Two fundamental parameters in holographic algorithms are the domain size and the basis size. Roughly, the domain size is the range of colors involved in the counting problem at hand (e.g. counting graph k-colorings is a problem over domain size k), while the basis size \ell captures the dimensionality of the representation of those colors. A major open problem has been: for a given k, what is the smallest \ell for which any holographic algorithm for a problem over domain size k ``collapses to'' (can be simulated by) a holographic algorithm with basis size \ell? Cai and Lu showed in 2008 that over domain size 2, basis size 1 suffices, opening the door to an extensive line of work on the structural theory of holographic algorithms over the Boolean domain. Cai and Fu later showed for signatures of full rank that over domain sizes 3 and 4, basis sizes 1 and 2, respectively, suffice, and they conjectured that over domain size k there is a collapse to basis size \lfloor\log_2 k\rfloor. In this talk, we give an algebraic proof resolving this conjecture in the affirmative for signatures of full rank for all k.

11:45 am12:30 pm
Partition functions of edge-coloring models are graph parameters closely related to counting graph homomorphisms. They appear in several academic disciplines; e.g. as Lie algebra weight systems in the theory of Vassiliev knot invariants, as Holant problems in theoretical computer science, as tensor networks in quantum information theory and as partition functions of vertex models in statistical physics.  In this talk I will describe a quasi polynomial time approximation algorithm for partition functions of a certain class of edge-coloring models.
2:00 pm2:45 pm

We consider the importance of the choice of metric in path coupling, and its relationship to the technique of path coupling with stopping times. We provide strong evidence that the stopping time method is no more powerful than standard path coupling using a carefully chosen metric. However, the stopping time approach does give insight into the design of good metrics for specific problems. We give illustrative applications, to sampling independent sets in hypergraphs, and to sampling colourings of hypergraphs and bipartite graphs.

Joint work with Magnus Bordewich and Marek Karpinski

3:00 pm3:45 pm
Matrix partitions are a generalization of graph homomorphisms.  Given a d-by-d symmetric matrix M with entries from {0,1,*}, an M-partition of a graph G is a partition of its vertices into sets V_1, ..., V_d such that:
- if M[i,j] = 0, there are no edges between V_i and V_j;
- if M[i,j] = 1, then G contains every possible edge between V_i and V_j;
- if M[i,j] = *, there are no restrictions on the edges between V_i and V_j.
Thus, it can be seen that a homomorphism from a G to a graph H corresponds to an M-partition for a matrix M that contains no 1's.
I will discuss a complexity dichotomy for counting list M-partitions, i.e., M-partitions where each vertex of the graph has, in addition, a list of the parts of M in which it may be placed. These problems are #P-complete if M has a structure we call a derectangularizing sequence, and in FP otherwise. I will also briefly discuss work on the problem without lists.
Joint work with Martin Dyer, Andreas Goebel, Leslie Ann Goldberg, Colin McQuillan and Tomo Yamakami.

Wednesday, March 30th, 2016

9:30 am10:15 am

H-colourings of a graph G (a.k.a. homomorphisms from G to H) generalise familiar proper vertex colourings of G.  More than 15 years ago, Dyer and Greenhill presented a dichotomy for exactly counting H-colourings.  That was for exact counting, and, even now, there is only a partial complexity classification for approximate counting. A familiar theme in the study of CSPs is that the “conservative” case is often easier to resolve.  This is one reason to look at list H-colourings.  The decision problem for list H-colourings was studied by Feder, Hell and Huang, who proved a dichotomy result.  In this talk, I’ll present a classification for the problem of approximately counting list H-colourings of a graph, and briefly consider weighted variants.

This is joint work with Andreas Galanis and Leslie Ann Goldberg (Oxford), and others.

10:30 am11:15 am
I will describe some recent observations related to the calculation of the Ising partition function, or equivalently the enumeration of the edge-cuts of graphs. In particular I will discuss geometric representation of binary linear codes, 4-dimensional discrete Ihara-Selberg function and relation with the 3-dimensional Ising and dimer problems, and complexity of the Max-Cut problem for embedded graphs.
11:45 am12:30 pm
Part of the importance of the partition function in the study of spin systems comes from the fact that the derivatives of its logarithm (i.e., derivatives of the free energy) encode mean values of natural observables of these spin systems.  Examples of such mean observables include the mean energy and the mean magnetization in the Ising model, the average size of matchings in the monomer-dimer model, and the average size of independent sets in the hard core lattice gas model.  However, unlike the case of partition functions, not much was not until recently about the computational complexity of exactly computing such mean observables.
In this talk, we describe some recent results establishing the #P hardness of all the mean observables listed above. We also point out connections with the study of complex zeros of partition functions that arose in the course of proving these results.
This talk is based on joint work with Leonard J. Schulman and Alistair Sinclair.
2:00 pm2:45 pm

Although a general dichotomy for exact counting CSP was proved, the complexity for approximation remains wildly open. I will focus on the program to classifying approximability for bounded-degree Boolean #CSP. Dyer, Goldberg, Jalsenius and Richerby gave a beautiful full classification when the maximum degree is six or above, in which no non-trivial approximation result appears. However, for smaller degrees (maximum degree is five or below), interesting tractable (in term of approximation) cases do appear and a complete classification is far from known.  In this talk, I will summary the known results in this range and propose a number of interesting open questions.

3:00 pm3:45 pm
The canonical paths argument is an important technique to prove the rapid mixing property of Markov chains. It plays an important role in the analysis of Markov chains for sampling matchings, Jerrum-Sinclair's chain for Ising model and the Markov chain for permanent. However, there are much fewer success examples comparing to coupling, another technique for bounding mixing time. The main reason is that there is no systematic approach or general recipe to design canonical paths.
Recently, McQuillan gave a nice generalization of the Glauber dynamics for sampling matchings in the framework of Holant problems. Based on his exploration, we develop a general theory to design canonical paths for Markov chains: We reduce the task of designing canonical paths to solving a set of linear equations, which can be easily done even by hand.
In this talk, I will first introduce McQuillan's generalization and our new characterization of the canonical paths. Then I will interpret many known success examples of canonical paths arguments in our new theory. Finally, I will show how to obtain fully polynomial-time randomized approximation schemes (FPRAS) for counting the number of b-matching with b<=7 and b-edge-cover with b<=2 using our new approach, which are natural generalizations of counting matchings and edge covers in graphs.
This is a joint work with Lingxiao Huang and Pinyan Lu.
4:15 pm5:00 pm
We consider the problems #Sub(C) for fixed graph classes C: Given as input a graph H from C (the pattern) and another graph G, count the occurrences of H as a subgraph in G. Our goal is to understand which properties of the pattern class C make the problem #Sub(C) easy/hard. For instance, for the class of stars, we can solve this problem in linear time. For the class of paths however, it subsumes counting Hamiltonian paths and is hence #P-hard.
As it turns out, the mere assumption of FP not being equal to #P fails to give a sweeping dichotomy for this problem, since there exist intermediate problems. However, adopting the framework of fixed-parameter tractability, we show how to classify the problems #Sub(C) as either polynomial-time solvable or #W[1]-hard: A class C lies on the "easy" side of this dichotomy if the graphs appearing in it have vertex-covers of constant size.
We will obtain similar dichotomies for the problems of counting colored subgraphs, for counting subgraphs modulo fixed numbers, and for other variations of the problem. These results show that parameterized complexity theory, apart from being interesting on its own, can help to obtain "classical" dichotomies.
The talk will be self-contained and begins with an introduction to the necessary concepts from parameterized complexity.

Thursday, March 31st, 2016

9:30 am10:15 am

The complexity landscape of approximate computing partition functions appears to be quite complicated. This makes the problem of classifying such problems according to their approximation complexity very difficult. We try to separate counting problems with respect to gadget reductions, which is equivalent to the study of clones related to the problem, that is, sets of functions or relations closed under gadgets. We survey the several main approaches to such classification, as well as some new and existing results.

10:30 am11:15 am
The partition functions count homomorphisms from an input graph G to a fixed graph H.  In the setting of algebraic complexity (which generalises exact counting complexity), probing "from the left" turns out to be more useful.  We show that enumerating monomials that are in bijection with homomorphisms from a fixed graph G to an input graph H naturally gives rise to polynomial families complete for VP and VNP, the algebraic analogues of P and NP defined by Valiant in 1979. These provide the first example of a family that is defined independent of a circuit model and that is complete for VP.
The cut enumerator polynomial Cut_q (for a natural number q >1), defined by Burgisser in 2000, is known to have "intermediate" status as follows: Over any finite field of size q, it is in VNP, and unless PH collapses, is neither in VP nor VNP-complete. Till recently this was the only known family with these properties. Abstracting this
technique, we show that a host of other similar polynomials based on a generalised version of enumerations of satisfying assignments, vertex covers, cliques, 3 dimensional matchings, and closed walks, all have the same properties. Furthermore, augmenting recent results due to Grochow using extension complexity bounds in polyhedral theory, we show that two of these polynomials are provably not obtainable as monotone affine polynomial-size projections of the permanent.
11:45 am12:30 pm

Evaluation of the chromatic polynomial is easy on finitely many points, and #P hard everywhere else. We call this the difficult point property $DPP$. Let $F$ be a graph property and $k$ be a positive integer. A function $f: V(G) \rightarrow [k]$ is an $F$-coloring if for every $i \in [k]$ the set $f^{-1}(i)$ induces a graph in $F$. The author and Boris Zilber have shown in 2006 that counting $F$-colorings with $k$ colors is a polynomial $P_F(G;k)$ in $k$. We show infinitely many examples of properties $F$, where $DPP$ holds for $P_F(G;k)$, and formulate several conjectures, including also multivariate graph polynomials.

2:00 pm2:45 pm
I will give an overview of  algebraic  geometry  and representation theory in complexity theory. I will discuss how it clarifies questions, its uses in proving lower bounds, and recent work on its potential use in developing algorithms and upper bounds.
3:00 pm3:45 pm

Many computational complexity problems, including constraint satisfaction and weighted counting constraint satisfaction problems, graph isomorphism, and others, can be expressed in a unified way as word problems in certain kinds of monoidal categories over finite tensor signatures. Using categories axiomitizes notions such as planarity and avoids long combinatorial descriptions, as well as characterizing the difference between problems. It allows the tools of category theory to be brought to bear on complexity problems and allows reductions to be expressed as functors. This approach also generates many new open problems as we vary the kind of monoidal category, the representation functor, and the tensor signature.

4:15 pm5:00 pm

Systems of polynomial equations can be used to compactly and elegantly model combinatorial problems in such a way that if a given combinatorial property is not satisfied, then the system of polynomial equations has no solution. If a system of polynomial equations has no solution, there exists a very specific algebraic proof of infeasibilty via the famous Hilbert's Nullstellensatz. In this talk we compare and contrast the complexity of Hilbert's Nullstellensatz certificates when the underlying combinatorial problem is NP-complete (such as Partition), as compared to problems known to be in P (such as 2-colorability or Matching).

Friday, April 1st, 2016

9:30 am10:15 am
Many problems in random combinatorial structures exhibit an apparent gap between the existential results and algorithmically achievable results, though no formal complexity theoretic hardness of these problems is known. Examples include the problem of proper coloring of a random graph, finding a largest independent set of a graph, random K-SAT problem, and many others. In our talk we consider a new example of such a gap for the problem of finding a  submatrix which achieves the largest average value in a given random matrix. We will consider some known and a new algorithm for this problem, all of which produce a matrix with average value constant factor away from the globally optimal one. We then consider the overlap structure of pairs of matrices achieving a certain average value, and show that it undergoes a certain  connectivity phase transition just above the value achievable by the best known algorithm. We conjecture that the onset of this overlap gap property marks the onset of the algorithmic hardness for this problem and in fact we conjecture that this is the case for most randomly generated optimization problems.
Joint work with Quan Li (MIT)
10:30 am11:15 am

We survey recent results on the power of LP relaxations for optimisation problems known as valued constraint satisfaction problems (CSPs) which might be of interest to the counting community.

11:45 am12:30 pm

We consider counting CSPs and Holant problems defined by general asymmetric constraints of unbounded arity. We give a fixed parameter tractable (FPT) algorithm for Holant problems, in terms of two parameters: the treewidth of the underlying graph and the "regularity" of the signatures. We define a notion of regularity for the signatures (constraint functions). And we show that the Holant problem defined by r-regular signatures on a graph of treewidth k can be computed within time r^O(k) poly(n). This covers the known FPT algorithms in terms of treewidth for spin systems, counting graph homomorphisms, counting CSPs with bounded-arity constraints, Holant problems and tensor networks on bounded-degree graphs, and counting matchings and perfect matchings on general graphs.