<div dir="ltr">slides: <a href="https://docs.google.com/presentation/d/1-HO4OALhM7B2GCJqZ9GC6ZCkpT_3YSxqtQcr0cgAnX4/">https://docs.google.com/presentation/d/1-HO4OALhM7B2GCJqZ9GC6ZCkpT_3YSxqtQcr0cgAnX4/</a></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Oct 10, 2022 at 8:42 AM Antares Chen <<a href="mailto:antaresc@uchicago.edu">antaresc@uchicago.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><span style="font-family:Arial,Helvetica,sans-serif;font-size:large">******************************</span><span style="font-family:Arial,Helvetica,sans-serif;font-size:large">******************************</span><span style="font-family:Arial,Helvetica,sans-serif;font-size:large">**************************</span><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;color:rgb(49,49,49);word-spacing:1px"><font size="4"><br></font></b></div><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;color:rgb(49,49,49);word-spacing:1px"><font size="4"><br></font></b></div><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;color:rgb(49,49,49);word-spacing:1px"><font size="4">Date</font></b><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;font-size:1.13em;color:rgb(49,49,49);word-spacing:1px">:</b><span style="font-size:1.13em;color:rgb(49,49,49);word-spacing:1px"> </span><span style="color:rgb(49,49,49);word-spacing:1px"><font size="4">October 12, 2022</font></span><br></div><div><div style="margin:0px"><div style="margin:0px"><div style="margin:0px"><div style="margin:0px"><div style="margin:0px"><div style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;margin:0px"><div style="font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><font style="font-size:1.13em"><b>Time: </b>12:30pm CT</font></div><div style="font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><font style="font-size:1.13em"><b>Location: </b>JCL 298</font></div><div dir="auto" style="font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><b><font style="font-size:1.13em"><br></font></b></div><div dir="auto" style="margin:0px;color:rgb(49,49,49);word-spacing:1px"><font size="4"><font><b>Speaker: </b></font><a href="https://kunalmarwaha.com/" style="font-family:Arial" target="_blank">Kunal Marwaha</a></font></div><div dir="auto" style="font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><font size="4"><br></font></div></div><div style="margin:0px"><span style="color:rgb(49,49,49);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:16px;word-spacing:1px"><font style="font-size:1.13em"><b>Title:</b></font></span> <font size="4">Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses</font></div><div style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:15px;margin:0px"><b style="color:rgb(49,49,49);font-size:16px;word-spacing:1px"><font style="font-size:1.13em"><br></font></b></div><div style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:15px;margin:0px"><span style="margin:0px;font-size:16px;color:rgb(49,49,49);word-spacing:1px"><font style="font-size:1.13em"><b>Zoom: </b>[<a href="https://uchicago.zoom.us/j/92566649832?pwd=WVJyVlF3VlJ1QTc3YUg3UlJvY2xBQT09" target="_blank">link</a>]</font></span></div><div style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:15px;margin:0px"><br></div><div style="margin:0px"><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="color:rgb(49,49,49);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:13pt;margin:0px"><b>Abstract:</b></span><span style="color:rgb(32,31,30);font-family:"trebuchet ms",sans-serif;font-size:12pt;margin:0px;word-spacing:0px"> </span></font><font size="4" color="#000000"><span style="font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap">We formalize a general and deep connection between two intensely studied classes of optimization problems: constraint satisfaction problems (CSPs), studied in computer science, and spin glass models, studied in statistical physics. We demonstrate that for dense enough random CSPs, the geometric properties of the set of nearly-optimal solutions converge to those of a corresponding spin glass model. In these spin glass models, the very same geometric properties imply bounds on the average-case approximability achieved by broad classes of algorithms; these bounds are conjectured to be the best possible among all polynomial-time algorithms. The correspondence we establish here implies that the same lower bounds apply to average-case CSPs. Joint work with Chris Jones, Juspreet Singh Sandhu, Jonathan Shi; </span><a href="https://www.google.com/url?q=https://arxiv.org/abs/2210.03006&sa=D&source=calendar&ust=1665797901546505&usg=AOvVaw2abEADbjvdp4PGhaNhvf28" style="font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px;white-space:pre-wrap" target="_blank">https://arxiv.org/abs/2210.03006</a></font></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><font size="4"><br></font></span></font></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large">[</span><a href="https://urldefense.com/v3/__https://orecchia.net/event/theory-lunch/__;!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAswwp_F5nRs$" rel="noopener noreferrer" title="https://orecchia.net/event/theory-lunch/" style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large;margin:0px" target="_blank"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px">Theory</span></span></span></span></span> <span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px">Lunch</span></span></span></span> Webpage</a><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large">]</span><br style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large"><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large">[</span><a href="https://urldefense.com/v3/__https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America*Chicago__;Lw!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAsww4XtIRnQ$" rel="noopener noreferrer" title="https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America/Chicago" style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large;margin:0px" target="_blank"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px">Theory</span></span></span></span></span></span></span><span style="margin:0px"> </span><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px">Lunch</span></span></span></span></span><span style="margin:0px"> </span>Calendar</a><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large">]</span><font size="4"><br></font></span></font></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large"><br></span></span></font></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><span style="font-size:large">******************************</span><span style="font-size:large">******************************</span><span style="font-size:large">**************************</span><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large"><br></span></span></font></div></div></div></div></div></div></div></div></div>
_______________________________________________<br>
Theory mailing list<br>
<a href="mailto:Theory@mailman.cs.uchicago.edu" target="_blank">Theory@mailman.cs.uchicago.edu</a><br>
<a href="https://mailman.cs.uchicago.edu/mailman/listinfo/theory" rel="noreferrer" target="_blank">https://mailman.cs.uchicago.edu/mailman/listinfo/theory</a><br>
</blockquote></div>