Georgia Institute of Technology College of Sciences

Workshop Theme: Submodular functions are discrete analogues of convex functions, arising in various fields of computer science and operations research. Since the seminal work of Jack Edmonds (1970), submodularity has long been recognized as a common structure of many efficiently solvable combinatorial optimization problems. Recent algorithmic developments in the past decade include combinatorial strongly polynomial algorithm for minimization, constant factor approximation algorithms for maximization, and efficient methods for learning submodular functions. In addition, submodular functions find novel applications in combinatorial auctions, machine learning, and social networks. This workshop aims at providing a forum for researchers from a variety of backgrounds for exchanging results, ideas, and problems on submodular optimization and its applications. The workshop will be held from March 19-22, 2012. For complete details and workshop program, please see the website.

Consider an N by N matrix X of complex entries with iid real and imaginary parts with probability distribution h where h has Gaussian decay. We show that the local density of eigenvalues of X converges to the circular law with probability 1. More precisely, if we let a function f (z) have compact support in C and f_{\delta,z_0} (x) = f ( z-z^0 / \delta ) then the sequence of densities (1/N\delta^2) \int f_\delta d\mu_N converges to the circular law density (1/N\delta^2) \int f_\delta d\mu with probability 1. Here we show this convergence for \delta = N^{-1/8}, which is an improvement on the previously known results with \delta = 1. As a corollary, we also deduce that for square covariance matrices the number of eigenvalues in intervals of size in the intervals [a/N^2 , b/N^2] is smaller than log N with probability tending to 1.