<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-9">
<meta name="viewport" content="width=device-width">
<meta content="IE=edge">
<meta content="text/html; charset=UTF-8">
<style type="text/css">
<!--
html
{box-sizing:border-box;
font-size:14px;
margin:0}
table
{border-spacing:0}
td
{vertical-align:top;
margin:0}
img
{max-width:100%}
h1, h2, h3, h4, h5
{font-weight:600;
line-height:1.4}
.css-1om2ube
{width:74px;
height:18px;
margin:0 0 0 5px;
top:3px}
.css-13nbghr
{width:100%;
height:100%;
line-height:1.6em;
color:#333333;
background-color:#fafafa;
font-weight:400}
.css-18xjf65
{margin:0 auto;
clear:both;
font-size:16px;
padding:20px;
width:720px}
.css-y9bb7n
{background:#fff;
font-size:16px;
line-height:24px;
word-wrap:break-word;
padding:40px;
border-radius:6px}
.css-40d1fs
{font-size:12px;
color:#888;
margin:0;
vertical-align:baseline;
padding:20px 40px}
-->
</style>
</head>
<body itemscope="" itemtype="http://schema.org/EmailMessage" class="css-13nbghr" style="width:100%; height:100%; line-height:1.6em; color:#333333; background-color:#fafafa; font-weight:400">
<strong>
<div><font face="Tahoma" color="#000000" size="2"> </font></div>
</strong>
<hr tabindex="-1" style="display:inline-block; width:98%">
<font face="Tahoma" size="2"><b>From:</b> noreply+automations@airtableemail.com <noreply+automations@airtableemail.com>On Behalf OfTheoryBot (via Airtable) <noreply+automations@airtableemail.com><br>
<b>Sent:</b> Wednesday, April 26, 2023 12:12:31 AM (UTC-06:00) Central Time (US & Canada)<br>
<b>To:</b> Antares Chen <antaresc@uchicago.edu><br>
<b>Cc:</b> Christopher Kang <ctkang@uchicago.edu><br>
<b>Subject:</b> Theory Lunch 2023-04-26T17:30:00.000Z<br>
</font><br>
<div></div>
<div>
<div></div>
<table class="container css-18xjf65" style="border-spacing:0; margin:0 auto; clear:both; font-size:16px; padding:20px; width:720px">
<tbody>
<tr>
<td colspan="2" class="content css-y9bb7n" style="vertical-align:top; margin:0; background:#fff; font-size:16px; line-height:24px; word-wrap:break-word; padding:40px; border-radius:6px">
<p style="margin-top:0"><span>Today's Theory Lunch talk:</span></p>
<p><em><span>Eren Kızıldağ (Columbia University): Algorithmic barriers from intricate geometry in random computational problems</span></em></p>
<p><span><a href="https://urldefense.com/v3/__https://uchicago.zoom.us/j/91616319229?pwd=dDdXQnFXeGNubFRkZy9hTDQrcWlXdz09__;!!BpyFHLRN4TMTrA!9XM-RT9qT28t_k4Efn47sMI8jbt5OGe73Vbd_6G8WG4hQN--uJQIwWTAXbEWudlgSWP4oQIDStsDedNyglCn95uA50pR83NzUlk$">https://uchicago.zoom.us/j/91616319229?pwd=dDdXQnFXeGNubFRkZy9hTDQrcWlXdz09</a></span></p>
<p></p>
<p><span>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.</span></p>
<p></p>
<p><span>Time permitting, I will discuss how the same program extends also to other models, including (a) discrepancy minimization, and (b) random number partitioning problem. </span></p>
<p></p>
<p><span>Based on joint works with David Gamarnik, Will Perkins, and Changji Xu.</span></p>
</td>
</tr>
<tr>
<td colspan="2" class="footer css-40d1fs" style="font-size:12px; color:#888; margin:0; vertical-align:baseline; padding:20px 40px">
<table style="border-spacing:0">
<tbody>
<tr>
<td style="vertical-align:top; margin:0">Sent via Automations on </td>
<td style="vertical-align:top; margin:0"><a href="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$" style="color:#3276dc"><img src="https://static.airtable.com/images/type_logo@116h.png?v=3" width="74" height="18" alt="Airtable" class="css-1om2ube" style="max-width:100%; width:74px; height:18px; margin:0 0 0 5px; top:3px"></a></td>
</tr>
<tr>
<td colspan="2" style="vertical-align:top; margin:0">
<div>©2023 Airtable</div>
</td>
</tr>
</tbody>
</table>
</td>
</tr>
</tbody>
</table>
</div>
</body>
</html>