BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1099
DTSTAMP:20230914T125950Z
SUMMARY:Robust Algorithms for recovering planted structures in Semi-random 
 instances
DESCRIPTION:Speaker: Yash Khanna (Indian Institute of Science\, Bangalore)\
 n\nAbstract: \nIn this work\, we design algorithms for two fundamentally i
 mportant and classical graph problems in the planted setting. Both of thes
 e 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 arbitrar
 y set of vertices (S) is chosen and either a dense graph or a clique (or a
 n 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 roundi
 ng semi-definite programs and our primary focus is on recovering (complete
 ly 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. 
 \n\nThe two problems which we study are:\n1. Densest k-Subgraph/Clique\nGi
 ven an undirected graph G\, the Densest k-Subgraph problem (DkS) asks to c
 ompute a subset S of V of cardinality k such that the weight of edges insi
 de S is maximized. This is a fundamental NP-hard problem whose approximabi
 lity\, inspite of many decades of research\, is yet to be settled. There i
 s a significant gap between the best known worst-case approximation factor
  of this problem [BCC+10] and the hardness of approximation for it (assumi
 ng the Exponential Time Hypothesis) [Man17]. We ask what are some easier i
 nstances of this problem? We propose some natural semi-random models of in
 stances with a planted dense subgraph\, and study approximation algorithms
  for computing the densest subgraph in them. There are many such random an
 d semi-random models which have been studied in the literature [BCC+10\, A
 me15\, HWX16\, BA19 etc.].\n2. Independent Set in Hypergraphs\nThe indepen
 dent set problem in graphs poses the following question: given a graph\, a
 nd 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 famo
 us 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 edg
 e 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 hyp
 ergraphs have not been studied so far. Studying classical problems like th
 ese on hypergraphs is naturally of theoretical as well as practical intere
 st. We study the algorithmic problems studied in McKenzie et al. [MMT20] a
 nd develop algorithms for them in the case of hypergraphs.\n\nNote: This i
 s joint work with Anand Louis and Rameesh Paul. Both of these e-prints wil
 l be up on arXiv soon.\n\nSpeaker 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.\n-----------------\nZoom meeting link : https:
 //zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09\n
URL:https://www.tcs.tifr.res.in/web/events/1099
DTSTART;TZID=Asia/Kolkata:20201113T171500
DTEND;TZID=Asia/Kolkata:20201113T181500
END:VEVENT
END:VCALENDAR