[Theory] FW: Theory Lunch 2023-02-01T18: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, February 1, 2023 12:49:46 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-02-01T18:30:00.000Z


Today's Theory Lunch talk:

Aaron Potechin (UChicago): Sum of Squares Lower Bounds for Densest k-Subgraph

https://uchicago.zoom.us/j/91616319229?pwd=dDdXQnFXeGNubFRkZy9hTDQrcWlXdz09<https://urldefense.com/v3/__https://uchicago.zoom.us/j/91616319229?pwd=dDdXQnFXeGNubFRkZy9hTDQrcWlXdz09__;!!BpyFHLRN4TMTrA!50ueZxDp8tKkonSObHOvQFOvzZcgCbiuwi1AkFsuphr2HgJBuKGnM07FUcWKrEHklO3of3ct8Ozq0TnqXfqlTbD7sE5BS2bgCJE$>

Description: In the densest k-subgraph problem, we are given a graph G and we are asked to find the subgraph of G with k vertices which has the maximum number of edges. Despite decades of research, the hardness of densest k-subgraph is only partially understood, both in the worst case and average case settings.

In this talk, I will consider the following average case variant of the densest k-subgraph problem. Can we distinguish between the following two distributions of graphs?

1. Random distribution: G(n,p) where p = n-𝛽.

2. Planted distribution: G(n,p) + G(k,q) where k = nαand q = n-𝛾.

I will describe the known upper bounds on this problem from the log-density framework and spectral algorithms. I will then describe our sum of squares lower bounds and how they compare to these upper bounds.

Sent via Automations on         [Airtable]
©2023 Airtable
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230201/4d6998f1/attachment.html>