TIME: 3:00-4:00 pm, Nov 7, 2007 PLACE: CSE 503 SPEAKER: Eddie Nikolova MIT TITLE: From Shortest Paths to Quasi-Concave Minimization ABSTRACT: In this talk I will walk through a journey of research, that started with a simple application in mind: that of finding the shortest path in an uncertain environment (or: how to get to the airport ontime). In particular, our goal was to maximize the probability that the path length does not exceed a given threshold value (deadline). This stochastic shortest path problem is one of few that have considered a nonlinear objective function--due to the difficulty of finding closed-form expressions for the objective, in addition to the challenge of optimizing the objective, which falls in the category of non-convex optimization. We give a surprising exact $n^{\Theta(log n)}$ algorithm for the case of independent normally distributed edge lengths, which is based on quasi-concave minimization. Motivated by the stochastic shortest path problem, we further embark on giving new tools for quasi-concave minimization--a problem of considerable difficulty, whose solutions are typically exponential, and usually heuristics of unknown approximation guarantees are employeed. To that effect, we provide the first smoothed analysis of quasi-concave minimization. The analysis is based on a smoothed bound for the number of extreme points of the projection of the feasible polytope onto a $k$-dimensional subspace. The bound we derive can be used to design a polynomial-time approximation algorithm for low-rank quasi-concave minimization (as is the case of the shortest path problem above). We supplement the positive smoothed bound with a hardness result: that general quasi-concave minimization is hard to approximate. The latter implies that our bound is tight, in that no polynomial smoothed bound is possible for general quasi-concave minimization. This talk is based on two recent papers, On the Hardness and Smoothed Complexity of Quasi-Concave Minimization, joint with J. Kelner (FOCS 07) Stochastic Shortest Paths via Quasi-Convex Maximization, joint with M. Brand, J. Kelner and M. Mitzenmacher (ESA 06)