Department of Mathematics

Indian Institute of Science

Bangalore 560 012






Prof.  Siddharth Barman  
Affiliation : IISc, Bangalore

Subject Area






Department of Mathematics, Lecture Hall I




02:15 - 03:15 PM




October 21, 2016 (Friday)



"Algorithmic Applications of An Approximate Version of Caratheodory's Theorem"


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 vectors X, for every vector in the convex hull of X there exists an epsilon-close (under the p-norm, for 2 <= p < \infinity) 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.