View all Seminars  |  Download ICal for this event

Robust Algorithms for recovering planted structures in Semi-random instances

Series: M.Tech (Research)Thesis Defence -ON-LINE

Speaker: Mr. Yash KhannaM.Tech (Research) studentDept. of CSA

Date/Time: May 03 11:00:00

Location: Microsoft Teams - ONLINE

Faculty Advisor: Dr. Anand Louis

In this work, we design algorithms for two fundamentally important and classical graph problems in the planted setting. Both of these problems are NP-hard and the bounds known from the algorithmic front are either not fully understood, or not much progress can be made because of tight lower bounds. Thus it is natural to consider semi-random models for these problems. These models are inspired from the seminal paper of Feige and Killian [FK01] and have been studied in numerous follow-up works with the latest ones by Steinhardt, and McKenzie et al. [Ste17, MMT20]. The construction of our instance starts with an empty graph, then an arbitrary set of vertices (S) is chosen and either a dense graph or a clique (or an independent set) is planted on it, the subgraph on S x VS is a random graph, while the subgraph on VS might be a random, arbitrary, or some special graph (depending on the model). Our algorithms are based on rounding semidefinite programs and our primary focus is on recovering (completely or partially) the planted structure (S) with high probability (over the randomness of the input). We give algorithms that exploit the geometry of the corresponding vectors (from the SDP) and are easy to design/analyse.
The two problems which we study are:
1) Densest k-Subgraph/k-Clique Given an undirected graph G, the Densest k-Subgraph problem (DkS) asks to compute a set S subseteq V of cardinality k such that the weight of edges inside S is maximized. This is a fundamental NP-hard problem whose approximability, in spite of many decades of research, is yet to be settled. There is a significant gap between the best known worst-case approximation factor of this problem [BCC+10] and the hardness of approximation for it (assuming the Exponential Time Hypothesis) [Man17]. We ask what are some

Speaker Bio:
Yash Khanna is a third (and final) year M.Tech (Research) student in the Department of Computer Science and Automation in the Theory group. He previously graduated from BITS Pilani. His research interests include Algorithms and Complexity.

Link to Microsoft Teams:

Host Faculty: