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.
As we already explained in the main description of the proposal, the common belief is that hard phases in optimization and inference problems are unbreakable by any polynomial time algorithm and the solution typically requires a time growing exponentially with N.
Given that we are going to test algorithms that may work in polynomial time to find solutions in the hard phases, in case of success, the present proposal would produce a new paradigm for computational complexity in this class of problems.
Moreover, we see a strong limitation in the fact that most, if not all, of the algorithms which have been solved analytically, are linear algorithms.
We plan to study algorithms which are not in this category: the new polynomial time algorithms will work certainly better than linear algorithms and hopefully will break the hard phase.
In that case, our results will generate great interest in trying to describe analytically the new polynomial-time algorithms, which are at present not very much studied.
REFERENCES
M Mezard, G Parisi, R Zecchina, Analytic and Algorithmic Solution of Random Satisfiability Problems, Science 297:812 (2002a)
M Mezard, R Zecchina, Random k-satisfiability problem: From an analytic solution to an efficient algorithm, Phys. Rev. E 66:056126 (2002b)
S Mertens, M Mezard, R Zecchina, Threshold values of random K-SAT from the cavity method, Random Struct. Algorithms, 28:340 (2006)
A Montanari, G Parisi, F Ricci-Tersenghi, Instability of one-step replica-symmetry-broken phase in satisfiability problems. Journal of Physics A: Mathematical and General, 28:2073 (2004)
R Mulet, A Pagnani, M Weigt, R Zecchina, Coloring random graphs, Phys. Rev. Lett. 89:268701 (2002)
L Zdeborova, F Krzakala, Phase transitions in the coloring of random graphs, Phys. Rev. E 76:031131 (2007)
M Mezard, G Parisi, MA Virasoro, Spin Glass Theory and Beyond, World Scientific, Singapore, (1987)
L Zdeborova, F Krzakala, Statistical physics of inference: Thresholds and algorithms, Adv. Phys. 65:453 (2016)
Y Iba, The Nishimori line and Bayesian statistics, J. Phys. A: Math. and Gen. 32:3875 (1999)
H Nishimori, Statistical physics of spin glasses and information processing: an introduction (Clarendon Press, 2001)
M Mezard, A Montanari, Information, Physics, and Computation, Oxford University Press (2009)
A Decelle, F Krzakala, C Moore, L Zdeborova, Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications, Physi. Rev. E 84:066106 (2011)
M Mezard, A Montanari, Reconstruction on trees and the spin glass transition, J. Stat. Phys. 124, 1317 (2006)
C Borgs, J Chayes, E Mossel, S Roch, The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels, in Proc. FOCS '06 [arXiv:math/0604366](2006)
F Krzakala, C Moore, E Mossel, J Neeman, A Sly, L Zdeborova, P Zhang, Spectral redemption in clustering sparse networks, PNAS 110:20935 (2013)
A Saade, F Krzakala, L Zdeborova, Spectral clustering of graphs with the Bethe Hessian, Advances in Neural Information Processing Systems, 406 (2014)
F. Ricci-Tersenghi, G. Semerjian and L. Zdeborova, Typology of phase transitions in Bayesian inference problems, Phys. Rev. E 99, 042109 (2019)
T Kirkpatrick. EGD Cohen, J Dorfman J, Fluctuations in a nonequilibrium steady state: Basic equations, Phys. Rev. A 26:950 (1982)
BM Law, JV Sengers, Fluctuations in fluids out of thermal equilibrium, J. Stat. Phys. 57:531 (1989)
B Derrida, Non-equilibrium steady states: fluctuations and large deviations of the density and of the current, J. Stat. Mech. P07023 (2007)
L Bertini, A De Sole, D Gabrielli, G Jona-Lasinio, C Landim, Macroscopic fluctuation theory, Rev. Mod. Phys. 87:593 (2015)
A Montanari, G Semerjian, Rigorous Inequalities between Length and Time Scales in Glassy Systems, J. Stat. Phys. 125:23 (2006)
S Kirkpatrick, CD Gelatt, MP Vecchi, Optimization by simulated annealing, Science 220:671 (1983)
RH Swendsen, JS Wang, Replica Monte Carlo simulation of spin glasses Physical Review Letters 57 : 2607-2609 (1986)
K Hukushima, K Nemoto, Exchange Monte Carlo method and application to spin glass simulations, J. Phys. Soc. Jpn. 65:1604 (1996)
DJ Earl, MW Deem, Parallel tempering: Theory, applications, and new perspectives, Phys. Chem. Chem. Phys. 7:3910 (2005)
S Seitz, M Alava, P Orponen, Focused local search for random 3-satisfiability, J. Stat. Mech. P06006 (2005)
M Alava, J Ardelius, E Aurell, P Kaski, S Krishnamurthy, P Orponen, S Seitz, Circumspect descent prevails in solving random constraint satisfaction problems, PNAS 105:15253 (2008)
C Baldassi, C Borgs, J Chayes, A Ingrosso, C Lucibello, L Saglietti, R Zecchina, Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes, PNAS 113:E7655 (2016)
M. Ostilli, C. Presilla, Exact Monte Carlo time dynamics in many-body lattice quantum systems, J. Phys. A 38, 405-426 (2005)