CATS-Apr-24-2015
Title
Convexity, Colors, LP and PPAD
Speaker
Ahmed Abdelkader
Abstract
We start with an overview of fundamental convexity results in discrete geometry. This includes the theorems of Radon, Carathéodory, Helly and Tverberg. We follow by describing their duals and the colorful generalizations pioneered by Bárány [1]. Then, we present some recent works on the computational aspects of the colorful Carathéodory's theorem [2] and its application to Colorful Linear Programming (CLP) [1, 3]. In particular, the authors in [3] describe a reduction from BIMATRIX, which is PPAD-complete, to CLP, which they show is NP-complete by reusing a result in [1]. This would imply that any NP-complete problem is at least as hard as any PPAD-complete problem.
[1] Bárány, Imre, and Shmuel Onn. "Colourful linear programming and its relatives." Mathematics of Operations Research 22.3 (1997): 550-567.
[2] Mulzer, Wolfgang, and Yannik Stein. "Computational Aspects of the Colorful Carathéodory Theorem." arXiv preprint arXiv:1412.3347 (2014). (accepted in SoCG 2015)
[3] Meunier, Frédéric, and Pauline Sarrabezolles. "Colorful linear programming, Nash equilibrium, and pivots." arXiv preprint arXiv:1409.3436 (2014).