[Theory] FW: Theory Lunch 2023-05-03T17:30:00.000Z

[Christopher Kang]

________________________________
From: noreply+automations at airtableemail.com <noreply+automations at airtableemail.com>On Behalf OfTheoryBot (via Airtable) <noreply+automations at airtableemail.com>
Sent: Wednesday, May 3, 2023 12:02:00 AM (UTC-06:00) Central Time (US & Canada)
To: Antares Chen <antaresc at uchicago.edu>
Cc: Christopher Kang <ctkang at uchicago.edu>
Subject: Theory Lunch 2023-05-03T17:30:00.000Z


Today's Theory Lunch talk:

Neng Huang (University of Chicago): Separating MAX 2-AND, MAX DI-CUT and MAX CUT

https://uchicago.zoom.us/j/91616319229?pwd=dDdXQnFXeGNubFRkZy9hTDQrcWlXdz09<https://urldefense.com/v3/__https://uchicago.zoom.us/j/91616319229?pwd=dDdXQnFXeGNubFRkZy9hTDQrcWlXdz09__;!!BpyFHLRN4TMTrA!4seTbmqtYzNHM0Bc0uqvXj0_9doZDLYAQgVC_Vjj8I9LbNyjpOdjz-orni2g1D4-LJ12f1-8f7aN0TT-VTGlhectNCCNIi4ebvg$>

Description: In this talk, I'll discuss our recent work on MAX DI-CUT, the directed version of MAX CUT. We prove a new unique games hardness result for MAX DI-CUT, showing that it is strictly harder to approximate than MAX CUT if UGC is true, resolving a question raised by Feige and Goemans. We also obtain a new approximation algorithm for MAX DI-CUT, showing that it is strictly easier than MAX 2-AND, its natural generalization, again assuming UGC.

Based on joint work with Joshua Brakensiek, Aaron Potechin and Uri Zwick.

Sent via Automations on         [Airtable] <https://urldefense.com/v3/__https://airtable.com?utm_medium=email&utm_source=product_team&utm_content=transactional-alerts__;!!BpyFHLRN4TMTrA!4seTbmqtYzNHM0Bc0uqvXj0_9doZDLYAQgVC_Vjj8I9LbNyjpOdjz-orni2g1D4-LJ12f1-8f7aN0TT-VTGlhectNCCNL3FQFJg$>
©2023 Airtable
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230503/dd46f16e/attachment.html>