Georgia Institute of Technology College of Sciences

For general graphs, approximating the maximum clique is a notoriously hard problem even to approximate to a factor of nearly n, the number of vertices. Does the situation get better with random graphs? A random graph on n vertices where each edge is chosen with probability 1/2 has a clique of size nearly 2\log n with high probability. However, it is not know how to find one of size 1.01\log n in polynomial time. Does the problem become easier if a larger clique were planted in a random graph? The current best algorithm can find a planted clique of size roughly n^{1/2}. Given that any planted clique of size greater than 2\log n is unique with high probability, there is a large gap here. In an intriguing paper, Frieze and Kannan introduced a tensor-based method that could reduce the size of the planted clique to as small as roughly n^{1/3}. Their method relies on finding the spectral norm of a 3-dimensional tensor, a problem whose complexity is open. Moreover, their combinatorial proof does not seem to extend beyond this threshold. We show how to recover the Frieze-Kannan result using a purely probabilistic argument that generalizes naturally to r-dimensional tensors and allows us recover cliques of size as small as poly(r).n^{1/r} provided we can find the spectral norm of r-dimensional tensors. We highlight the algorithmic question that remains open. This is joint work with Charlie Brubaker.

I will discuss certain geometric properties of random matrices with independent logarithmically concave columns, obtained in the last several years jointly with O. Guedon, A. Litvak, A. Pajor and N. Tomczak-Jaegermann. In particular I will discuss estimates on the largest and smallest singular values of such matrices and rates on convergence of empirical approximations to covariance matrices of log-concave measures (the Kannan-Lovasz-Simonovits problem).

The G-equation is a Hamilton-Jacobi level-set equation, that is used in turbulent combustion theory. Level sets of the solution represent a flame surface which moves with normal velocity that is the sum of the laminar flame velocity and the fluid velocity. In this work I will discuss the large-scale long-time asymptotics of these solutions when the fluid velocity is modeled as a stationary incompressible random field. The main challenge of this work comes from the fact that our Hamiltonian is noncoercive. This is a joint work with J.Nolen.

We study a problem of estimation of a large Hermitian nonnegatively definite matrix S of unit trace based on n independent measurements Y_j = tr(SX_j ) + Z_j , j = 1, . . . , n, where {X_j} are i.i.d. Hermitian matrices and {Z_j } are i.i.d. mean zero random variables independent of {X_j}. Problems of this nature are of interest in quantum state tomography, where S is an unknown density matrix of a quantum system. The estimator is based on penalized least squares method with complexity penalty defined in terms of von Neumann entropy. We derive oracle inequalities showing how the estimation error depends on the accuracy of approximation of the unknown state S by low-rank matrices. We will discuss these results as well as some of the tools used in their proofs (such as generic chaining bounds for empirical processes and noncommutative Bernstein type inequalities).