Title: Algorithmic Applications of An Approximate Version of Caratheodory's Theorem
Speaker: Siddharth Barman (IISc CSA)
Date: 21 October 2016
Time: 2:15 – 3:15 pm
Venue: LH-1, Mathematics Department

In this talk I will present algorithmic applications of an approximate version of Caratheodory’s theorem. The theorem states that given a set of $d$-dimensional vectors $X$, for every vector in the convex hull of $X$ there exists an epsilon-close (under the $p$-norm, for $2 \leq p < \infty$) vector that can be expressed 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 ambient dimension $d$. This theorem can be obtained by instantiating Maurey’s lemma (c.f. Pisier 1980/81 and Carl 1985).

I will describe how this approximate version of Caratheodory’s theorem leads novel additive approximation algorithms for finding (i) Nash equilibria in two-player games (ii) dense subgraphs.


Contact: +91 (80) 2293 2711, +91 (80) 2293 2265
E-mail: chairman.math[at]iisc[dot]ac[dot]in