Department Seminar by Will Perkins

Wednesday, April 28, 2021 9:00 am - 9:00 am EDT (GMT -04:00)

Please Note: This seminar will be given online.

Probability seminar series

Will Perkins
University of Illinois at Chicago

Link to join seminar: Hosted on Webex

Frozen 1-RSB structure of the symmetric Ising perceptron


The Ising perceptron model is a toy model of a neural network storing random patterns.  The model can be phrased as a random constraint satisfaction problem: given a set of m n-dimensional Gaussian vectors X_i, solutions are binary vectors of length n whose inner product with each X_i lies in some interval.  For the symmetric perceptron (where this interval is symmetric around 0), we prove a conjecture of Krauth and Mezard on the structure of the solutions space when m is linear in n.  For all densities below the satisfiability threshold, typical solutions are completely isolated: they are at linear distance from the nearest other solution.  We will discuss possible implications this "frozen 1-RSB" scenario has for algorithms.  Based on joint work with Changji Xu (Harvard).