BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/716
DTSTAMP:20230914T125935Z
SUMMARY:Approximating Dense Bipartite Subgraphs via an Approximate Versio
n of Caratheodory's Theorem
DESCRIPTION:Speaker: Gunjan Kumar\n\nAbstract: \nWe present algorithmic app
lications of an approximate version of Caratheodory's theorem. The theorem
states that given a set of vectors $X$ in $\\mathbb{R^d}$\, for every vec
tor in the convex hull of $X$ there exists an $\\epsilon$-close (under the
$p$-norm distance\, for $2 \\le p < \\infty $ ) vector that can be expres
sed as a convex combination of at most b vectors of $X$\, where the bound
b depends on $\\epsilon$ and the norm p and is independent of the dimensio
n $d$. This theorem can be derived by instantiating Maurey's lemma\, early
references to which can be found in the work of Pisier (1981) and Carl(19
85). However\, in this paper we present a self-contained proof of this res
ult.\n\nThe approximate Caratheodory's theorem leads to an additive approx
imation algorithm for the normalized densest $k$-bipartite subgraph proble
m. Given a graph with n vertices and maximum degree $d$\, the developed al
gorithm determines a $k \\times k$ bipartite subgraph with density w
ithin $\\epsilon$ (in the additive sense) of the optimal density in ti
me $n^{O(\\frac{log d}{\\epsilon^2})}$.\n\nThis result appears in STOC 201
5\, titled `Approximating Nash Equilibria and Dense Bipartite Subgraphs vi
a an Approximate Version of Caratheodory's Theorem' by Siddharth Barman.\n
URL:https://www.tcs.tifr.res.in/web/events/716
DTSTART;TZID=Asia/Kolkata:20161007T160000
DTEND;TZID=Asia/Kolkata:20161007T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR