One of the most interesting aspects of the Linear Complementarity Problem (LCP) is its range from relatively easy problems such as linear and convex quadratic programming problems to NP-hard problems. A major effort in LCP theory had been the study of the Lemke algorithm, a simplex-like algorithm which is guaranteed to terminate in finite number of iterations but not necessarily with a solution (or a certificate that no solution exists). Over the years, many subclasses of LCP were proven to be workable by the Lemke algorithm. Those subclasses were often characterized as "nice" even when no polynomial upper bound for the algorithm was known to exist. In fact, for most of these classes, instances with exponential number of steps had been discovered. In this talk, I'll discuss the close connection between these classes and the PPAD (Polynomial-time Parity Argument Directed) complexity class. The discovery that computing Nash equilibrium (which is an LCP) is PPAD complete is particularly significant in analyzing the complexity of LCP. I'll also discuss the LCP reduction-via-perturbation technique and its relation to the PPAD class and the Lemke Algorithm.

This talk is based on a joint work with Sushil Verma

Ilan Adler is a professor and chairman of the department of Industrial Engineering and Operations Research at the University of California at Berkeley. Professor Adler holds B.A in Economics and Statistics from the Hebrew University in Israel, M.Sc in Operations Research from the Technion in Israel and Ph.D in Operations Research from Stanford. His research interests are in optimization theory, financial engineering and combinatorial probability models.