Random structures, spin glasses and efficient algorithms

An Algorithm is a systematic procedure for solving a computational problem that can be implemented on a computer. An example is the Gaussian elimination method for solving a system of linear equations. The running time of an algorithm is the number of elementary steps (e.g., addition, modification of a symbol in a string, etc.) that the algorithm performs. Of course, the running time depends on the size of the input. For example, in the case of Gaussian elimination the size of the input is the number of symbols needed to write down (or enter) the linear system of equations. Denote this quantity by m. Then the running time of Gaussian elimination is bounded by m^3. Generally an algorithm is considered Efficient if for every possible input its running time is bounded by a polynomial in the size of that input. (Hence, Gaussian elimination is efficient.)In spite of intensive research since the early days of computing, there is a broad class of computational problems for which no efficient algorithms are known. In terms of complexity theory, most of these problems can be classified as NP-hard . One example is the Boolean Satisfiability problem (SAT). In this problem the input is a Boolean formula, and the objective is to find an assignment to the Boolean variables that satisfies the entire formula (if such a satisfying assignment exists).Although the SAT problem is NP-hard, it occurs as a sub-problem in numberless real-world applications. In fact, SAT is of similarly eminent importance in Computer Science as solving polynomial equations is in Algebra. Therefore, an immense amount of research deals with heuristic algorithms for SAT. The goal of this line of research is to devise algorithms that can efficiently solve as general types of SAT inputs as possible (although none of these methods solves all possible inputs efficiently).Despite this bulk of work, it remains extremely simple to generate empirically hard problem instances that elude all of the known heuristic algorithms. The easiest way to do so is by drawing a SAT formula at random (from a suitable but very simple probability distribution). Indeed, random input instances were considered prime examples of hard inputs to such an extent that it was proposed to exploit their hardness in cryptographic applications. Random SAT formulas also occur prominently in the seminal work on Algorithms and Complexity from the 1970s, where their empirical hardness was reckoned most vexing . However, it remained unknown why these types of instances eluded all known algorithms (let alone how else to cope with these inputs).Therefore, it came as a surprise when statistical physicists reported that a new algorithm called Survey Propagation ( SP ) experimentally solves these hard SAT inputs efficiently. Indeed, a naive implementation of SP solves within seconds sample instances with a million of variables, while even the most advanced previous SAT solvers struggle to solve inputs with a few hundred variables. SP comes with a sophisticated but mathematically non-rigorous analysis based on ideas from spin glass theory. This analysis suggests why all prior algorithms perform so badly. Its key feature is that it links the difficulty of solving a SAT input to geometric properties of the set of solutions.Though the physics methods have inspired the SP algorithm, they do not provide a satisfactory explanation for the success (or the limitations) of SP. Therefore, the goal of this project is to study these new ideas from spin glass theory from a Computer Science perspective via mathematically rigorous methods. On the one hand, we are going to provide a rigorous analysis of SP to classify what types of inputs it can solve. On the other hand, we intend to study the behaviour of algorithms from the point of view of the solution space geometry ; this perspective has not been studied systematically in Algorithms and Complexity before.