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

[Kunal Marwaha]

slides:
https://docs.google.com/presentation/d/1-HO4OALhM7B2GCJqZ9GC6ZCkpT_3YSxqtQcr0cgAnX4/

On Mon, Oct 10, 2022 at 8:42 AM Antares Chen <antaresc at uchicago.edu> wrote:

> ************************************************************
> **************************
>
> *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$>
> ]
>
> ************************************************************
> **************************
> _______________________________________________
> Theory mailing list
> Theory at mailman.cs.uchicago.edu
> https://mailman.cs.uchicago.edu/mailman/listinfo/theory
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20221013/147d080a/attachment-0001.html>