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

[Christopher Kang]

Some room reservation issues today; stay tuned for updated plan.

-C
Please excuse the brevity. I am on mobile and responding quickly.
________________________________
From: uchicago-theory-students at googlegroups.com <uchicago-theory-students at googlegroups.com> on behalf of Christopher Kang <ctkang at uchicago.edu>
Sent: Wednesday, May 3, 2023 12:02:03 AM
To: uchicago-theory-students at googlegroups.com <uchicago-theory-students at googlegroups.com>; theory at mailman.cs.uchicago.edu <theory at mailman.cs.uchicago.edu>
Subject: FW: Theory Lunch 2023-05-03T17:30:00.000Z


________________________________
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

--
You received this message because you are subscribed to the Google Groups "University of Chicago Theory Students" group.
To unsubscribe from this group and stop receiving emails from it, send an email to uchicago-theory-students+unsubscribe at googlegroups.com<mailto:uchicago-theory-students+unsubscribe at googlegroups.com>.
To view this discussion on the web visit https://groups.google.com/d/msgid/uchicago-theory-students/b06b5779745646e39f66e7046c526399%40BN8PR11MB3793.namprd11.prod.outlook.com<https://urldefense.com/v3/__https://groups.google.com/d/msgid/uchicago-theory-students/b06b5779745646e39f66e7046c526399*40BN8PR11MB3793.namprd11.prod.outlook.com?utm_medium=email&utm_source=footer__;JQ!!BpyFHLRN4TMTrA!4pPg9qp8IYtkJbv3Ti9BnblC0uNGzlPRbntmR6WINUl4L5z9B370i18fQwPa4sWU0dt4JcyKgAdtwGzhvyrgkw$>.
For more options, visit https://groups.google.com/d/optout<https://urldefense.com/v3/__https://groups.google.com/d/optout__;!!BpyFHLRN4TMTrA!4pPg9qp8IYtkJbv3Ti9BnblC0uNGzlPRbntmR6WINUl4L5z9B370i18fQwPa4sWU0dt4JcyKgAdtwGzJUUwfFg$>.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230503/193d4376/attachment.html>