The study of random constraint satisfaction problems was initiated in the eighties with the objective of better understanding the generic properties of hard instances, and developing better heuristics. How much has been accomplished on the way to these objectives? I will present a review of partial results, conjectures, and open problems, emphasizing contributions from multiple research communities. I will also outline the connections between progress on this research direction and connection with 'applications' in machine learning, statistics, and information theory.

Monte Carlo sampling was initiated in the 40s by the likes of Ulam and Metropolis in Los Alamos, to study (atomic) physics problems. Since then, it has become a fantastic tool at the roots of statistical physics. A large part of the activity in this area is to develop better heuristics and to understand their properties.  We will present a review of partial results and open problems regarding sampling and estimation of the partition function from a physicist's point of view, with a focus on a very difficult problem called spin glasses. We will attempt to highlight the algorithms and methods used in practice, the problems for which better algorithms are needed, and the open problems for theoretical analysis.

This mini-course will present the fundamentals of analysis of convergence rates of discrete time Markov chains, and applications from statistical physics and combinatorics. It will start with an introduction to Markov chains and their properties, and relation between sampling and counting. Then it will discuss techniques for bounding the mixing time: The second session will focus on coupling and the third session on canonical paths and related concepts.

The first session of this mini course will take place on Monday, January 25 from 1:30 pm – 2:30 pm; the second session of this mini course will take place on Tuesday, January 26 from 9:30 am – 10:30 am. 

We consider some of the most recent refinements to classical counting complexity, namely, the parameterized complexity and the exponential-time complexity of counting problems.

In parameterized complexity, problem instances come together with a parameter k, and this allows for a more fine-grained complexity analysis than could be achieved by considering only the input size n. (For example, in the setting of graphs, possible parameters could be the maximum degree, genus or certain width-measures of the graph.) We will survey various parameterizations of the permanent, together with lower bounds under the exponential-time hypotheses ETH and SETH. These hypotheses postulate lower bounds on the running time for deciding satisfiability of CNF-formulas and have been recently used to explain the lack of progress in many fundamental algorithmic questions.

We also consider the problems of counting general subgraphs H in a host graph G, parameterized by the size of H. This gives rise to the problems #Sub(C) for fixed graph classes C: For inputs H and G, where H is from C, we wish to count H-copies in G. We show a dichotomy theorem that, depending on C, establishes #Sub(C) to be either polynomial-time solvable or complete for #W[1], the parameterized analog of #P.