Seminars and Colloquia by Series

Thursday, December 2, 2010 - 15:05 , Location: Skiles 002 , Santosh Vempala , College of Computing, Georgia Tech , Organizer:
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.
Thursday, November 18, 2010 - 15:05 , Location: Skiles 002 , Richard Samworth , Statistical Laboratory, Cambridge, UK , Organizer:
If $X_1,...,X_n$ are a random sample from a density $f$ in $\mathbb{R}^d$, then with probability one there exists a unique log-concave maximum likelihood estimator $\hat{f}_n$ of $f$.  The use of this estimator is attractive because, unlike kernel density estimation, the estimator is fully automatic, with no smoothing parameters to choose. We exhibit an iterative algorithm for computing the estimator and show how the method can be combined with the EM algorithm to fit finite mixtures of log-concave densities. Applications to classification, clustering and functional estimation problems will be discussed, as well as recent theoretical results on the performance of the estimator.  The talk will be illustrated with pictures from the R package LogConcDEAD. Co-authors: Yining Chen, Madeleine Cule, Lutz Duembgen (Bern), RobertGramacy (Cambridge), Dominic Schuhmacher (Bern) and Michael Stewart
Thursday, November 11, 2010 - 15:05 , Location: Skiles 002 , Radoslaw Adamczak , University of Warsaw and Fields Institute , Organizer:
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).
Thursday, October 21, 2010 - 15:05 , Location: Skiles 002 , Slim Ayadi , School of Math, Georgia Tech , Organizer:
  We study the spectral properties of matrices of long-range percolation model. These are N*N random real symmetric matrices H whose elements are independent random variables taking zero value with probability 1-\psi((i-j)/b), b\in \R^{+}, where \psi is an even positive function with \psi(t)<1 and vanishing at infinity. We show that under rather general conditions on the probability distribution of H(i,j) the semicircle law is valid for the ensemble we study in the limit N,b\to\infty. In the second part, we study the leading term of the correlation function of the resolvent G(z)=(H-z)^{-1} with large enough |Imz| in the limit N,b\to\infty, b=O(N^{\alpha}), 1/3<\alpha<1. We show that this leading term, when considered in the local spectral scale leads to an expression found earlier by other authors for band random matrix ensembles. This shows that the ensemble we study and that of band random matrices belong to the same class of spectral universality. 
Thursday, October 7, 2010 - 15:05 , Location: Skiles 002 , Alexei Novikov , Penn State , Organizer:
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.
Thursday, September 30, 2010 - 15:05 , Location: Skiles 002 , Amarjit Budhiraja , University of North Carolina at Chapel Hill , Organizer:
A two-player zero-sum stochastic differential game, defined in terms of an m-dimensional state process that is driven by a one-dimensional Brownian motion, played until the state exits the domain, is studied.The players controls enter in a diffusion coefficient and in an unbounded drift coefficient of the state process. We show that the game has value, and characterize the value function as the unique viscosity solution of an inhomogeneous infinity Laplace equation.Joint work with R. Atar.
Thursday, September 16, 2010 - 15:05 , Location: Skiles 002 , Vladimir Koltchinskii , School of Mathematics, Georgia Tech , Organizer:
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).
Thursday, May 6, 2010 - 15:00 , Location: Skiles 269 , Erick Herbin , Ecole Centrale Paris , Organizer:
The aim of this joint work with Ely Merzbach is to present a satisfactory definition of the class of set-indexedL\'evy processes including the set-indexed Brownian motion, the spatial Poisson process, spatial compound Poisson processesand some other stable processes and to study their properties. More precisely, the L\'evy processes are indexed by a quite general class $\mathcal{A}$ of closed subsets in a measure space $(\mathcal{T} ,m)$. In the specific case where $\mathcal{T}$ is the $d$-dimensional rectangle$[0 ,1]^d$ and $m$ is the Lebesgue measure, a special kind of this definition was given and studied by Bass and Pyke and by Adler and Feigin. However, in our framework the parameter set is more general and, it will be shown that no group structure is needed in order to define the increment stationarity property for L\'evy processes.
Thursday, April 22, 2010 - 15:00 , Location: Skiles 269 , Jay Rosen , College of Staten Island, CUNY , Organizer:
We  provide a sufficient condition for the continuity of real valued permanental processes. When applied to the subclass of permanental processes which consists of squares of Gaussian processes,   we  obtain the sufficient condition for continuity which is also known to be necessary.    Using  an isomorphism theorem of Eisenbaum and Kaspi which relates Markov local times and permanental processes  we   obtain a general sufficient condition for the joint continuity of  the local times.
Thursday, April 8, 2010 - 15:00 , Location: Skiles 269 , Alexander Bulinski , Lomonosov Moscow State University , Organizer:
We consider various dependence concepts for random fields. Special attention is paid to Gaussian and shot-noise fields. The multivariate central limit theorems (CLT) are proved for the volumes of excursion sets of stationary quasi-associated random fields on $\mathbb{R}^d$. Formulae for the covariance matrix of the limiting distribution are provided. Statistical versions of the CLT are established as well. They employ three different estimators of the asymptotic covariance matrix. Some numerical results are also discussed.