09/11/2020
Hi All,
Yash Khanna is giving a talk on Robust Algorithms for recovering planted structures in Semi-random instances on *Friday* this week (Nov 13) at *5:15pm* on Zoom (https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09). He was kind enough to share the link of this talk with us and everyone interested in theoretical computer science should attend this talk. Find the details below.
Title: Robust Algorithms for recovering planted structures in Semi-random instances
Speaker: Yash Khanna
Affiliation: Indian Institute of Science, Bangalore
Date and Time: 13th November 2020, 5:15pm - 6:15pm
Zoom Link:
https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
Abstract:
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 V-S is a random graph, while the subgraph on V-S might be a random, arbitrary, or some special graph (depending on the model). Our algorithms are based on rounding semi-definite 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/Clique
Given an undirected graph G, the Densest k-Subgraph problem (DkS) asks to compute a subset S of 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 easier instances of this problem? We propose some
natural semi-random models of instances with a planted dense subgraph and study approximation algorithms for computing the densest subgraph in them. There are many such random and semi-random models which have been
studied in the literature [BCC+10, Ame15, HWX16, BA19 etc.].
2. Independent Set in Hypergraphs
The independent set problem in graphs poses the following question: given a graph, and a subset of vertices such that any two vertices of the set do not have an edge between them. The maximization version of this problem features as one of the Karp's original twenty-one
NP-complete problems ([Kar72], the clique problem instead of its complement, the independent set problem). The independent set problem is relatively well understood and by the famous result of Håstad [Hås99], the lower and upper bounds of this problem are tight. Hypergraphs are a natural extension of graphs, where each edge is formed across a tuple of distinct vertices. For a graph, each tuple has a size, two. To the best of our knowledge, semi-random models on hypergraphs have not been studied so far. Studying classical problems like these on hypergraphs is naturally of theoretical as well as practical interest. We study the algorithmic problems studied in McKenzie et al. [MMT20] and develop
algorithms for them in the case of hypergraphs.
Note: This is joint work with Anand Louis and Rameesh Paul. Both of these e-prints will be up on arXiv soon.
Speaker Bio:
Yash Khanna is a third (and final) year M.Tech (Research) student in the Theory Group of CSA, IISc Bangalore. His research interests include Algorithms and Complexity. He previously graduated from BITS Pilani.
Zoom is the leader in modern enterprise video communications, with an easy, reliable cloud platform for video and audio conferencing, chat, and webinars across mobile, desktop, and room systems. Zoom Rooms is the original software-based conference room solution used around the world in board, confer...
