[Theory] FW: Theory Lunch 2023-04-26T17:30:00.000Z

[Christopher Kang]

________________________________
From: noreply+automations at airtableemail.com <noreply+automations at airtableemail.com>On Behalf OfTheoryBot (via Airtable) <noreply+automations at airtableemail.com>
Sent: Wednesday, April 26, 2023 12:12:31 AM (UTC-06:00) Central Time (US & Canada)
To: Antares Chen <antaresc at uchicago.edu>
Cc: Christopher Kang <ctkang at uchicago.edu>
Subject: Theory Lunch 2023-04-26T17:30:00.000Z


Today's Theory Lunch talk:

Eren Kızıldağ (Columbia University): Algorithmic barriers from intricate geometry in random computational problems

https://uchicago.zoom.us/j/91616319229?pwd=dDdXQnFXeGNubFRkZy9hTDQrcWlXdz09<https://urldefense.com/v3/__https://uchicago.zoom.us/j/91616319229?pwd=dDdXQnFXeGNubFRkZy9hTDQrcWlXdz09__;!!BpyFHLRN4TMTrA!9XM-RT9qT28t_k4Efn47sMI8jbt5OGe73Vbd_6G8WG4hQN--uJQIwWTAXbEWudlgSWP4oQIDStsDedNyglCn95uA50pR83NzUlk$>

Description: 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.

Sent via Automations on         [Airtable] <https://urldefense.com/v3/__https://airtable.com?utm_medium=email&utm_source=product_team&utm_content=transactional-alerts__;!!BpyFHLRN4TMTrA!9XM-RT9qT28t_k4Efn47sMI8jbt5OGe73Vbd_6G8WG4hQN--uJQIwWTAXbEWudlgSWP4oQIDStsDedNyglCn95uA50pRCTw_9vM$>
©2023 Airtable
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230426/6a339e96/attachment.html>