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
Wed May 4 23:04:03 PDT 2022

A gentle reminder: This is happening in 10 minutes.

From: theory-seminar <theory-seminar-bounces at> on behalf of Junyao Zhao <junyaoz at>
Sent: Sunday, May 1, 2022 11:35 PM
To: theory-seminar at <theory-seminar at>; thseminar at <thseminar at>
Subject: [theory-seminar] Theory Lunch 5/5: Frederic Koehler

Hi everyone,

This week's theory lunch will take place Thursday at noon in the Engineering Quad<,-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...
URL: <>

More information about the theory-seminar mailing list