Seminars

View all Seminars  |  Download ICal for this event

Algorithms Approaching the Threshold for Semi-random Planted Clique

Series: Bangalore Theory Seminars

Speaker: Rares-Darius Buhai ETH Zurich

Date/Time: Jun 02 16:00:00

Location: Microsoft Teams - Online Talk (See Teams link below)

Abstract:
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="Link
<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