Approximating the independence number and the chromatic number in expected polynomial time

The independence number of a graph and its chromatic number are known to be hard to approximate. Due to recent complexity results, unless coRP = NP, there is no polynomial time algorithm which approximates any of these quantities within a factor of n(1-epsilon) for graphs on n vertices. We show that the situation is significantly better for the average case. For every edge probability p = p(n) in the range n(-1/2+epsilon) less than or equal to p less than or equal to 3/4, we present an approximation algorithm for the independence number of graphs on n vertices, whose approximation ratio is O((np)(1/2)/log n) and whose expected running time over the probability space G(n, p) is polynomial. An algorithm with similar features is described also for the chromatic number. A key ingredient in the analysis of both algorithms is a new large deviation inequality for eigenvalues of random matrices, obtained through an application of Talagrand's inequality.