The area of optimization seeks, broadly, to minimize a cost function subject to constraints on the solution set. More concretely, it also concerns the design of efficient algorithms for finding optimal or near-optimal solutions. Over the past few years new approaches from Spin Glass Theory, a branch of statistical physics, have been used to propose solutions and efficient algorithms for hard optimization problems in Electrical Engineering and Computer Science.
This talk will overview this interplay and focus on two examples: (i) The Random Assignment Problem (RAP), which arises in a variety of practical scenarios; notably in crossbar switch scheduling. (ii) The Number Partitioning Problem (NPP), which models load balancing and multiprocessor scheduling. I will trace the history of these problems and state some conjectures regarding the cost and the structure of the optimal solutions obtained by the powerful (but non-rigorous) methods of physics. I will then sketch our resolution of the Parisi and Coppersmith-Sorkin Conjectures for the RAP, and of the local Random Energy Model(REM) Conjecture for the NPP. Finally, I will explain how the methods of physics have yielded remarkably efficient algorithms for image reconstruction, constraint satisfaction, and other problems.