WP2: Algorithms and complexity

The investigation in this work package will contribute to the algorithmic aspects of the problems of matching theory and graph homomorphisms included in the work packages WP1+3 and to the following two main topics.

Complexity of approximation algorithms. For approximation algorithms we plan to build on techniques that we and our collaborators recently developed for some of these problems. For edit distance this entails using random walks and utilizing periodicity of the strings to speed-up the computation.One of our main tools to establish circuit lower bounds is communication complexity. Recently, there has been a great success in establishing so called simulation theorems which allow to lift lower bounds from decision tree complexity into communication lower bounds on the complexity of composed functions. Such communication lower bounds have applications in understanding circuit complexity, formula complexity and data structures.

For example, Koucký with collaborators recently established a novel simulation theorem for composition in asymmetric setting. This allowed them to prove new data structure lower bounds for the vector-matrix-vector multiplication problem. In another paper they established simulation theorems in the symmetric setting for the inner function of exponentially smaller size than previously known. Simulation theorems with constant size inner functions could be used to give new lower bounds in proof complexity. Gavinsky et al. look on the communication complexity of composition of functions with the aim of establishing circuit depth lower bounds and formula lower bounds. This was further extended by Dinur and Meir. They were able to prove stronger composition theorem and give a new proof of the best known formula lower bounds. We plan to utilize those techniques in our lower bound efforts.

Complexity and algorithms for problems on random graphs and hypergraphs. Our novel approach to studying the algorithmic complexity is to use advanced methods of statistical mechanics that are conjectured to provide exact predictions for the proposed problems. We then combine these methods and predictions with the classical probabilistic methods to prove the predictions.

Molloy recently proved that the chromatic number of every triangle-free graph must be at most . At the same time random regular graphs have chromatic number roughly twice smaller than that. The open question is whether there are natural ensembles of larger girth graphs that have chromatic number larger than the random regular graphs.

We will investigate several proposals for such graphs using the 1st and 2nd moment bounds on the chromatic number, as well as advanced methods of statistical mechanics that are conjectured to provide exact predictions for coloring of random regular and random Erdős–Rényi graphs.

For a fixed large number of colors qwe have algorithms able to color graphs of average degree smaller (in the learning order) than qlog q, yet from non-constructive probabilistic considerations we know that proper colorings exist up to average degree 2 qlog q. In attempts to provide heuristic explanations for this behavior work in statistical physics put forward a conjecture that certain type of solutions, called frozen, are hard to find. Recent work, however, suggested that other than frozen solutions still exist well beyond the average degree qlog q. It is hence an interesting question to investigate whether some algorithms are able to focus on those solution and break the current algorithmic barrier for random graph coloring at average degree qlog q.

Recent work related to the Pentagon problem provided heuristic arguments that triangle-free random 3-regular graphs indeed are with high probability 5-circular colorable. The present collaboration will investigate way in which this conjecture can be proven rigorously.

The Travelling salesmen problem (TSP) is one of the most famous combinatorial optimization problems. Existing work established a range of results on the problem with random weights taken from a probability distribution with non-negative support. In that case the properties of the distribution close to the infimum of its support are crucial. TSP with random weights that are supported on the real axes, including negative numbers, has not been addressed as far as we know. The extreme value statistics of the weight distribution will play a key role for the value of the optimal solution. We plan to provide a classification of probability distributions according to the minimal path length they lead to in a TSP of a fully connected graph with weights taken from the corresponding distribution.

Motivated by the problem of DNA assembly we will study the following theoretical problem. Consider a k-regular graph with edge weights chosen from some probability distribution P, the weights on the edges of a complete graph that do not belong to the k-regular subgraph are chosen from a distribution Q. Observe the full matrix of weights and aim to infer the edges of thek-regular subgraph. For k = 1 this can be seen as a planted bathing problem, for k = 2 this is related to the planted TSP problem (modulo the fact that in TSP the planted subgraph would be connected).

We will work on extending the class of combinatorial models for which computation of partition function is so-called det-tractable, i.e. reduces to computations of a polynomial (in the size of the original problem) number of determinants of matrices which are polynomial. Enabling exampling is the Ising model over planar graphs. We will work with other planar problems (beyond Ising), extensions to graphs embedded into surfaces of higher genus, and generalizations to higher alphabets. For problems which are proven to be of set-complexity we will also work on designing efficient algorithms for computing partition function improving state of the art.

For the Graphical Model problems which inference (partition function, sampling, marginal probability computation) do not admit polynomial solution we have three directions to explore: (a) variational approaches, e.g. based on ideas of belief propagation and more generally approaches based on gauge transformations and reparametrizations (changing parameters in the graphical models such that the partition function stay invariant); (b) stochastic algorithms, allowing efficient sampling of the series representing the partition function; (c) elimination algorithms, also related to Renormalization Group approaches of statistical physics, where one is looking for an optimal sequence of summations over variables and approximations. We will also explore synthetic approaches based on creative combinations of (a), (b) and (c). Additionally, we will work with problems allowing polynomial inference, then focusing on designing approximations which allow partition function (and other inference problem) computations in linear time.