Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 5/5: Frederic Koehler

Junyao Zhao junyaoz at stanford.edu
Sun May 1 23:35:54 PDT 2022


Hi everyone,

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+Courtyard/@37.4284882,-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.

Cheers,
Junyao

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20220502/11b4d120/attachment-0003.html>


More information about the theory-seminar mailing list