Search Mailing List Archives
[theory-seminar] Theory Lunch 5/5: Frederic Koehler
junyaoz at stanford.edu
Wed May 4 23:04:03 PDT 2022
A gentle reminder: This is happening in 10 minutes.
From: theory-seminar <theory-seminar-bounces at lists.stanford.edu> on behalf of Junyao Zhao <junyaoz at stanford.edu>
Sent: Sunday, May 1, 2022 11:35 PM
To: theory-seminar at lists.stanford.edu <theory-seminar at lists.stanford.edu>; thseminar at cs.stanford.edu <thseminar at cs.stanford.edu>
Subject: [theory-seminar] Theory Lunch 5/5: Frederic Koehler
This week's theory lunch will take place Thursday at noon in the Engineering Quad<https://www.google.com/maps/place/Science+%26+Engineering+Quad+Courtyardemail@example.com,-122.1765394,17z/data=!3m1!4b1!4m5!3m4!1s0x808fbb8ce58bcc27:0x677c06a883bb7bb7!8m2!3d37.428484!4d-122.1743507>. We'll start with some socializing, followed by a talk at 12:30pm. Fred will tell us about: A Sampling Generalization of Dense MAX-CUT
Abstract: A classic result from the 90's says MAX-CUT is polynomial time approximable within (1 - \epsilon) multiplicative error on dense graphs, even though it is hard on sparse graphs. Sampling from a dense/low-threshold-rank Ising model is a version of this problem that essentially (1) replaces 'max' by 'soft-max' and (2) requires an approximation with small additive error. While interesting structural results were known for such models, it remained unclear if the sampling problem was polynomial time tractable. We discuss a new algorithm which can indeed sample and (as a special case) recovers the approximability of dense MAX-CUT.
Based on a joint work with Holden Lee and Andrej Risteski.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar