Algorithms, Dynamics and Connections with Phase Transitions

该项目的重点是算法和相变之间的相互作用。我们在NP类中考虑计算问题。这些都是通信网络、生物学、编码理论和许多其他领域中大量重要实际问题的抽象。这里，我们关注NP中问题的随机实例，而不是最坏的情况。这种方法在许多方面都是有动机的。例如，像在编码理论中一样，处理随机实例可能是问题的一部分。在其他情况下，随机实例会产生我们所称的统计-计算权衡。也就是说，调整问题的参数，我们生成实例族，其可处理性从有效可解到(据信是)计算困难。这里我们特别考虑称为随机约束满足问题(RCSP)的实例。这些是经典组合或代数问题的随机实例，如图着色、k-可满足性等。物理学家一直将rCSP作为无序系统的模型进行研究。他们发展出了巧妙的、数学上不严格的想法，在过去的十年里，这些想法已经发展成为一种名为腔方法的工具包。空穴的预测与rCSP解空间的大小和几何形状有关。在这个项目中，我们计划研究rCSP中Gibbs分布的采样算法。这些分布定义在rCSP的解空间上，例如，对于图着色，这是在底层图的k-着色上的均匀分布。我们关注两种不同的抽样方法。第一种方法是基于马尔可夫链蒙特卡罗(MCMC)方法。自然存在的问题是，对于给定的一组参数，MCMC动态混合的速度有多快。MCMC算法实现马尔可夫链简单，通常具有显著的经验性能。然而，分析它们可能是具有挑战性的。我们还打算研究一种非MCMC抽样方法。该计划将使用[Efthy miou SODA2012]中介绍的方法。该算法与MCMC算法有很大的不同。IIT的实现和描述非常简单，其性能也非常显著。有许多非常有趣的方向值得用这种方法来探索。此外，我们计划从空腔方法来研究某些预测的可靠性。吉布斯分布：研究吉布斯分布的自然方法是从空间相关性衰减的角度。在这项研究中，自然产生了几个不同的空间混合概念。其中一些概念似乎与算法的性能有关。我们计划研究随机图上非对称分布的空间混合，重点是所谓的重建阈值。我们还打算研究自旋玻璃的非重构问题，例如爱德华兹-安德森模型。我们关注非重构，因为重构的On-set意味着rCSP的采样和搜索算法不再是多项式的。自由能量：许多自然推理和学习问题自然地被转化为rCSP，例如，用于网络推理的随机块模型(SBM)，神经元的模型，如委员会机器Ising Perceptron。从自由能的角度研究这些模型是很自然的。我们打算利用自由能的形式为非对称SBM的推理算法建立信息下界，并研究神经网络物理模型的基本性质，包括容量估计，或寻找它们的能量图景。

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.