BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20230602T120000Z
UID:05bfbb8e0c180644a4d884aea5e845e7-468
DTSTAMP:19700101T120016Z
DESCRIPTION:Algorithms Approaching the Threshold for Semi-random Planted Clique
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/468/algorithms-approaching-the-threshold-for-semi-random-planted-clique/
SUMMARY:We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian. The previous best algorithms for this model succeed if the planted clique has size at least n2/3 in a graph with n vertices. Our algorithms work for planted-clique sizes approaching n1/2 — the information-theoretic threshold in the semi-random model and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige and Steinhardt.
<br>
Joint work with Pravesh Kothari and David Steurer.
<br>
<br>
Microsoft Teams link:
<br>
<a href="https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d">https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d</a>
<br>
<br>
We are grateful to the Kirani family for generously supporting the theory seminar series
<br>
<br>
<br>
Hosts: Rameesh Paul, Rahul Madhavan, Aditya Subramanian and Aditya Abhay Lonkar
DTSTART:20230602T120000Z
END:VEVENT
END:VCALENDAR