Our task in this proposal is to find and test new algorithms that can optimize, learn from or satisfy constraints that occur in the complex systems, driven by vast amounts of real-world data, that now manage our lives. Even when idealized, these problems are often exponentially hard in principle yet, if the constraints are few enough, easy to solve in practice. But small increases in complexity can make problems very hard and with larger increases, impossible. This pattern of easy/hard/impossible is ubiquitous and is often found with sharp boundaries, like phase transitions, separating the regions. We focus on the hard phases, for which little science exists to understand the distributions of difficulty and the best methods of solution. We seek to unify the phase diagrams of these problems and to create powerful approaches to their approximate solution on large but finite scales, bringing a combination of formal analysis and computer experimentation to bear. By combining the replica and the cavity methods of analysis with simple practical methods that go arbitrarily far from equilibrium, do not satisfy any detailed balance condition and are known to be able to break many sophisticated and putatively absolute bounds, we believe we can achieve an important advance in optimization, constraint satisfaction, and inference, with impact on applications. We will focus on problems in which high entropy and low signal to noise impede search, leading to glassy behaviour even though a highly ordered phase can easily be shown to exist. Reconstructing a hidden structure using small `hints' is then a critical test of inference.
