Seminars
View all Seminars | Download ICal for this eventAlgorithms 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