Algorithms, Dynamics and Connections with Phase Transitions

点击翻译按钮获取中文摘要

The project focuses on an interplay between algorithms and phase transitions. We consider computational problems in the class NP. These are abstractions of a tremendous wealth of important practical problems in communication networks, biology, coding theory and many others. Here, we focus on random instances of problems in NP, rather than worst case ones. This approach is motivated in many ways. For example, dealing with random instances can be a part of the problem like in coding theory. In other cases, random instances give rise to what we call statistical - computational tradeoffs. That is, adjusting the parameters of the problem we generate families of instances whose tractability varies from efficiently solvable to (what is believed to be) computationally hard. Here we particularly consider instances of problems known as random Constraint Satisfaction Problems (rCSP). These are random instances of classical combinatorial, or algebraic problems such as the graph colouring, k-satisfiability etc. Physicists, have been studying rCSPs as models of disordered systems. They have developed ingenious alas mathematically non-rigorous ideas which over the past decade have grown into a toolkit called the Cavity Method. Cavity's predictions are related to the size and the geometry of the solution space of a rCSP. This allows us to understand and appreciate the challenges we have to deal in our algorithmic problems.In this project we plan to study sampling algorithms for Gibbs distributions in rCSPs. These distributions are defined over the solution space of the rCSP, e.g. for graph colourings this is the uniform distribution over the k-colourings of the underlying graph. We focus on two different approaches for sampling. The first one is based on the Markov Chain Monte Carlo (MCMC) method. The natural question there is how fast the MCMC dynamics mixes for a given set of the parameters. The MCMC algorithms are simple to implement Markov chains and usually they have a notable empirical performance. However, analysing them can be challenging.We also intend to study a non-MCMC approach to sampling. The plan is to use the approach introduced in [Efthymiou SODA2012]. This algorithm is very different than the MCMC ones. iIt is very simple to implement and describe, with a provably notable performance. There are a lot of very interesting directions that worth exploring with this approach.Furthermore, we plan to investigate the soundness of certain predictions from the Cavity method.Gibbs distributions: The natural way of studying Gibbs distributions is in terms of spatial correlation decay. There are several, different, notions of spatial mixing which arise naturally in the study. Some of these notions seem to be related to the performance of algorithms. We plan to study spatial mixing for non-symmetric distributions on random graphs with focus on the so-called reconstruction threshold. We also intend to study non-reconstruction problem for spin-glasses, e.g., the Edwards-Anderson model. We focus on non-reconstruction because the on-set of reconstruction signifies that sampling and search algorithms for rCSP stop being polynomial.Free Energy: Many natural inference and learning problems are cast naturally as rCSP, e.g., Stochastic Block Model (SBM) for networks inference, models of neurones like Ising Perceptron, the committee machine. It a natural to study these models in terms of their free energy. We intend to use the formalism of free energy to establish information lower bounds for inference algorithms for the non-symmetric SBM and study basic properties of physics' models of neural networks, including capacity estimates, or finding their energy landscape.