Paata Ivanishvili




Thursday, December 5, 2019 - 11:00am


RH 306

Let a_ij be a finite collection of real numbers, and let s_i and s_j be spins (they take only two values +1 or -1). The goal is to choose the spins s_i and s_j so  that to maximize the double sum a_ij s_i s_j, where the summation runs over all indecies from 1 to n such that i does not qual to j.  If a_ij =1 then the sum is maximized if all spins have the same sign which gives the result to be of order n^2. However, if a_ij=-1 then the sum is maximized when half of the spins take value 1 and the other half -1. When a_ij are arbitrary real numbers this becomes a nontrivial problem (also known as Dean's problem). The problem is well understood  in average when a_ij are i.i.d symmetric  +1 or -1 random vairables  (the Sherrington--Kirkpatrick model).  We will speak about possible  lower bounds of  the maximum in terms of arbitrary real numbers a_ij,  its extensions to d-spin case, some conjectures in this area, and their applications in quantum computing.