[Theory] [Theory Lunch] Kunal Marwaha, Wednesday 10/12 12:30pm-1:30pm, JCL 298.

[Antares Chen]

************************************************************
**************************

*Date**:* October 12, 2022
*Time: *12:30pm CT
*Location: *JCL 298

*Speaker: *Kunal Marwaha <https://kunalmarwaha.com/>

*Title:* Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses

*Zoom: *[link
<https://uchicago.zoom.us/j/92566649832?pwd=WVJyVlF3VlJ1QTc3YUg3UlJvY2xBQT09>
]

*Abstract:* 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; https://arxiv.org/abs/2210.03006
<https://www.google.com/url?q=https://arxiv.org/abs/2210.03006&sa=D&source=calendar&ust=1665797901546505&usg=AOvVaw2abEADbjvdp4PGhaNhvf28>

[Theory Lunch Webpage
<https://urldefense.com/v3/__https://orecchia.net/event/theory-lunch/__;!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAswwp_F5nRs$>
]
[Theory Lunch Calendar
<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$>
]

************************************************************
**************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20221010/8609fa99/attachment-0001.html>