Physics 7654: Dynamical systems that solve hard problems

Spring
2018

 

 

This is a one-time, 8-lecture course about a new kind of meta-algorithm for solving hard problems. We meet Wednesdays and Fridays 2:30-4:00 in Rockefeller 230, starting February 21. Prerequisites are (1) linear algebra and (2) the ability to program in some language. To receive credit (for this part of  Physics 7654) you need to do two of the four assignments.

Here is the algorithm, in one equation (a dynamical system for a vector variable):

Problems are encoded by the two "constraint projections" P1 and P2. This algorithm was discovered independently in three completely different contexts, and slight variants are commonly known by the names ADMM, Douglas-Rachford and HIO. The version above is a distillation of these and called RRR. Here is a recent publication where you can find out more.

The course will feature applications from physics (diffractive imaging, spin glasses), computer science (graph coloring, satisfiability), and home economics (cake cutting).

If you are considering taking the course, start by thinking about different ways to solve this puzzle. We will design a dynamical system to solve it in class.

The Dutta Notebooks (homework solutions)

Course github site

proxpy