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