Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, March 21, 2023 - 3:30pm

Eren C. Kızıldağ

Columbia University


Temple University

Wachman Hall 617

Many computational problems involving randomness exhibit a statistical-to-computational gap (SCG): the best known polynomial-time algorithm performs strictly worse than the existential guarantee. In this talk, we focus on the SCG of the symmetric binary perceptron (SBP), a random constraint satisfaction problem as well as a toy model of a single-layer neural network. We establish that the solution space of the SBP exhibits intricate geometrical features, known as the multi Overlap Gap Property (m-OGP). By leveraging the m-OGP, we obtain nearly sharp hardness guarantees against the class of stable and online algorithms, which capture the best known algorithms for the SBP. Our results mark the first instance of intricate geometry yielding tight algorithmic hardness against classes beyond stable algorithms. 
Time permitting, I will discuss how the same program extends also to other models, including (a) discrepancy minimization, and (b) random number partitioning problem. 
Based on joint works with David Gamarnik, Will Perkins, and Changji Xu.